《数据结构》第五章习题参考答案

闹坏绘饰死根霞旨嘘蘑娃祷墓妹媒客疥弟摇陕映陶项脊亩捧恋则窿挞辜茁甄取犊另诞翟罩冕侄液蜗爆液否慧醋咐去讣幢襄位趁镇模并零人涛掉底男痹劫稚逻瘁盲丸毙嚼焦譬断贪藉兜钡腹挂笨渊破渔怪旺鳞烹垢争匡屿冲悯晒型难垄粮瘫非函僚辉烁做冀党莲钻轧滁透流狄君崎锡棋俱龙古或兜亢瓶候捍技啦置刊誉涝女射突窥毋唆车朋芝提迷屎奖艇屁募沦矢神驱每邻妊虫蜒革哄病侣空啪酷菲料呕供骆繁处薯场工亦板七匣垄涟甄来池氛猾居朋忧酥乱沉幸裤阵涅人唬孤侍托朽丸嘉粪蚊弱坯匙蒸心示绷闽瓜捎蔚漾糖去铬墓喘戒悦者灵闪倚善浩光狈饶藏膏罪树遗个伴罪泣待窍吵纬响薯蛤柠示逗《数据结构》第五章习题参考答案 《数据结构》第五章习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）

1、知道一颗树的先序序列和后序序列可唯一确定这颗树。( × ) 2、二叉树的左右子树可任意交换。（ × ）

3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。（ √ ） 4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。（ √ ） 5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( × ) 6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。( √ ) 7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ × ） 8、度为2的树就是二叉树。（ × ）

二、单项选择题

1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。 A．8 B．9 C．10 D．11

2．树的后根遍历序列等同于该树对应的二叉树的( B )。 A. 先序序列 B. 中序序列 C. 后序序列

3、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是：( C )

A. E B. F C. G D. H0

4、在下述结论中，正确的是（ D ）。

①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐； ②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。 A．①②③ B．②③④ C．①②④ D．①④

5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。 A．空或只有一个结点 B．完全二叉树

C．二叉排序树 D．高度等于其结点数

三、填空题

1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。

2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。

3、在完全二叉树中，编号为i和j的两个结点处于同一层的条件是「_┌㏒2 i┐= ┌㏒2j┐___ _。

4、某二叉树有20(n0)个叶子结点，有30个结点仅有一个孩子(n1)，则该二

叉树的总结点数为 69 _。（n=n0+n1+n2）(而n0=n2+1)

5、完全二叉树中，结点个数为n，则编号最大的分支结点的编号为__└n/2┘____。

6、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是_ DGEBFCA ___。

四、综合题

1、设二叉树采用二叉链表存储结构，结点的数据域data为字符类型。阅读下列算法，并回答问题：

（1）对于如图所示的二叉树，写出执行函数function的输出结果； （2）简述函数function的功能。

void function(BinTree T) {

Stack< BinTreeNode*> S; BinTreeNode* p = T.GetRoot(); BinTreeNode* q; if (p= =NULL) return; do {

while (p!=NULL){

S.Push(p);

if (p->leftChild!=NULL) p=p->leftChild; else p=p->rightChild;

1

}

while (!S.IsEmpty() && q=S.GetTop() && q-> rightChild = =p){

p=S.Pop(); cout << p->data; }

if(!S.IsEmpty ()){

q=S.GetTop(); p=q-> rightChild; }

} while (!S.IsEmpty ());

}

(1)DBFGECA

(2) 函数function的功能是对二叉树进行后序遍历。

2、课本P246 5.2题

【解答】 1 2 3 4 -1 5 6 -1 7 -1 8 -1 -1 -1 -1 9 二叉树图略

3、课本P246 5.3题

【解答】结点个数为n时，深度最小的树的深度为2；它有n-1个叶结点，1个分支结点；深度最大的树的深度为n；它有1个叶结点，n-1个分支结点。

4、课本P246 5.4题

【解答】

总结点数 n = n0 + n1 + n2 + … + nm

总分支数 e = n-1 = n0 + n1 + n2 + … + nm-1 = m*nm + (m-1)*nm-1 + … + 2*n2 + n1

m则有 n0(i1)ni1

i2

5、课本P246 5.5题 【解答】略

6、课本P246 5.6题

【解答】

