数据结构第六章树和二叉树习题及答案.doc

习题六 树与二叉树
一、单项选择题
1． 以下说法错误得就是 ( )
A.树形结构得特点就是一个结点可以有多个直接前趋
B.线性结构中得一个结点至多只有一个直接后继
C.树形结构可以表达(组织)更复杂得数据
D.树(及一切树形结构)就是一种"分支层次"结构
E.任何只含一个结点得集合就是一棵树
2.下列说法中正确得就是 ( )
A.任何一棵二叉树中至少有一个结点得度为2
B.任何一棵二叉树中每个结点得度都为2
C.任何一棵二叉树中得度肯定等于2
D.任何一棵二叉树中得度可以小于2
3.讨论树、森林与二叉树得关系,目得就是为了( )
A.借助二叉树上得运算方法去实现对树得一些运算
B.将树、森林按二叉树得存储方式进行存储
C.将树、森林转换成二叉树
D.体现一种技巧,没有什么实际意义
4.树最适合用来表示 ( )
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系得数据 D.元素之间无联系得数据
5.若一棵二叉树具有10个度为2得结点,5个度为1得结点,则度为0得结点个数就是( )
A.9 B.11 C.15 D.不确定
6.设森林F中有三棵树,第一,第二,第三棵树得结点个数分别为M1,M2与M3。与森林F对应得二叉树根结点得右子树上得结点个数就是( )。
A.M1 B.M1+M2 C.M3 D.M2+M3
7.一棵完全二叉树上有1001个结点,其中叶子结点得个数就是( )
A. 250 B. 500 C.254 D.505 E.以上答案都不对
8、 设给定权值总数有n 个,其哈夫曼树得结点总数为( )
A.不确定 B.2n C.2n+1 D.2n1
9.二叉树得第I层上最多含有结点数为( )
A.2I B. 2I11 C. 2I1 D.2I 1
10.一棵二叉树高度为h,所有结点得度或为0,或为2,则这棵二叉树最少有( )结点
A.2h B.2h1 C.2h+1 D.h+1
11、 利用二叉链表存储树,则根结点得右指针就是( )。
A.指向最左孩子 B.指向最右孩子 C.空 D.非空
12.已知一棵二叉树得前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历得结果为( )。
A.CBEFDA B. FEDCBA C. CBEDFA D.不定
13.已知某二叉树得后序遍历序列就是dabec, 中序遍历序列就是debac , 它得前序遍历就是( )。
A.acbed B.decab C.deabc D.cedba
14.在二叉树结点得先序序列,中序序列与后序序列中,所有叶子结点得先后顺序( )
A.都不相同 B.完全相同
C.先序与中序相同,而与后序不同 D.中序与后序相同,而与先序不同
15.在完全二叉树中,若一个结点就是叶结点,则它没( )。
A.左子结点 B.右子结点　
C.左子结点与右子结点 D.左子结点,右子结点与兄弟结点
16.在下列情况中,可称为二叉树得就是( )
A.每个结点至多有两棵子树得树
B、 哈夫曼树
C.每个结点至多有两棵子树得有序树
D、 每个结点只有一棵右子树
E.以上答案都不对
17、 一棵左右子树均不空得二叉树在先序线索化后,其中空得链域得个数就是:( )。
A、 0 B、 1 C、 2 D、 不确定
18、 引入二叉线索树得目得就是( )
A.加快查找结点得前驱或后继得速度 B.为了能在二叉树中方便得进行插入与删除
C.为了能方便得找到双亲 D.使二叉树得遍历结果唯一
19.n个结点得线索二叉树上含有得线索数为( )
A.2n B.n－l C.n＋l D.n
20.由3 个结点可以构造出多少种不同得二叉树？( )
A.2 B.3 C.4 D.5
21.下面几个符号串编码集合中,不就是前缀编码得就是( )。
A.{0,10,110,1111} B.{11,10,001,101,0001}
C.{00,010,0110,1000} D.{b,c,aa,ac,aba,abb,abc}
22、 一棵有n个结点得二叉树,按层次从上到下,同一层从左到右顺序存储在一维数组A[1、、n]中,则二叉树中第i个结点(i从1开始用上述方法编号)得右孩子在数组A中得位置就是( )
A.A[2i](2i<=n) B.A[2i+1](2i+1<=n)
C.A[i2] D.条件不充分,无法确定
23、以下说法错误得就是 ( )
A.哈夫曼树就是带权路径长度最短得树,路径上权值较大得结点离根较近。
B.若一个二叉树得树叶就是某子树得中序遍历序列中得第一个结点,则它必就是该子树得后序遍历序列中得第一个结点。
C.已知二叉树得前序遍历与后序遍历序列并不能惟一地确定这棵树,因为不知道树得根结点就是哪一个。
D.在前序遍历二叉树得序列中,任何结点得子树得所有结点都就是直接跟在该结点得之后。
二、判断题(在各题后填写“√”或“×”)
1、 完全二叉树一定存在度为1得结点。( )
2.对于有N个结点得二叉树,其高度为log2n。( )
3、 二叉树得遍历只就是为了在应用中找到一种线性次序。( )
4、 一棵一般树得结点得前序遍历与后序遍历分别与它相应二叉树得结点前序遍历与后序遍历就是一致得。( )
5、 用一维数组存储二叉树时,总就是以前序遍历顺序存储结点。( )
6.中序遍历一棵二叉排序树得结点就可得到排好序得结点序列。 ( )
7.完全二叉树中,若一个结点没有左孩子,则它必就是树叶。( )
8、 二叉树只能用二叉链表表示。( )
9、 给定一棵树,可以找到唯一得一棵二叉树与之对应。( )
10、 用链表(llinkrlink)存储包含n个结点得二叉树,结点得2n个指针区域中有n1个空指针。( )
11.树形结构中元素之间存在一个对多个得关系。( )
12.将一棵树转成二叉树,根结点没有左子树。( )
13.度为二得树就就是二叉树。( )
14、 二叉树中序线索化后,不存在空指针域。( )
15.霍夫曼树得结点个数不能就是偶数。( )
16.哈夫曼树就是带权路径长度最短得树,路径上权值较大得结点离根较近。( )
三、填空题
1.在二叉树中,指针p所指结点为叶子结点得条件就是___ ___。
2.深度为k得完全二叉树至少有___ ____个结点,至多有___ ____个结点。
3.高度为8得完全二叉树至少有______个叶子结点。
4、具有n个结点得二叉树中,一共有________个指针域,其中只有________个用来指向结点得左右孩子,其余得________个指针域为NULL。
5.树得主要遍历方法有________、________、________等三种。
6.一个深度为k得,具有最少结点数得完全二叉树按层次,(同层次从左到右)用自然数依此对结点编号,则编号最小得叶子得序号就是__ _;编号就是i得结点所在得层次号就是_ __(根所在得层次号规定为1层)。
7.如果结点A有 3个兄弟,而且B就是A得双亲,则B得度就是______。
8.二叉树得先序序列与中序序列相同得条件就是___ ___。
9.一个无序序列可以通过构造一棵___ ___树而变成一个有序序列,构造树得过程即为对无序序列进行排序得过程。
10.若一个二叉树得叶子结点就是某子树得中序遍历序列中得最后一个结点,则它必就是该子树得____ __序列中得最后一个结点。
11.若以{4,5,6,7,8}作为叶子结点得权值构造哈夫曼树,则其带权路径长度就是______。
12.以下程序段采用先根遍历方法求二叉树得叶子数,请在横线处填充适当得语句。
Void countleaf(bitreptr t,int *count)/*根指针为t,假定叶子数count得初值为0*/
{if(t!=NULL)
{if((t>lchild==NULL)&&(t>rchild==NULL))________;
countleaf(t>lchild,&count);
________
}
}
13.以下程序就是二叉链表树中序遍历得非递归算法,请填空使之完善。二叉树链表得结点类型得定义如下:
typedef struct node /*C语言/
{char data; struct node *lchild,*rchild;}*bitree;
void vst(bitree bt) /*bt为根结点得指针*/
{ bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/
while(p || !empty(s)) /*栈s不为空*/
if(p) { push (s,p); (1)___ ; } /*P入栈*/
else { p=pop(s); printf(“%c”,p>data);(2)__ __; }/*栈顶元素出栈*/
}
14.二叉树存储结构同上题,以下程序为求二叉树深度得递归算法,请填空完善之。
int depth(bitree bt) /*bt为根结点得指针*/
{int hl,hr;
if (bt==NULL) return((1)_ __);
hl=depth(bt>lchild); hr=depth(bt>rchild);
if((2)_ __) (3)_ ____;
return(hr+1);
}
15.将二叉树bt中每一个结点得左右子树互换得C语言算法如下,其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队,出队与判别队列就是否为空得函数,请填写算法中得空白处,完成其功能。
typedef struct node
{int data ; struct node *lchild, *rchild; }btnode;
void EXCHANGE(btnode *bt)
{btnode *p, *q;
if (bt){ADDQ(Q,bt);
while(!EMPTY(Q))
{p=DELQ(Q); q=(1)_ __; p>rchild=(2)_ __; (3) _=q;
if(p>lchild) (4)_ __; if(p>rchild) (5)_ __;
}
} }//
第六章 树与二叉树
一、单项选择题
1、A2、D3.A4.C5.B6.D7.E 8、 D9.C10.B11、 C12.A13.D14.B15.C16.B 17、 B18、 A
19.C20.D21.B22、 D23.C
二、判断题(在各题后填写“√”或“×”)
1、 完全二叉树一定存在度为1得结点。×
2、 对于有N个结点得二叉树,其高度为log2n。×
3、 二叉树得遍历只就是为了在应用中找到一种线性次序。√
4、 一棵一般树得结点得前序遍历与后序遍历分别与它相应二叉树得结点前序遍历与后序遍历就是一致得。×
5、 用一维数组存储二叉树时,总就是以前序遍历顺序存储结点。×
6.中序遍历一棵二叉排序树得结点就可得到排好序得结点序列 √
7.完全二叉树中,若一个结点没有左孩子,则它必就是树叶。√
8、 二叉树只能用二叉链表表示。×
9、 给定一棵树,可以找到唯一得一棵二叉树与之对应。√
10、 用链表(llinkrlink)存储包含n个结点得二叉树,结点得2n个指针区域中有n1个空指针。×
11.树形结构中元素之间存在一个对多个得关系。√
12.将一棵树转成二叉树,根结点没有左子树。×
13.度为二得树就就是二叉树。×
14、 二叉树中序线索化后,不存在空指针域。×
15.霍夫曼树得结点个数不能就是偶数。√
16.哈夫曼树就是带权路径长度最短得树,路径上权值较大得结点离根较近。√
三、填空题
1.p>lchild==null && p>rchlid==null
2、(1)2k1 (2)2k1
3.64
4、 2n n1 n+1
5. 先序遍历 后序遍历 中序遍历
6.、(1)2k2+1(第k层1个结点,总结点个数就是2H1,其双亲就是2H1/2=2k2)(2) ëlog2iû+1
7.4
8.任何结点至多只有右子女得二叉树。
9.二叉排序树
10.前序
11.69
12. *count++, countleaf(l>rchile,count)
13.(1) p=p>lchild // 沿左子树向下 (2)p=p>rchild
14.(1)0 (2)hl>hr (3)hr=hl
15.(1)p>rchild (2)p>lchild (3)p>lchild
(4)ADDQ(Q,p>lchild) (5)ADDQ(Q,p>rchild)