数据结构试题集（含答案） 

【知识点：二叉树前序序列的隐含性质：第一个一定是二叉树的根，后面紧跟着的是其左子树的根；二叉树后序序列的隐含性质：最后一个一定是二叉树的根，它的紧前一个是其右子树的根】 答案：

3、假设用于通讯的电文仅由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这8个字母设计哈夫曼编码。

26

答案： 4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

答案：二叉树形态

ABCEDFGH

5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 答案：

301218743125116 WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。 答案：(1)树形态：

27

321367919105523 (2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79

7、已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。

ABDGJEHKILCF答案： 8、一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，完成问题：

（1）设计一棵哈夫曼树；（画出其树结构） （2）计算其带权路径长度WPL； 答案：(1)树形态：

6430341618995413 (2)带权路径长度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129

9、已知某森林的二叉树如下所示，试画出它所表示的森林。

28

ABCEDHFG ADCEGFH答案：

B

10、有一分电文共使用5个字符;a,b,c,d,e，它们的出现频率依次为4、7、5、2、9，试构造哈夫曼树，并给出每个字符的哈夫曼编码。 答案：

11、画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。

ABCDIJNEFGKLMH

29

答案：

12、如下所示的二叉树，请写出先序、中序、后序遍历的序列。

FDBEGIACHJ 答案：先序：FDBACEGIHJ

中序：ABCDEFGHIJ 后序：ACBEDHJIGF 六、编程题

1、编写求一棵二叉树中结点总数的算法。 答案： （以先序遍历的方法为例）

void count_preorder(Bitree *t, int *n) {

if(t!=NULL)

{*n++;

count_preorder(t->lchild); count_preorder(t->lchild); }

}

30