习题六树和二叉树6.1 单项选择题(A) (B) (C) (D)图8.7 4棵二叉树1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。

图8.8 4棵二叉树2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。

3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__oA. t —> left二NULLB. t —> ltag=1C. t —> ltag=1 且t —> left=NULLD. 以上都不对4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B__ oA.正确B. 错误5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A__。

A.正确B. 错误6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_B_oA.正确B. 错误7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__oA. 2hB. 2h-1C. 2h+1D. h+1 a8. 如图8.9所示二叉树的中序遍历序列 B o图8.9 一棵二叉树A. abcdgefB. dfebagcC. dbaefcgD. defbagc9. 已知某二叉树的后序遍历序列是d abec，中序遍历序列是debac，它的前序遍历序列是D ___ 。

A. acbedB. decabC. deabcD. cedba10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是B 。

A. a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孙11•假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为个。

BA. 15B. 16C. 17D. 4712. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是D _____。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法__B__ oA.正确B. 错误14. 按照二叉树的定义，具有3个结点的二叉树有_。

__种。

A. 3B. 4C. 5D. 615. 一棵二叉树如图8.10所示，其中序遍历的序列为a图8.10 一棵二叉树A. abdgcefhB. dgbaechfC. gdbehfcaD. abcdefgh16. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。

结论A是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对17. 深度为5的二叉树至多有_C_个结点A. 16B. 32C. 31D. 1018. 在一非空二叉树的中序遍历序列中，根结点的右边_A___。

A.只有右子树上的所有结点B. 只有右子树上的部分结点C.只有左子树上的部分结点D. 只有左子树上的所有结点a 19. 树最适合用来表示_C_。

A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据20. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A___。

A. 不发生改变B. 发生改变C. 不能确定D. 以上都不对21. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用__C__存储结构。

A. 二叉链表B. 广义表存储结构C. 三叉链表D. 顺序存储结构22. 对一个满二叉树，m个树叶，n个结点，深度为h,则__D__。

A. n=h+mB. h+m=2nC. m=h-1D. n=2 h-123. 如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为_C。

A. uwvtsB. vwutsC. wuvtsD. wutsv24. 具有五层结点的二叉平衡树至少有_B_t结点。

F(n)=F(n-1)+F(n-2)+1, 1 是根节点，F(n-1) 是左子树的节点数量，F(n-2) 是右子树的节点数量A. 10B. 12C. 15D. 1725. 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_C__。

A. n在m右方B. n 是m祖先C. n 在m左方D. n 是m子孙6.2 填空题(将正确的答案填在相应的空中)1. 有一棵树如图8.12 所示，回答下面的问题：⑴ 这棵树的根结点是___K1_；⑵ 这棵树的叶子结点是___K2,K5,K7,K4_ ；⑶ 结点k3 的度是_2___；⑷ 这棵树的度是 —3_; ⑸这棵树的深度是_4___; ⑹ 结点k3的子女是 _K5,K6__; ⑺结点k3的父结点是_K1__;2. 指出树和二叉树的三个主要差别 _树的结点个数至少为1,而二叉树的结点个数 可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为 2；树的结点无左、右之分，而二叉树的结点有左、右之分 。

3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目 的是_利用二叉树的已有算法解决树的有关问题—04. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t 中，如图8.13所示,k-22 +16. 在一棵二叉树中，度为零的结点的个数为 n °,度为2的结点的个数为n 2,则 有 n °=_n2+1 _ 07. 一棵二叉树的第i (i > 1)层最多有_2'一1______ 个结点；一棵有n (n>0)个结点的 满二叉树共有__ 2 [log2n+1]-1 —个叶子和 —2[log2n+1] -1_个非终端结点。

