数据结构Ch6习题答案.doc

Ch6树
一、选择题：
1．下列有关哈夫曼树的论述，错误的是( C )。
A．哈夫曼树根结点的权值等于所有叶结点权值之和。
B．具有n个叶结点的哈夫曼树共有2n-1个结点。
C．哈夫曼树是一棵二叉树，因此它的结点的度可认为0，1，2。
D．哈夫曼树是带权途径长度最短的二叉树。
2．由3个结点可以构成多少棵不一样形态的二叉树( C )。
A．3 B．4 C．5 D．6

3．假如一棵二叉树结点的前序序列是A，B，C，后序序列是C，B，A，则该二叉树结点的中序序列是( D )。
A．A，B，C B．A，C，B C．B，C，A D．不能确定

4．如图所示的4棵二叉树中，( B )不是完全二叉树。

A． B． C． D．
5．二叉树按某种次序线索化后，任一结点均有指向其前趋和后继的线索，这种说法( B )
A．对的 B．错误
若结点有左子树，则令其lchild指针指示其左孩子；若结点没有左子树，则令其lchild指针指示其前驱；
若结点有右子树，则令其rchild指针指示其右孩子；若结点没有右子树，则令其rchild指针指示其后继。
6．二叉树的前序遍历序列中，任意一种结点均处在其子女结点的前面，这种说法( A )。
A．对的 B．错误
7．对一棵70个结点的完全二叉树，它有( A )个叶子结点。
A．35 B．40 C．30 D．44

8．设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为( D )。
A．10 B．11 C．12 D．不确定
n0=n2+1
9．假定根结点的层次为0，具有15个结点的二叉树最小高度为( A )。
A．3 B．4 C．5 D．6
假定根结点的层次为1，具有15个结点的二叉树最小高度为4
10．若一棵二叉树中，度为2的结点数为9，该二叉树的叶子结点的数目为( A )。
A．10 B．11 C．12 D．不确定
n0=n2+1
11．设根结点的层次为0，则高度为k的二叉树的最大结点数为(C )。
A．2k-1 B．2k C．2k+1-1 D．2k+1
若设根结点的层次为1，则这棵树的高度为k+1，高度为k+1的二叉树的最大结点数为2k+1-1
12．以知某二叉树的后序遍历序列为abdec，先序遍历序列为cedba，它的中序遍历序列为( D )。
A．debac B．acbed C．decba D．不确定

13．设高度为h的二叉树上只有度为0和度为2的结点,则此二叉树所包括的结点数至少为( B )。
A．2h B．2h-1 C．2h+1 D．h+1

14．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是( C )。
A．n在m右方 B．n是m祖先 C．n在m左方 D．n是m子孙
15．将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为49的结点的左孩子编号为( A )。
A．98 B．99 C．50 D．48
16．某二叉树的前序和后序序列恰好相反,则该二叉树一定是( B )二叉树。
A． 空或只有一种结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子
17．对于一棵满二叉树，m个树叶，n个结点，深度为h，则( C )。
A．h+m=2n B．m=h-1 C．n=2h-1 D．n=h+m
18．判断线索二叉树中某结p有左孩子的条件是( C )。
A．p!=null B．p->lchild!=null C．p->ltag=0 D．p->ltag=1
19．实现任意二叉树的后序非递归算法而不使用堆栈构造，最佳方案是二叉树采用( C )存储构造。
A．二叉链表 B．广义存储构造 C．三叉链表 D．次序存储构造
20．在一棵二叉树结点的先序遍历序列，中序遍历序列和后序遍历序列中，所有的叶子结点的先后次序( B )。
A．都不相似 B．完全相似 C．先序和中序相似，而与后序不一样 D．中序和后序相似，而与先序不一样
21．下图所示FF是森林F转换而来的二叉树，那么F 一共有( C )个叶子结点。

A．4 B．5 C．6 D．7

