数据结构试题及答案(1)(5)

10、将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。（7分） 答案：

a + b c d + + * + f h g * + e 12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分）

2 10

8 1 3 5 3 15 7 2 7 5 12 6 6 9 4 21

答案:

13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。

6 6 2 3 1 5 3 4 7 2 7 15 5 22

答案：

为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：

0 1 0 1 0 1 23 0 29 1 0 1 11 0 14 1 0 1 5 3 7 8

赫夫曼编码为：概率为0.23的字符编码为：00

23

概率为0.11的字符编码为：010

概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111 概率为0.29的字符编码为：10

概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：1111

14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。

答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图： A

B F C E G D 24

H J

这棵二叉树的后序遍历序列为：EDCBIHJGFA

15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。

16、 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少? 答案：设高度为h(空树的高度为-1)的AVL树的最少结点为Nh，则Nh = Fh+3 -1。 Fh 是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3/2*log2(n+1), 最小高度为「log2(n+1) ┐-1。

17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构试题及答案(1)(5)在线全文阅读。