数据结构-树习题

第六章 树⼀、选择题

1、⼆叉树的深度为k，则⼆叉树最多有（ C ）个结点。A. 2k B. 2k-1 C. 2k-1 D. 2k-1

2、⽤顺序存储的⽅法，将完全⼆叉树中所有结点按层逐个从左到右的顺序存放在⼀维数组R[1..N]中，若结点R[i]有右孩⼦，则其右孩⼦是（B ）。

A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i]

3、设a,b为⼀棵⼆叉树上的两个结点，在中序遍历时，a在b前⾯的条件是（ B ）。A. a在b的右⽅ B. a在b的左⽅ C. a是b的祖先 D. a是b的⼦孙

4、设⼀棵⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树先序遍历序列为（ ）。A. adbce B. decab C. debac D. abcde5、在⼀棵具有5层的满⼆叉树中结点总数为（A）。 A. 31 B. 32 C. 33 D. 16

6、由⼆叉树的前序和后序遍历序列（ B ）惟⼀确定这棵⼆叉树。A. 能 B. 不能

7、某⼆叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左⼦树中结点数⽬为（ C ）。A. 3　 B. 2 C. 4 D. 5

8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。A. 67　 B. 68 C. 69 D. 70

9、将⼀棵有100个结点的完全⼆叉树从根这⼀层开始，每⼀层上从左到右依次对结点进⾏编号，根结点的编号为1，则编号为49的结点的左孩⼦编号为（ A ）。

A. 98　 B. 99 C. 50 D. 48

10、表达式a*(b+c)-d的后缀表达式是（ B ）。A. abcd+-　 B. abc+*d- C. abc*+d- D. -+*abcd

11、对某⼆叉树进⾏先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC12、树最适合⽤来表⽰（ C ）。

A. 有序数据元素 B. ⽆序数据元素 C. 元素之间具有分⽀层次关系的数据 D. 元素之间⽆联系的数据13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ）。

A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+14、在线索⼆叉树中，t所指结点没有左⼦树的充要条件是（ ）。

A. t->left==NULL　 B. t->ltag==1 C. t->ltag==1&&t->left==NULL D. 以上都不对15、任何⼀棵⼆叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。A. 不发⽣改变　 B. 发⽣改变 C. 不能确定 D. 以上都不对

16、假定在⼀棵⼆叉树中，度为2的结点数为15，度为1的结点数为30，则叶⼦结点数为（ ）个。 A. 15 B. 16 C. 17 D. 47

17、在下列情况中，可称为⼆叉树的是（ B ）。

A. 每个结点⾄多有两棵⼦树的树　 B. 哈夫曼树

C. 每个结点⾄多有两棵⼦树的有序树 D. 每个结点只有⼀棵⼦树

18、⽤顺序存储的⽅法，将完全⼆叉树中所有结点按层逐个从左到右的顺序存放在⼀维数组R[1..n]中，若结点R[i]有左孩⼦，则其左孩⼦是（ ）。

A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i]19、下⾯说法中正确的是（ ）。

A. 度为2的树是⼆叉树 B. 度为2的有序树是⼆叉树

C. ⼦树有严格左右之分的树是⼆叉树 D. ⼦树有严格左右之分，且度不超过2的树是⼆叉树20、树的先根序列等同于与该树对应的⼆叉树的（ ）。

A. 先序序列 B. 中序序列 C. 后序序列 D. 层序序列 21、按照⼆叉树的定义，具有3个结点的⼆叉树有（ C ）种。A. 3　 B. 4 C. 5 D. 6

22、由权值为3，6，7，2，5的叶⼦结点⽣成⼀棵哈夫曼树，它的带权路径长度为（ A ）。A. 51 B. 23 C. 53 D. 74⼆、判断题

（ ）1、存在这样的⼆叉树，对它采⽤任何次序的遍历，结果相同。（ ）2、中序遍历⼀棵⼆叉排序树的结点，可得到排好序的结点序列。

（ ）3、对于任意⾮空⼆叉树，要设计其后序遍历的⾮递归算法⽽不使⽤堆栈结构，最适合的⽅法是对该⼆叉树采⽤三叉链表。（ ）4、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。（√ ）5、⼀个含有n个结点的完全⼆叉树，它的⾼度是ëlog2nû＋1。（√ ）6、完全⼆叉树的某结点若⽆左孩⼦，则它必是叶结点。三、填空题

1、具有n个结点的完全⼆叉树的深度是 ëlog2nû+1 。2、哈夫曼树是其树的带权路径长度 最⼩ 的⼆叉树。

3、在⼀棵⼆叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有n0= N2+1 。4、树内各结点度的 最⼤值 称为树的度。四、代码填空题

1、函数InOrderTraverse(Bitree bt)实现⼆叉树的中序遍历，请在空格处将算法补充完整。 void InOrderTraverse(BiTree bt){ if( ){ InOrderTraverse(bt->lchild); printf(“%c”,bt->data); ; } }

2、函数depth实现返回⼆叉树的⾼度，请在空格处将算法补充完整。 int depth(Bitree *t){ if(t==NULL) return 0; else{

hl=depth(t->lchild);

hr= depth(t->rchild) ; 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）哪个结点是根结点？（2）哪些结点是叶⼦结点？（3）哪些结点是k的祖先？

（4）哪些结点是j的兄弟？（5）树的深度是多少？。

2、假设⼀棵⼆叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该⼆叉树。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个字母设计哈夫曼编码。4、已知⼆叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出⼆叉树。5、试⽤权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79

7、已知⼀棵⼆叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出⼆叉树的形态。8、⼀份电⽂中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，完成问题：（1）设计⼀棵哈夫曼树；（画出其树结构）（2）计算其带权路径长度WPL；

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

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

10、有⼀分电⽂共使⽤5个字符;a,b,c,d,e，它们的出现频率依次为4、7、5、2、9，试构造哈夫曼树，并给出每个字符的哈夫曼编码。11、画出与下图所⽰的森林相对应的⼆叉树，并指出森林中的叶⼦结点在⼆叉树中具有什么特点。12、如下所⽰的⼆叉树，请写出先序、中序、后序遍历的序列。

六、编程题

1、编写求⼀棵⼆叉树中结点总数的算法。答案： （以先序遍历的⽅法为例）void count_preorder(Bitree *t, int *n) {

if(t!=NULL){*n++;

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