《《精编》数据结构相关习题》由会员分享，可在线阅读，更多相关《《精编》数据结构相关习题（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的二叉树有几种形态 数据结构树 先序序列 ABCDEFGHI中序序列 BCAEDGHFI画出来并写出后序序列 后序序列 CBEHGIFDA 数据结构树 习题4a 写出二叉树的三种序列 并将其恢复为森林 先序 ABDFHCEGIJ中序 FHD
2、BAEIGJC后序 HFDBIJGECA 数据结构树 习题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 数据结构 邻接表 出度表 第7章图习题 数据结构 逆邻接表 入度表 第7章图习题 数据结构 2 7 1 深度优先遍历顶点序列 深度优先生成树 1 2 3 4 6 5
3、第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 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章图习题 数据结构 10430 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
