数据结构考试题库含答案(8)

（3）对于数组，除了顺序存储外，还有没有其他存储方式？没有填无，若有，请说明。 有，链式存储，如下图所示（1个得分点）

第六章 树和二叉树

1. 有一树，如下图所示： （简单）

请回答以下问题：

（1）树的叶子结点及其度。 （2）非终端结点及其度。 （3）树的深度。 答： （1）、叶子结点有：D 、E、F、G，它们的度都为零。（2分） （2）、非终端结点有：A 度为3，B 度为2，C 度为1。（2分） （3）、树的深度为3。（1分）

2. 请回答：树与二叉树有什么区别？（中等）

答：区别有两点：

(1)二叉树的一个结点至多有两个子树，树则不然。（2.5分） (2)二叉树一个结点的子树有左右之分，而树的子树没有次序。（2.5分）

3. 有一棵具有n个结点的满二叉树。请问：该满二叉树的叶子结点数目是多少，

并写出分析推理过程。（中等）

答：(n+1)/2。（2分）

分析过程：满二叉树中只有度为2和度为0的结点，故设叶子结点数目为：n0 ，度为2 结点数目为：n2 。又由于 n0= n2+1，n= n2+n0 ，所以可得出：n0=(n+1)/2 。（3分）

4. 有一棵二叉树，如下图所示：（简单）请问答以下问题：

（1）、用先序遍历法遍历该二叉树，则遍历结果是什么？

（2）、用中序遍历法遍历该二叉树，则遍历结果是什么？ （3）、用后序遍历法遍历该二叉树，则遍历结果是什么？ 答：（1）、A B D C E F

（2）、D B A E C F （3）、D B E F C A (错一个扣1.5分)

5. 请问如下二叉树，如果采用前序\\中序\\后序遍历结果是什么？（中等）

前序:ABDECF;中序:DBEAFC;后序:DEBFCA;(错一个扣1.5分)

6. 有如下一颗树

其前序\\中序\\后序遍历结果是什么? (中等) 其前序遍历结果是：A B D G C E F

其中序遍历结果是：D G B A E C F

其后序遍历结果是：G D B E F C A (错一个扣1.5分)

7. 假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母

在电文中出现概率为5％、25％、4％、7％、9％、12％、30％、8％。现在把字符出现概率扩大100倍后，作为这8个字母对应的权值（5，25，4，7，9，12，30，8）。以这些权值构成的霍夫曼树，如下图所示：

请问答以下问题：（中等） （1）、参考霍夫曼树，给字符A、B、C、D、E、F、G、H进行编码。（写出这8个字 符的霍夫曼编码）

（2）、如果发送的电文信息为“HECDB”，那么，发送的数据是什么。（或者说发送的编码序列是什么）

答：（1）、A:0011，B:01，C:0010， D:1010，E:000， F:100，G:11，H:1011 （3分）

（2）、1011 000 0010 1010 01 （2分）

8. 请简述满二叉树、完全二叉树的联系。

答：（1）、它们都是特殊的二叉树，遵循着二叉树的性质。 （2.5分） （2）、满二叉树是指每一层结点数都达到了最大值，所有叶子结点均在最大层上；而完全二叉树是遵循着满二叉树结点编号序列规律的一种树。（2.5分）

9. 如下是一颗树.

请问度为2的节点有哪些?度为3的节点有哪些?这颗树的度为多少?树的深度是几? (中等)

答:度为2的节点有B,E;（1.5分） 度为3的节点有A, D;（1.5分） 这颗树的度为4,（1分） 树的深度是4.（1分）

10. 请画出深度为4的满二叉树(较难)

11. 请画出深度为4的完全二叉树(较难)

12. 给定一组权值{6，2，3，9，6} 根据哈夫曼算法构造哈夫曼树. (难)

1) 将6、2、3、9、6看成是有5 棵树的森林(每棵树仅有一个结点)；

2) 在森林中选出两个根结点的权值最小的2，3树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和5；从森林中删除选取的两棵树，并将新树加入森林；

3) 在森林中选出两个根结点的权值最小的5，6树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和11；从森林中删除选取的两棵树，并将新树加入森林；

4）在森林中选出两个根结点的权值最小的6，9树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和15；从森林中删除选取的两棵树，并将新树加入森林；

5）在森林中选出两个根结点的权值最小的11，15树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和26；从森林中删除选取的两棵树，并将新树加入森林；