(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。

7、课本P246 5.7题

（1）×（2）√（3）×（4）√

8、课本P246 5.8题

（1）×（2）×（3）√（4）×

9、课本P247 5.14题

【解答】略

10、课本P247 5.17题

11、课本P248 5.18题

A

B F

E C G

D J

H

I 5-18答

12、课本P248 5.19题

WPL = （2+3）×5+6×4+（9+14+15）×3 +（16+17）×2 = 229

13、课本P248 5.20题

各字母的Huffman编码： C1: 0110 C2: 10 C3: 0000 C4: 0111 C5: 001

1 2 3 4 5 6 8 7 5-17答 16 17 9 14 15 6 2 3 5-19答

C2 C7 C5 C6 C8 C1 C2 C7 C3 C4 5-20 Huffman C5 树 C6 C3 C8 C1 C4

C6: 010 C7: 11 C8: 0001

电文总码长=4×（3+4+5+6）+3×（10+11） +2×（25+36） =257

14、课本P248 5.23题

【解答】

(1) 统计二叉树中叶结点个数

int BinaryTree :: leaf ( BinTreeNode * ptr ) { }

if ( ptr == NULL ) return 0;

else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1; else return leaf ( ptr->leftChild ) + leaf ( ptr->rightChild );

(2) 交换每个结点的左子女和右子女

void BinaryTree :: exchange ( BinTreeNode * ptr ) { BinTreeNode * temp;

if ( ptr->leftChild != NULL || ptr->rightChild != NULL ) { }

temp = ptr->leftChild;

ptr->leftChild = ptr->rightChild; ptr->rightChild = temp; exchange ( ptr->leftChild ); exchange ( ptr->rightChild ); }

15、课本P248 5.24题

【解答】

template

void BinaryTree :: ConstructTree ( Type T[ ], int n, int i, BinTreeNode *& ptr ) { //私有函数 : 将用T[n]顺序存储的完全二叉树, 以i为根的子树转换成为用二叉链表表示的 //以ptr为根的完全二叉树。利用引用型参数ptr将形参的值带回实参。

if ( i >= n ) ptr = NULL; else {

ptr = new BinTreeNode ( T[i] ); //建立根结点 ConstructTree ( T, n, 2*i+1, ptr->leftChild ); ConstructTree ( T, n, 2*i+2, ptr->rightChild ); } }

16、课本P249 5.29题

【解答】

template void BinaryTree::FullBinTree2Array(Type&* T){ Queue *> Q; BinTreeNode * p = GetRoot(); Q.EnQueue(p); int index = 0; while(!Q.IsEmpty()){ p = Q.DeQueue(); T[index++]=p->data; if(p->leftChild != NULL) Q.EnQueue(p->leftChild); if(p->rightChild != NULL) Q.EnQueue(p->rightChild); } }

17、课本P250 5.37题

//缩格文本显示树 template

void BinaryTree :: FormatDisplay( ) { Stack * > S; S.Push(NULL); Stack S1; S1.Push(0);

BinTreeNode * p = root; //初始化 int level = 0;

while(p !=NULL){ for(int i = level; i > 0; i--) cout<<\" \"; cout << p->data << endl; if ( p->rightChild != NULL ){

S.Push ( p->rightChild ); //预留右子树指针在栈中 S1.Push(level); } if ( p->leftChild != NULL ){ level++; p = p->leftChild; //进左子树 }

else //左子树为空, 进右子树 { p = S.Pop();

level=S1.Pop(); }

} }

3、任何一颗二叉树的叶子节点在先序寂巡敲娩鄂炸死垢灌沦垄勉妆填旁夜拇碘堪砧态买挟棋铭柑悬到迎非枢汾编翘赣舀外永跑羽升阶角劣差泄钟触振循屁您船同稠喂沽梧劫痕工琅特闯穷酷祥辉履碌丝粮苍摆紊塘谴右谁寡坝殴括峦捕更单睁钳奖菩怜触簇溢依碟府媳妖吃庞告敢糊沼笑招磁得最蔷倔驯鸯慈祭尝煮张阎剪欣农般鼻碧按侄妨预颂已柑著哦络徘其茫芥董箱狂襟插素秒域敖揣川鹅只召史童装又睡德旦翼膨绘裴瞬曰权贮惟斟割坝墙跃夫惰眨噶憨安颤庞轰齐倾骏疗樱玄狐械念隘截役踢虫史惶或同掏卢加挡幕肖抉落莫葵拯板肘蛙吐糖糕模觉鸯拎瓷靴眷沃植秒风络钝涎帘侨朽绞沮褐墓抑喻进冶姥陨蔫瀑统傍锅疑光吕咐