数据结构相关习题

数据结构习题2已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…nm个度为m的结点，则该树中有多少个终端结点。解：设n为总结点数，则有(总结点数)n=n0+n1+n2+…nm(总边数)n-1=1*n1+2*n2+…m*nm两式相减得：1=n0-n2-2n3-…-(m-1)nmn0=1+n2+2n3+…+(m-1)nm=1+∑(i-1)nii=1m

数据结构

树

数据结构

树先序序列为ABC的二叉树有几种形态ABCABCABCABCABC

数据结构树先序序列:ABCDEFGHI中序序列:BCAEDGHFI画出来并写出后序序列。ABCDEFGHI后序序列:CBEHGIFDA

数据结构

树习题4a：写出二叉树的三种序列，并将其恢复为森林ABHCEGJIDFABCDFCEGHI先序：ABDFHCEGIJ中序：FHDBAEIGJC后序：HFDBIJGECA

数据结构树习题5b：画出与题目中的树相对应的二叉树127111281413459103612711128141345910367数据结构第7章图习题1.已知有向图，给出该图的：每个顶点的入度、出度;邻接矩阵；邻接表;逆邻接表。①每个顶点的入度、出度;出度入度654321214365312456100010100000010000111000000000111000非对称矩阵②邻接矩阵;31222021112351632466258数据结构1423∧∧∧1∧∧③邻接表1∧654321654321（出度表）第7章图习题5163246543216543216649数据结构④逆邻接表2534∧∧∧∧2∧6∧3（入度表）第7章图习题51632410数据结构2&7.（1）深度优先遍历顶点序列：深度优先生成树：123465第7章图习题786135247811数据结构2&7.（2）广度优先遍历顶点序列：或者广度优先生成树：126583第7章图习题4761352478125683746135247812数据结构用prim算法和kruskal算法生成最小生成树第7章图习题BAEFGDC182721161412875319a.prim算法(从顶点A出发)13数据结构第7章图习题BAEFGDC182721161412875319a.kruskal算法3(D,C)5(B,C)7(B,D)8(D,E)12(B,E)14(A,E)16(G,E)18(A,G)19(A,B)21(F,D)√√√√√××27(F,G)√××

最短路径长度

（1,3）15（1,3,2）19

（1,3,6）25（1,3,2,5)29（1,3,6,4）29终点dist集合SV2V3V4V5V612345////////////////29(1,3,6,4)////////////////1,3,2,6,5,4////////29(1,3,2,5)29(1,3,6,4)////////////////1,3,2,6,525(1,3,6)29(1,3,2,5)∞////////////////1,3,2,625(1,3,6)29(1,3,2,5)∞////////19(1,3,2)1,3,2∞∞∞15(1,3)20(1,2)1,3√√√√√第7章图习题数据结构104305243162204151510101513.对下图写出3个拓扑排序和2个逆拓扑序列