《数据结构》第五章习题参考答案
- 格式：doc
- 大小：212.50 KB
- 文档页数：6
《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）
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
则有 1)1(20miinin
5、课本P246 5.5题
【解答】略
6、课本P246 5.6题
【解答】
(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；
(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；
(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。
7、课本P246 5.7题
（1）×（2）√（3）×（4）√
1
2
3
4
8、课本P246 5.8题
（1）×（2）×（3）√（4）×
9、课本P247 5.14题
【解答】略
10、课本P247 5.17题
11、课本P248 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
C6: 010
C7: 11
C8: 0001
电文总码长=4×（3+4+5+6）+3×（10+11）
+2×（25+36）
=257
A
B
C
D E F
I G
5-18答 J
H 16
5-19答 17
9 14 15
6
3 2
5-20 Huffman树 C7
C5 C6
C4 C2
C1 C3
C8
5-20 Huffman树 C7
C5 C6
C4 C2
C1 C3
C8
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();
