2022年数据结构复习题-答案--推荐 .pdf

《2022年数据结构复习题-答案--推荐 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构复习题-答案--推荐 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 6 章 树和二叉树一、选择题（每小题1 分，共 10 分）1.以下数据结构中， （A ）是非线性数据结构。A.树B.线性表C.队列D.栈2.在一棵二叉树中第五层上的结点数最多为（B ） 。A.8 B.15 C.16 D.32 3. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（A ） 。A. CBEFDA B. FEDCBA C. CBEDFA D. 不定4.若一棵二叉树具有10 个度为 2的结点，5 个度为 1 的结点，则度为 0 的结点个数是( B ） 。A.9 B.11 C.15 D.不确定5.给定二叉树如图所示。设N 代表二叉树的根

2、，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（D ） 。A. LRN B. NRL C. RLN D. RNL 6.在下列存储形式中，哪一个不是树的存储形式？（D ）A.双亲表示法B.孩子表示法C.孩子兄弟表示法D.顺序存储表示法7.有 n 个叶子的哈夫曼树的结点总数为（D ） 。A不确定B2n C2n+1 D2n-1 8.设 i 为 n 个结点的完全二叉树结点编号，i=1 ， 2，3.n；若 i （ n-1 ）/2 时，结点 i 的右孩子为（ B ）A.2i B.2i+1 C.2i-1 D.i+19. 由分别带权为9、2、5

3、、7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ） 。A.23 B.37 C.44 D.46 10.一棵具有n 个结点的完全二叉树的树高度（深度）是（A ） 。A. +1 B. log2n+1 C. D. log2n-1 11.由权值分别为7， 9， 4， 2， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 （B ） 。A.36 B.60 C.48 D.53 12.由权值分别为11， 8， 6， 2， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。A. 24 B. 71 C. 48 D. 53 13.具有 35 个结点的完全二叉树的深度为( B )。A.

4、5 B. 6 C. 7 D. 8 14.由权值分别为, , , , 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ） A24 B 55 C 72 D53 15.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( A )。 A不发生改变 B发生改变 C不能确定 D以上都不对名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 16.具有 10 个叶子结点的二叉树中有( B )个度为 2 的结点。 A 8 B9 C1

5、0 D 11 二、判断题（每小题1 分，共 10 分）1.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（对）2.二叉树的遍历结果不是唯一的。（对）3.二叉树中序线索化后，不存在空指针域。（对）4.在二叉树的第i 层上至少有2i-1个结点 (i=1) 。 （错）5.设 T 为哈夫曼树，具有5 个叶结点，树T 的高度最高可以是4。(错) 6.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。（错）7.有 n 个叶子结点的哈夫曼树所具有的结点数为2n。 （错） 。8.用树的前序遍历和中序遍历可以导出树的后序遍历。( 错) 9二叉树的后序遍历序列中，任意一个

6、结点均处在其孩子结点的后面。（ ）10度为 2 的有序树是二叉树。 （ ）11二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（ ）12用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）13若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（ ）14在哈夫曼树中，权值最小的结点离根结点最近。( ) 三、填空题（每空1 分，共 10 分）1.具有 n 个结点的完全二叉树的深度为。+1 2.设只含根结点的二叉树的高度为1，则高度为 k 的二叉树的最大结点数为，最小结点数为。2k-1 、k3.将一棵树转化为二叉树时，此二叉树的根节点的右子树为。空树四、简答题（共10

7、 分）1. 满二叉树和完全二叉树有什么区别？答： 满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1 层是满的，但最底层却允许在右边缺少连续若干个叶子结点，满二叉树是完全二叉树的一个特例。2. 画出二叉树的五种基本形态。答： 二叉树的五种基本形态为：3. 在结点个数为n(n1) 的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答： 结点个数为n 时，高度最小的树的高度为1，有 2 层；它有 n-1 个叶结点， 1 个分支结点；高度最大的树的高度为n-1 ，有 n 层；它有 1 个叶结点， n-1 个分支结点

8、。4. 什么是哈夫曼（Huffman）树？答： 设有 n 个权值 w1,w2, wn ，构造一棵有n 个叶子结点的二叉树，每个叶子的权值为wi, 则带权路径长度WPL 最小的二叉树叫哈夫曼树或最优二叉树。或者：又称最优二叉树，它是n 个带权叶子结点构成的所有二叉树中，带权路径长度WPL 最小的二叉树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 五、应用题（共40 分）1. （ 8 分）已知一棵树的边的集合表示为：(L,N),

9、(G ,K),(G,L),(G,M),(B,E),(B,F),(D,G), (D,H),(D,I),(D,J),(A,B),(A,C),(A,D)画出这棵树，并回答下列问题：(1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？(2)树的度是多少？各个结点的度是多少？(3)树的深度是多少？各个结点的层数是多少？以结点为根的子树的深度是多少？2. 用一维数组存放的一棵完全二叉树如下表所示A B C D E F G H I J K L 写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序。3.（5 分） 对任何一棵二叉树T， 如果其终端结点数为n0， 度为 2 的结点数为n2， 证明：n0=n

10、2+1。4. 叙述并证明二叉树的性质3。5. （ 8 分）已知一棵二叉树如下，（1）请分别写出按前序、中序、后序和层次遍历时得到的结点序列。（2）如果此二叉树由森林转换得到，请画出原森林中的各棵树。6. （8 分）画出由下列序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIKJ；中序： ABCDEFGHIJK。7. 有二叉树中序序列为：ABCEFGHD，后序序列为： ABFHGEDC，请画出此二叉树，并写出二叉树的先序遍历序列和层次遍历序列。8. （ 8 分）二叉树T的前序遍历序列和中次遍历序列分别是ABCDEFG 和 CBEDAFG，试画出该二叉树，并写出二叉树的后序遍历序列

11、和层次遍历序列。9. （ 6 分）二叉树的先序序列为EBADCFHGIKJ；二叉树的中序序列为ABCDEFGHIJK，请画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。10. （8 分）设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C 请画出该二叉树，并将这棵二叉树转换成对应的树（或森林）。11. （8 分）设一棵二叉树的前序序列为ABDGECFH，中序序列为： DGBEAFHC 。试画出该二叉树。并写出后序和层次遍历序列。12.（6 分）设给定一个权值集合W=(3 ，5，7，9，11)，要求根据给定的

12、权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL 。13. （ 8分） 假设字符a,b,c,d,e,f,g,h的使用频度分别是0.15,0.19,0.07,0.08,0.04,0.23，0.13 ，0.11 画出哈夫曼树并写出a,b,c,d,e,f,g,h的 Huffman（哈夫曼）编码。14. （8 分）假设字符a,b,c,d,e,f的使用频度分0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的 Huffman（哈夫曼）编码。15.（8 分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.10,0.12,0.16,0.25,0.30

13、，构造哈夫曼树并写出a,b,c,d,e,f的哈夫曼编码。16. （6 分）试分别画出具有三个结点的树和三个结点的二叉树的不同形态。17. 请画出下图所示的树所对应的二叉树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 答案：18. （6 分）请画出与下列二叉树对应的森林。19. 已知一棵树边的集合为, , ,，请回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？哪些是分支结点？（3）哪个是结点G的双亲结点？（ 4）哪些是

14、结点G的祖先？（ 5）哪些是结点G的孩子？（6）哪些是结点E的子孙？（ 7）哪些是结点E的兄弟？哪些是结点F 的兄弟？（8）结点 B和 N的层次号分别是多少？（9）树的深度是多少？（10）以结点 C为根的子树的深度是多少？20. 假设在树中，结点x 是结点 y 的双亲时，用（x，y）来表示树边。已知一棵树边的集合为：（i ，m ） ， （i ，n） ， （e，i ） ， （b，e） ， （b，d） ， （a，b） ， （g，j ） ， （g，k） ， （c，g） ， （c，f ） ， （h，l ） ， （c， h） ， （a，c）。用树形表示法画出此树，并回答下列问题：（1）哪个是根结点： （

15、2）哪些是叶结点？（3）哪个是g 的双亲？（4）哪些是 g 的祖先？（ 5）哪些是 g 的孩子？（ 6）哪些是 e 的子孙？（7）哪些是 e 的兄弟？哪些是f 的兄弟？（ 8）结点 b 和 n 的层次各是多少？（9）树的深度是多少？（10）以结点 c 为根的子树的深度是多少？（11）树的度数是多少？21. 已知一棵树边的结点为（I,M ） ，(I ，N),(E ，I),(B，E)，(B，D),(C ，B),(G ，L)，(G，K)， (A，G)，(A， F),(H ， J) ，(A，H)，(C，A) ，试画出这棵树，并回答下列问题：(1) 哪个是根结点？(2) 哪些是叶子结点？(3) 树的深度

16、是多少？六、算法题（共12 分）1. 编写计算二叉树深度的算法(二叉树的深度也叫二叉树的高度)。答： int Depth (BiTree T ) / 返回二叉树的深度 if (T ) depthLeft = Depth( T-lchild );/求左子树的深度 depthRight= Depth( T-rchild ); /求右子树的深度 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

17、 - - - - - - 第 4 页，共 5 页 - - - - - - - - - /深度的最大值+1 else depthval = 0; return depthval; 2. 编写算法：统计一个二叉树中所有叶子结点的数目。答： void CountLeaf (BiTree T, int& count) / 在实际使用时，count 作为全局变量，其初始值为0 if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf 参考题：3. 编写算法先序、中序、后序递归遍历二叉树的算法4. 编写中序非递归遍历二叉树的算法。5. 试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -