发布时间 : 星期六 文章数据结构各章作业题目更新完毕开始阅读
的不同二叉树棵数。
50. 如果一棵树有n1个度为1的结点，有n2个度为2的结点，……，有nm个度为m的结点，试问有
多少个度为0的结点？
51. 已知一棵二叉树的前序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ。(1)画出这棵二叉树；(2)给出这棵二叉树后序遍历序列；(3)画出这棵二叉树转换成对应的树(或森林)。
52. 假定用于通信的电文仅有8个字母A,B,C,D,E,F,G,H组成，各字母在电文中出现的频率分别为
5,25,3,6,10,11,36,4。试为这8 个字母设计不等长Huffman编码，并给出该电文的总码数。 三、算法设计
53. 设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为1的结点个数。 54. 设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为2的结点个数。 55. 设树T以孩子-兄弟链表作为其存储表示，编写一个算法统计树T的叶结点个数。 56. 设树T以孩子-兄弟链表作为其存储表示，编写一个算法计算树T的高度。
9
第七章作业 一、选择题
1. 具有n个顶点且每一对不同顶点间都有一条边的无向图被称为( )。
A. 完全无向图 B. 无向连通图 C. 无向强连通图 2. 一个有n个顶点的无向图中边数最多有( )条。
A. n B. n(n?1) C. n(n?1)/2 3. 对于具有n(n?1)个顶点的强连通图，其有向边条数至少是( ) 4. 5. 6. 7. 8.
D. 无向树图 D. 2n
A. n?1 B. n C. n?1 D. n?2 设G是一个非连通无向图，有15条边，则该图的顶点数至少有( )个。 A. 5 B. 6 C. 7 D. 8
在一个具有n个顶点的有向图中，若所有顶点的岀度之和为s，则所有顶点的入度之和为( )。 A. s B.s-1 C. s+1 D. n 一个有n个顶点和n条边的无向图一定是( )。 A. 重连通图 B. 不连通图 C. 无环的 D. 有环的 无向图的邻接矩阵是一个( )。 A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵 有n个顶点和e条边的无向图采用邻接矩阵存储，零元素的个数为( )。
22A. e B. 2e C. n?e D. n?2e 9. 带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中( )。
A. 第i行非∞的元素之和 B. 第i列非∞的元素之和 C. 第i行非∞且非0的元素个数 D. 第i列非∞且非0的元素个数 10. 设图有n个顶点和e条边，采用邻接矩阵时，遍历图的顶点所需时间为( )。 A. O(n) B. O(n) C. O(e) D. O(ne) 11. 设图有n个顶点和e条边，采用邻接表时，遍历图的顶点所需时间为( )。
A. O(n?e) B. O(n) C. O(e) D. O(ne) 12. 图的深度优先搜索类似于树的( )次序遍历。
A. 先根 B. 中根 C. 后根 D. 层 13. 图的广度优先搜索类似于树的( )次序遍历。
A. 先根 B. 中根 C. 后根 D. 层 14. 采用邻接表存储的图的深度优先搜索算法类似于二叉树的( )。
A. 中序遍历 B. 前序遍历 C. 后序遍历 D. 层次遍历 15. 采用邻接表存储的图的广度优先搜索算法类似于二叉树的( )。
A. 中序遍历 B. 前序遍历 C. 后序遍历 D. 层次遍历
16. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )。
A. 强连通图 B. 连通图 C. 有回路 D. 一棵树
17. 如果一个连通网络G中各边权值互不相同，权重最小的边一定包含在G的( )生成树中。
A. 最小 B. 任何 C. 广度优先 D. 深度优先 18. 任何一个连通图的最小生成树( )。
A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 19. 一个有n个顶点和e条边的连通图的生成树有( )条边。
A. n B. e C. n?1 D. n?1
20. 设一个n个顶点的带权连通图有nlog2n条边，则应该选通( )算法来求这个图的最小生成树，
从而使计算时间较少。 A. Prim B. Kruskal C. DFS D. BFS
2210
21. 求最短路径的Dijkstra算法的时间复杂度为( )。 A. O(n) B. O(n?e) C. O(n2) 22. 求最短路径的Floyd算法的时间复杂度为( )。
D. O(ne)
A. O(n) B. O(ne) C. O(n2) D. O(n3) 23. 设有向图具有n个顶点和e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为( )。 A. O(n) B. O(n?e) C. O(n2) D. O(ne)
24. 设有向图具有n个顶点和e条边，如果用邻接矩阵作为它的存储结构，则拓扑排序的时间复杂度
为( )。 A. O(nlog2e) B. O(n?e) C. O(n2) 二、应用题
25. 针对图1所示的有向图，画出该图的邻接矩阵、邻接表和逆邻接表。
ADD. O(ne)
BEabdcegf 图1 图2
26. 对图2所示的无向图，从顶点a开始进行深度优先遍历，给出2个可得到的顶点访问序列；从顶
点a开始进行广度优先遍历，给出2个可得到的顶点访问序列。
27. 已知一个带权连通图如图3所示，分别使用Prim算法和Kruskal算法求其最小生成树。
B1220CFa3b12cA586D1510C98FE1510651
4
d8e9f
图3 图4
28. 已知一个带权有向图如图4所示，用Dijkstra算法求从顶点a到其余各顶点的最短路径及路径长
度。
29. 如图所示的AOE网，求
(1) 完成此工程最少要多少天(设弧上的权值为天数)； (2) 每项活动ai的最早开始时间e(ai)和最迟开始时间l(ai)； (3) 哪些是关键活动；
(4) 是否存在某些活动，当其提高速度后能使整个工程缩短工期?
11
BF5A3D4G4J36C631E52I24H
图5
12