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

if( hl>hr ) return hl+1; else

return hr+1; } }

3、写出下面算法的功能。

Bitree *function(Bitree *bt){ Bitree *t,*t1,*t2; if(bt==NULL) t=NULL; else{

t=(Bitree *)malloc(sizeof(Bitree)); t->data=bt->data;

t1=function(bt->left); t2=function(bt->right); t->left=t2; t->right=t1; }

return(t); }

答案：交换二叉树结点左右子树的递归算法 4、写出下面算法的功能。

void function(Bitree *t){ if(p!=NULL){

function(p->lchild); function(p->rchild); printf(“%d”,p->data);

} }

答案：二叉树后序遍历递归算法 五、综合题

1、假设以有序对表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{,,,,,,,,,},请回答下列问题：

（1）哪个结点是根结点？ a

（2）哪些结点是叶子结点？ b,d,i,j,f,k,h （3）哪些结点是k的祖先？ g,c,a （4）哪些结点是j的兄弟？ i （5）树的深度是多少？ 4

2、假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。

25

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

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