22．在一非空二叉树的中序遍历序列中，根结点的右边( A )。
A．只有右子树上的所有结点 B．只有右子树上的部分结点
C．只有左子树上的所有结点 D．只有左子树上的部分结点
23．设森林F中有3棵树，其第一，第二和第三棵树的结点个数分别是n1，n2和n3，则与森林F相对应的二叉树根结点的右子树上的结点个数是( D )。
A．n1 B．n1+n2 C．n3 D．n2+n3
24．假定一棵二叉树的结点数为18，则它的最小高度为(C )。
A．18 B．8 C．5 D．4
第1层 第2层 第3层 第4层 第5层
1 2 4 8 3
25．树最合合用来表达(C )。
A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联络的数据
26．如下有关数据构造的论述对的的是(C )。
A．线性表的线性存储构造优于链式存储构造
B．二叉树的第i层上有 2i-1个结点，深度为k的二叉树上有2k-1个结点。
C．二维数组是其数据元素为线性表的线性表。 D．栈的操作方式是先进先出。
二．填空题
1．有一棵树如图示，回答下面问题：
(1) 这棵树的根结点是(A)；(2)这棵树的叶子结点是(B,E,H,G)；(3)结点C的度是(2)；(4)这棵树的度是(3)；(5)这棵树的深度是(4)；(6)结点C的孩子是(E,F),子孙是(E,F,H);(7)结点F的父亲是(C)，祖先是(A,C)。

2．二叉树的每一种结点至多有(2)棵子树，且子树有(左右)之分。
3．树的结点包括一种(数据元素)及若干指向其(子树)的分支，结点拥有的子树数称为(度)，度为0的结点称为(树叶或终端结点)，度不为0的结点称为(非终端结点或分支结点)。
4．对二叉树来说，第k层上至多有(2k-1)个结点。
5．前序遍历序列为abc的不一样二叉树有(5)种不一样形态。

6．二叉树的前序遍历序列为I J KL MNO,中序遍历序列为J LK I NMO,则后序遍历序列为(LKJNOMI)。

7．一棵树转化为一棵二叉树后，二叉树没有(右)子树。
8．一棵具有n个结点的完全二叉树，它的高度是([log2n]+1)。
一棵具有n个结点的完全二叉树，它的高度是([log2n]+1)。
h-1层最终一种结点的编号2h-1-1
h层第一种结点的编号2h-1
h层最终一种结点的编号2h-1
2h-1≥n≥2h-1
n≥2h-1
h≤logn+1
h= [logn]+1
n=2k-1=>k= log2(n+1)
9．深度为k的二叉树至多有(2k-1)个结点。
10．具有n个结点的二叉树用二叉链表表达，有(n+1)个空链域。
有2n个链域
有n-1个非空链域
11．哈夫曼树是带权途径长度(最短)的二叉树。
12．具有m个叶子结点的哈夫曼树共(2m-1)个结点。
13．前序为a，b，c且后序为c，b，a的二叉树有(4)棵。

14．树和二叉树从定义上说是两种不一样的数据构造，那么将树转化为二叉树的基本目的是(运用已经有的二叉树的算法来处理树的有关问题)。
15．深度为k的完全二叉树至多有(2k-1)个结点；至少有(2k-1)个结点，若按自上而下，从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号是(2k-2+1)。

16．已知完全二叉树的第8层有8个结点，则其叶子结点数为(68)个。
第7层的叶结点总数：26-4
第8层的叶结点总数：8
17．已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点个数最多为(235)个。

18．已知二叉树有50个叶子结点，且仅有一种孩子的结点数为30，则总结点数为(129)。
设度为i的结点有ni个，共n个结点
有n0+n1+n2=n(结点总数)
0*n0+1*n1+2*n2=n-1(边数)
因此：n0=n2+1

n1=30
19．用数组A[1…n]次序存储完全二叉树的各结点，则当i ≤(n-1)/2时，结点A[i]的右孩子是结点(A[2i+1])。
20．一棵二叉树结点的前序序列为A，B，D，E，G，C，F，H，I，中序序列为D，B，G，E，A，C，H，F，I，则该二叉树结点的后序序列为(DGEBHIFCA)。

21．有m个叶子结点的哈夫曼树上的结点数是(2m-1)。
22．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1和1，则T中叶子结点的个数为(8)。
设度为i的结点有ni个
n1=4 n2=2 n3=1 n4=1
n0+n1+n2+n3+n4=n
n-1=0*n0+1*n1+2*n2+3*n3+4*n4
23．6个结点可构造出 132 种不一样形态的二叉树。
高度：6
高度：5
高度：4
高度：3
24．在一棵高度为3的四叉树中，最多具有 21 结点。
1+1*4+1*4*4
25．一棵树的广义表表达为a (b (c, d (e, f), g (h) ), i(j, k (x, y) ) )，结点f的层数为 3 。假定根结点的层数为0。

26．一棵树的广义表表达为a (b (c, d (e, f), g (h) ), i(j, k (x, y) ) )，结点k的所有祖先的结点数为 2 个。
27．假定一棵三叉树(即度为3的树)的结点个数为50，则它的最小高度为 4 。假定根结点的高度为0。
第一层：30=1个结点
第二层：1×3=31=3个结点
第三层：1×3×3=32=9个结点
第四层：1×3×3×3=33=27个结点------------前四层，共40个结点
第五层：50-40=10个结点
28．对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1 。
即求边数
29．设二叉树根的高度为1，则：高度为h的完全二叉树的不一样二叉树棵数： 2h-1 ，(即最终一层分别有1，2，…，2h-1个结点的完全二叉树)高度为h的满二叉树的不一样二叉树棵数： 1 。
三．判断题
1．(×)二叉树是一棵无序树。
2．(×)若有一种结点是二叉树中某个子树的前序遍历成果序列的最终一种结点，则它一定是该子树的中序遍历成果序列的最终一种结点。
3．(√)在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相似的遍历成果。
4．(√)在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来以便。
5．(√)二叉树是树的特殊情形。
6．(×)对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。

7．(×)对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。
8．(×)若有一种叶子结点是二叉树中某个子树的前序遍历成果序列的最终一种结点，则它一定是该子树的中序遍历成果序列的最终一种结点。
9．(√)线索化二叉树中的每个结点一般包具有5个数据组员。
10．(×)若有一种结点是二叉树中某个子树的中序遍历成果序列的最终一种结点，则它一定是该子树的前序遍历成果序列的最终一种结点。
四．其他
1．二叉树的遍历措施有哪几种，分别简诉其遍历环节。
二叉树的遍历措施有先序遍历、中序遍历、后序遍历三种。
(1)先序遍历二叉树算法是：
若二叉树为空，则空操作；
否则
访问根结点(D)；
先序遍历左子树(L)；
先序遍历右子树(R)。
(2)中序遍历二叉树算法是：
若二叉树为空，则空操作；
否则
中序遍历左子树(L)；
访问根结点(D)；
中序遍历右子树(R)。
(3)后序遍历二叉树算法是：
若二叉树为空，则空操作；
否则
后序遍历左子树(L)；
后序遍历右子树(R)；
访问根结点(D)。
2．若按中序遍历二叉树的成果为A，C，B。作出所有能得到这一遍历成果的二叉树。

3．二叉树结点数据采用次序存储构造，存储数组中，如图所示，画出该二叉树的二叉链式表达形式。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
e
a
f

d

g

c
j

h
i

b

4．已知一棵树的双亲表达如下，其中各兄弟结点是从左到右依次出现的，画出该树及对应的二叉树。

5．写出二叉树的先序，中序和后序遍历序列，并将该二叉树分解为森林。

二叉树的先序遍历序列：ABCDEFGHI
二叉树的中序遍历序列：BDCAFEHIG
二叉树的后序遍历序列：DCBFIHGEA
对应的森林：

6．以知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ，试画出这棵二叉树，并写出其后序遍历序列。

后序遍历序列为：EDCBIHJGFA
7．画以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树，并求其带权途径长度WPL。