8. 结点最少的树为 —只有一个结点的树__，结点最少的二叉树为_空二叉树 —o则该二叉树的链接表示形式为9. 现有按中序遍历二叉树的结果为abc，问有_5—种不同形态的二叉树可以得到10. 根据二叉树的定义，具有三个结点的二叉树有—5_种不同的形态，它们分别是—参照楼上—011. 由如图8.17所示的二叉树，回答以下问题：⑴其中序遍历序列为_dgbaechif_ ;⑵其前序遍历序列为_____abdgcefhi _；⑶其后序遍历序列为_gdbeihfca _____ ;⑷该二叉树的中序线索二叉树为⑸该二叉树的后序线索二叉树为⑹该二叉树对应的森林是a12. 已知一棵树如图8.20所示，转化为一棵二叉树，表示为13. 以数据集｛4 , 5, 6, 7, 10, 12, 18｝为结点权值所构造的 Huffman 树为，其带权路径长度为_165—6.3 算法设计题:1 •试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数 2. 一棵度为2的树与一棵二叉树有何区别？3. 一棵含有N 个结点的k 叉树,可能达到的最大深度和最小深度各为多少？4. 证明:一棵满k 叉树上的叶子结点数n 。

和非叶子结点数 e 之间满足以下关系o=(k-1) n 1+15. 请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线 索。

b dc eg图8.20 一棵树3719131865缺点。

8. 假设一棵二叉树的先序序列为 EBADCFHGIK 和中序序列为ABCDEFGHIJ K 请画 出该树。

9. 编写按层次顺序(同一层自左至右)遍历二叉树的算法。

习题七图7.1 单项选择题 1.在一个图中，所有顶点的度数之和等于所有边数的 _A_J 咅 A. 1/2 B. 1 C. 2 D. 42. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 __B__倍A. 1/2B. 1C. 2D. 43. 一个有n 个顶点的无向图最多有__C 」边。

A. n B. n(n-1) C. n(n -1)/2 D. 2n4. 具有4个顶点的无向完全图有_A_条边。

A. 6 B. 12 C. 16 D. 20GFKCEBCHJ树的后根次序访问序列为 DIA FCJH爭组成,0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10 使用0-7的二进制表示形式是另一种编码方案。

对于上述实例，比较两种方案的优。

试为这八个字母设计哈夫曼编码。

A 6.画出和下列已知序列对应树的先根次序访问序文仅有八个电文中出现的频率分别为 H7•假设用于通讯GA. 5B. 6C. 7D. 86.在一个具有n 个顶点的无向图中，要连通全部顶点至少需要 _C_条边A. nB. n+1C. n-1D. n/2 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是9. 已知一个图如图9.5所示，若从顶点a 出发按深度搜索法进行遍历，则可能得 到的一种顶点序列为__D ①按宽度搜索法进行遍历，则可能得到的一种顶点序 列为__②__。

① A. a,b,e,c,d,f B. e,c,f,e,b,dC. a,e,b,c,f,dD.a,e,d,f,c,b② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D.a,c,f,d,e,b10. 已知一有向图的邻接表存储结构如图9.6所示。

7.对于一个具有 —D — A. n B. (n-1) C. n-1 D. n8.对于一个具有 n 个顶点和e 条边的无向图，若采用邻接表表示，贝9表头向量的大小为一①A —;所有邻接表中的接点总数是 一②C① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. eC.2eD. n+e2v1出发，所得到的顶点序列是3,v5,v4 B. v1,v2,v3,v4,v5——A. v1C. v1,v3,v4,v5,v2D. v1,v4,v3,v5,v2⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是_B_。

A. v1,v2,v3,v4,v5B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4D. v1,v4,v3,v5,v211. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的_A_。

A.先序遍历B. 中序遍历C. 后序遍历D. 按层遍历12. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_D___。

A.先序遍历B. 中序遍历C. 后序遍历D. 按层遍历13. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用___D仝A.求关键路径的方法B. 求最短路径的Dijkstra 方法C.宽度优先遍历算法D. 深度优先遍历算法7.2 填空题（将正确的答案填在相应饿空中）1. n个顶点的连通图至少_n-1 _____ 条边。