16. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是[ 33 ] 。 选择题：

17. 按照二叉树的定义，具有3个结点的二叉树有___C________种形态。 (A)3 (B)4 (C)5 (D)6 18. 二叉树是非线性数据结构，它（ C ）。 (A)不能用顺序存储结构存储; (B)不能用链式存储结构存储;

(C)顺序存储结构和链式存储结构都能存储; (D)顺序存储结构和链式存储结构都不能使用 19. 下列陈述中正确的是（ D ）。

(A)二叉树是度为2的树

(B)二叉树中结点只有一个孩子时无左右之分 (C)二叉树中必有度为2的结点

(D)二叉树中最多只有两棵子树，并且有左右之分

20. 设有一棵22个结点的完全二叉树，那么整棵二叉树有（ D ）个度为0的结点? (A)6 (B)7 (C)8 (D)11

21. 某非空二叉树共有叶结点15个，没有度为1的结点，则该树共有（ A ）个结点。 (A)29 (B)28 (C)27 (D)不能确定

22. 已知完全二叉树有26个结点，则整棵二叉树有（ A ）个度为1的结点？ (A)1 (B)0 (C)2 (D)不确定

23. 将一棵有50个结点的完全二叉树编号，根结点为1，每层从左到右依次编号，则编号为49的结点的双亲结点的编号是（ B ）。 (A)23 (B) 24 (C) 25 (D)26

24. 对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ C ）方法实现编号。 (A) 前序遍历 (B) 中序遍历 (C) 后序遍历 (D) 从根开始进行层次遍历

25. 一棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号，（号码为1-n），编号须具有如下性质：二叉树中任一结点V，其编号等于其左子树中结点的最大编号加1。而其右子树中结点的最小编号等于V的编号加1。试问应按（B ）遍历顺序编号。 (A)前根 B中根 C后根 D层次

27. 某二叉树的中序遍历为：BDAEC，后序遍历为：DBECA，则前序遍历为（ A ）。 (A)ABDCE (B)ADBCE (C)ABDEC (D)BDACE

28. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（ D ）。 (A)DEBAFC (B)DEFBCA (C)DEBCFA (D)DEBFCA

29. 在有n个叶子结点的哈夫曼树中，其结点总数为（ D ）。 (A)不确定 (B)2n (C)2n+1 (D) 2n-1 30. 哈夫曼树的带权路径长度是（ B ）。

(A) 所有结点权值之和 (B) 所有叶结点带权路径长度之和 (C) 权结点的值 (D) 除根以外所有结点权值之和 31. 下列说法正确的是（ A ）。

(A) 树的先根遍历序列与其对应的二叉树的先根遍历序列相同 (B) 树的先根遍历序列与其对应的二叉树的后根遍历序列相同 (C) 树的后根遍历序列与其对应的二叉树的先根遍历序列相同 (D) 树的后根遍历序列与其对应的二叉树的后根遍历序列相同 判断题：

32. 对于一棵任意二叉树，若叶子结点数为n0，度为2的结点个数为n2，则有n2= n0+1。( 错 ) 33. 对于一棵任意二叉树，若叶子结点数为n0，度为2的结点个数为n2，则有n0= n2+1。( 对 ) 34. 深度为n的非空二叉树的第i层最多有2n-1 个结点。( 错 ) 35. 非空二叉树的第i层最多有2i-1 个结点。( 对 ) 36. 二叉树中，任何一个结点的度为2。( 错 ) 37. 二叉树中每个结点的两棵子树是有序的。( 对 )

38. 具有12个结点的完全二叉树有4层深。( 对 )

39. 具有12个结点的完全二叉树有5个度为2的结点。( 对 )

40. 线索二叉树是在二叉树的所有结点的存储结构中增加先驱和后继指针得到的。( 错 ) 41. 已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( 对 ) 42. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( 错 ) 43. 哈夫曼树中不存在度为1的分支结点。( 对 ) 44. 有n个叶子结点的哈夫曼树共有2n-1个结点。( 对 )

第七章

1. 在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是【 连通 】2. 3. 4. 5. 6. 7. 8. 9.

的。

图的存储结构主要有【 顺序存储 】和【链式存储 】两种。

遍历图的基本方法有【 深度 】优先搜索和【 广度 】优先搜索两种。 有如图所示的图的邻接矩阵，从1顶点出发对该图进行深度优先搜索的结点序列是【 1,2,3,4,6,5 】，广度优先搜索的结点序列是【 1,2,3,5,6,4 】。 若连通图G的顶点个数为n，则G的生成树的边数为【 n-1 】。

有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的【出 】 度 。

有向图G用邻接矩阵存储，其第i列的所有元素之和等于顶点i的【入 】 度 。

无向图的邻接矩阵是一个【对称 】矩阵；在邻接矩阵上，无向图中顶点vi的度为【2 】； 邻接表上，无向图中顶点vi的度为【1 】。 一个具有n个顶点的简单无向图最多（ C ）条边。

(A)n (B)n(n-1) (C)n(n-1)/2 (D)2n 10. 有8个结点的无向连通图最少有（ C ）条边。 (A)5 (B) 6 (C)7 (D)8 11. 一个具有n个顶点的无向完全图的边数为B

(A) n(n+1)/2 (B) n(n-1)/2 (C) n(n-1) (D) n(n+1)

12. 任何一个带权的无向连通图的最小生成树B

(A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D) 可能不存在 13. 已知一个有向图２，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为D (A) a d b e f c B .a d c e f b C .a d c b f e (D) a d e f c b

14. 对下图1所示的带权有向图，从顶点1到5 的最短路径为（ D ）。 (A)1,4,5 (B)1,2,3,5 (C)1,4,3,5 (D)1,2,4,3,5

16. 某有向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接表由m个头结点和n个表结点组成。( 错 ) 17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(对 ) 18. 有n个结点的无向完全图有n*(n-1)/2条边。( 对 ) 19. 有n个结点的有向完全图有n*(n-1)/2条边。( 错 )

20. 某无向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接表由m个头结点和n个表结点组成。( 错 ) 21. 有向图中所有顶点的入度之和等于所有顶点的出度之和。( 错 ) 22. 普里姆算法是采用“加边法”构造最小生成树的。( 错 ) 23. AOE 网是一种带权的无环连通图。( 错 ) 24. AOE 网是一种带权的有向无环图。( 对 )

25. AOE网所表示的工程至少所需要的时间等于从源点到汇点的最长路径长度。( 对 ) 26. AOE网来表示工程计划时，从源点到汇点的最短路径表示了关键路径。( 错 )