12 13 1313 13 14 1414 14 15 1515 15 16 1616 16 17 1717 17 18 1818 18 19 1919 19 20 2020 20 21 2121 21 e ee e a aa a f ff f d dd d g gg g c cc c j jj j l ll l h hh h b
bb
b 图6.6 k k k k k
一棵二叉树的顺序存储数组t k k 2 1 4 3 5 6 7 17g c e f d b a 图
6.8 一棵树 6.3 简答题 简答题简答题
简答题 1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分 别画出。
2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。 请画出该树。
3. 由如图6.7所示的二叉树，回答以下问题： （1）画出该二叉树的中序线索二叉树； （2）画出该二叉树的后序线索二叉树；
（3）画出该二叉树对应的森林。
4. 已知一棵树如图6.8所示，转化为一棵二叉树，表示为____。
5. 以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每 一步图示，计算其带权路径长度为。
6. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少? 7. 证明:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关 系:
n0=(k-1)n1+1 6.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。请画出该树。 18 E B F A C D K G H I J 图6.12 习题答案
习题答案习题答案
习题答案 6.1 1. B 2. B 3. C 4. C 5. C 6. A 7. D 8. A
11. D 2. A 13. B 14. B 15. B 16. D 17. C 18. C 19. B 20. B 21. B 22. B 23. B 24. A 25. C
6.2
1. ⑴ k1 ⑵ k2,k5,k7,k4 ⑶ 2 ⑷ 3 ⑸ 4 ⑹ k5,k6 2. 树的结点个数至少为1(不同教材规定不同)，而二叉 树的结点个数可以为0；
树中结点的最大度数没有限制，而二叉树结点的最 大度数为2；
树的结点无左、右之分，而二叉树的结点有左、右 之分；
3. 树可采用孩子-兄弟链表（二叉链表）做存储结构， 目的并利用二叉树的已有算法解决树的有关问题。 4. 如图6.9所示 5. 2 k-1
、 2 k-1 、 2 k-2+1 6. n2+1
7. 2 i-1 2[log 2
n+1]-1 2[log 2
n+1] –1
8. 只有一个结点的树；空的二叉树 9. 5；如图6.10所示
10. dgbaechif 、abdgcefhi 、gdbeihfca 、 6.3 1. 5种, 图6.11 2. 二叉树如图6.12所示。 图 6.11 树形5种
A 9. C 10. ⑺ k1 a
图6.10 树形5种 a a a a c c c c c b b b b b b e a f j c d l g h b
图6.9 19图6.13 a d h j b c 图
6.14 对应的森林 i e f a b c e d i
g 图
6.15 一棵树的孩子兄弟表3. 图6.13（右）所
6.13（左）所示；后序线索二叉树如中序线索二叉树如图示；该二叉树转换后的的森林如图6.14所示。
4. 图6.8的树转化为一棵二叉树如下，图6.15：
5. 画出构造Huffman树如图6.16所示，计算其带权路径长度为
6. 一棵含有N个结点的k叉树,可能达到的最大深度 h=N-k+1 ，最小深度各为: logkN+1。 62 37 25 19 18 13 12
。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题集(含答案)(4)在线全文阅读。
相关推荐：