《习题6树和二叉树.doc》由会员分享，可在线阅读，更多相关《习题6树和二叉树.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、如有侵权，请联系网站删除，仅供学习与交流习题6 树和二叉树【精品文档】第 5 页习题6 树和二叉树说明：本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。6.1 单项选择题1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B_。A. 正确 B. 错误2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。 A15 B16 C17 D473. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。A. 3 B. 4 C. 5 D. 64. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_C_种。A. 5 B.
2、 6 C. 30 D. 325. 深度为5的二叉树至多有_C_个结点。A. 16 B. 32 C. 31 D. 106. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ B _。A. 2h B. 2h-1 C. 2h+1 D. h+17. 对一个满二叉树，m个树叶，n个结点，深度为h，则_A_ 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-18. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历
3、为uwtvs，那么该二叉树的后序为_C_。 A. uwvts B. vwuts C. wuvts D. wutsv10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A. 正确 B. 错误11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_D_。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 在一非空二叉树的中序遍历序列中，根结点的右边_A_。A. 只有右子树上的所有结点 B. 只有右子树上的部分结点C. 只有左子树上的部分结点
4、D. 只有左子树上的所有结点13. 如图6.1所示二叉树的中序遍历序列是_B_。A. abcdgef B. dfebagc C. dbaefcg D. defbagcgcefdbaagedbchf图6.2 图6.1 14. 一棵二叉树如图6.2所示，其中序遍历的序列为_ B _。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgha15设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孙16. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是
5、_D_。 A. acbed B. decab C. deabc D. cedba17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_C_存储结构。A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构18. 如图6.3所示的4棵二叉树，_C_不是完全二叉树。(A) (B) (C) (D)图6.324. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_A_是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列
6、与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对25. 树最适合用来表示_C_。A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据6.2 填空题（将正确的答案填在相应的空中）k1 11kkkkkk21 4356 71. 有一棵树如图6.5所示，回答下面的问题： 这棵树的根结点是_k0_； 这棵树的叶子结点是_； 结点k3的度是_2_； 这棵树的度是_3_； 这棵树的深度是_4_； 结点k3的子女是_k5,k6_； 结点k3的父结点是_k1_；2. 指出树和二叉树的三个主要差别：树的结点个
7、数至少为1,而二叉树的结点个数可以为0树中结点的最大度数没有限制,而二叉树结点的最大度数为2树的结点无左、右之分,而二叉树的结点有左、右之分3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题_。4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为_ _。123456789101112131415161718192021eafdgcjlhb图6.6 一棵二叉树的顺序存储数组t5. 深度为k的完全二叉树至少有_2k-1_个结点。至多有_2k-1_个结点，若按
8、自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_1k-2+1_。6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=_n2+1_。7. 一棵二叉树的第i（i1）层最多有_2i-1_个结点；一棵有n（n0）个结点的满二叉树共有_(n+1)/2_个叶子和_(n-1)/2_个非终端结点。8. 结点最少的树为_只有一个结点的树_，结点最少的二叉树为_空的二叉树_。9. 现有按中序遍历二叉树的结果为abc，问有_5_种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_。10. 由如图6.7所示的二叉树，回答以下问题： 其中序遍历序列
9、为_dgbaechif_； 其前序遍历序列为_abdgcefhi_； 其后序遍历序列为_gdbeihfca_；6.3 简答题1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。iaedbchHf图6.7 一棵二叉树igcefdba图6.8 一棵树3. 由如图6.7所示的二叉树，请画出该二叉树对应的森林。4. 已知一棵树如图6.8所示，转化为一棵二叉树，表示为_。5. 以数据集4，5，6，7，10，12，18为结点权值，画出构造Huffman树的每一步图示，计算其带
10、权路径长度为。6. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少? 最大深度：h=N-k+1,最小深度：logkN+17. 证明:一棵满k叉树上的叶子结点数n和非叶子结点数n之间满足以下关系: n=(k-1)n+16.4 算法设计题1. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。2试编写算法，对一棵二叉树,统计叶子的个数。3试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。7. 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。8. 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。