8．设用于通讯的电文仅有8个字母构成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

9．有一棵二叉树，其中序和后序遍历序列分别为dgbaechif，gdbeihfca。画出该二叉树，对该二叉树进行先序线索化，并求该二叉树所对应的森林。

10．二叉树以二叉链表构造存储，在下列中序遍历序列算法中填上对的的语句。
Status in_order (BiTree p)
{if ( p !=NULL)
{ (1)in_order(p->lchild) ;
printf ( p->data);
(2)in_order(p->rchild) ; }
}
11．以二叉链表作为存储构造，试完毕下列程序
(1)下列函数是中序输出二叉树的各结点，读程序并在每一种空格初填写一种语句或体现式。
void printtree (BiTree BT)
{BiTnode *p;
InitStack (s ); //构造栈s
p=(1) BT ; s.top=0;
while (p || s.top!=0)
{ while ((2) p!=NULL )
{ s.elem[s.top++]=p;
(3) p=p->lchild ;}
if (s.top>0){(4)p=s.elem[--top] ;
printf (“%d”, p->data);
(5)p=p->rchild ;}
}
}
(2)所谓二叉树T1和T2是等价的，那就是说，或者T1和T2都是空的二叉树；或者T1和T2都是非空的二叉树，且T1和T2的根结点的值相似，同步T1和T2的根结点的左子树是等价的，且T1和T2的根结点的右子树也是等价的。下面给出了判断二叉树T1和T2与否等价的程序。读程序并在每一种空格初填写一种语句或体现式。
int equalbitre (BiTree t1, BiTree t2 )
{ int equal=0;
if (t1= =null &&(1) t2==null ) equal=1;
else if (t1!= null &&(2) t2!=null)
if (t1->data= =t2->data)
if (equalbitre ( t1->lchild, t2->lchild))
(3) if (equalbitre ( t1->rchild, t2->rchild))
equal=1;
return equal;
}
12．一棵用二叉链表表达的二叉树，其根指针为root，试写出求二叉树结点数目的算法。
答案一：int Size(BiTree T)
{
if(T==NULL)
return 0;
else
return(1+Size(T->lchild)+Size(T->rchild));
}
答案二：
i=0;
int in_order (BiTree p){
if ( p !=NULL)
{ in_order(p->lchild) ;
printf ( p->data);
i++;
in_order(p->rchild) ; }
return i;
}
答案三：
void printtree (BiTree BT)
{BiTnode *p;
i=0；
InitStack (s ); //构造栈s
p=(1) BT ; s.top=0;
while (p || s.top!=0)
{ while (p!=NULL )
{ s.elem[s.top++]=p;
p=p->lchild ;}
if (s.top>0){(4)p=s.elem[--top] ;
printf (“%d”, p->data);
i++；
p=p->rchild ;}
}
}

13．以二叉链表作为存储构造，试编写求二叉树高度的算法。
int hight(BTree BT)
{//h1和h2分别是以BT为根的左右子树的高度
if(BT==NULL) return 0;
else{
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
}
14. 对于下图给出的树，指出树中的根结点、叶结点和分支结点。并指出各个结点的度数和层数。

0703班15题
15. 对于体现式(a+b)*(c+d)*(e-f)，(1)画出对应的二叉树表达；(2)给出它的前缀体现式；(3)给出它的后缀体现式。

前缀体现式：**+ab+cd-ef
后缀体现式：ab+cd+*ef-*
16．已知二叉树中的结点类型用BTNode表达，被定义为:
struct BTNode { ElemType data; BTNode *lchild, *rchild; };
其中data为结点值域，lchild和rchild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。
Int DST ( BTNode *BT, ElemType x ) {
if ( BT==NULL ) return 0;
else {
if(BT->data==x) { BT = NULL; return 1; }
else {
if(DST(BT->lchild, x)) return 1;
if (DST(BT->rchild, x)) return 1;
else return 0;
}
}
}
算法功能：从一棵二叉树中删除根结点值为x的子树，若删除成功则返回1，否则返回0