《数据结构相关习题》由会员分享，可在线阅读，更多相关《数据结构相关习题（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构习题,已知一棵度为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)nm,n0=1+n2+2n3+(m-1)nm,数据结构 树,数据结构 树,先序序列为ABC的二叉树有几种形态,数据结构 树,先序序列:A B C D E F G H I 中序序列:B C A E D G H F I 画出来并写出后序序列。,后序序列: C B E H G I F D A,数据结构 树,习题
2、4a：写出二叉树的三种序列，并将其恢复为森林,先序：A B D F H C E G I J 中序：F H D B A E I G J C 后序：H F D B I J G E C A,数据结构 树,习题5b：画出与题目中的树相对应的二叉树,数 据 结 构,第7章 图习题,1.已知有向图，给出该图的：每个顶点的入度、出度;邻接矩阵；邻接表;逆邻接表。,每个顶点的入度、出度;,1,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,非 对 称 矩 阵,邻接矩阵;,3,1,2,2,2,0,2,1,1,1,2,3,
3、数 据 结 构,邻接表,（出度表）,第7章 图习题,数 据 结 构,逆邻接表,（入度表）,第7章 图习题,数 据 结 构,2&7. （1）深度优先遍历顶点序列： 深度优先生成树：,1,2,3,4,6,5,第7章 图习题,7,8,数 据 结 构,2&7. （2）广度优先遍历顶点序列： 或者 广度优先生成树：,1,2,6,5,8,3,第7章 图习题,4,7,1,2,5,6,8,3,7,4,数 据 结 构,用prim算法和kruskal算法生成最小生成树,第7章 图习题,a.prim算法(从顶点A出发),数 据 结 构,第7章 图习题,a. kruskal算法,3 (D,C),5 (B,C),7 (
4、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,/,/,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,5,25(1,3,6),29(1,3,2,5),/,/,1,3,2,6,25(1,3,6),29(1,3,2,5),/,19(1,3,2),1,3,2,15(1,3),20(1,2),1,3,第7章 图习题,数 据 结 构,10 4 30,13. 对下图写出3个拓扑排序和2个逆拓扑序列,拓扑排序：,1,7,8,2,4,6,9,3,5,数 据 结 构,第7章 图习题,1,7,8,4,9,6,2,3,5,1,7,8,4,6,9,3,2,5,逆拓扑排序：,5,2,3,6,9,4,8,1,7,5,3,2,6,9,4,8,1,7,
