数据结构课程课后习题集答案解析 下载本文

练习题6

1. 单项选择题

(1)树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有层次关系的数据 D.元素之间无联系的数据 答:C

(2)树是结点的有限集合,它( ① )根结点,记为T。其余的结点分成为m(m≥0)个( ② )的集合T1、T2、…、Tm,每个集合又都是树,此时结点T称为Ti的双亲结点,Ti称为T的子树(1≤i≤m)。一个结点的子树个数为该结点的( ③ )。

①:A.有0个或1个 B.有0个或多个 C.有且只有1个 D.有1个或1个以上 ②:A.互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 ③:A.权 B.维数 C.次数(或度) D.序 答:①A ②A ③C (3)二叉树( ① )。在完全的二叉树中,若一个结点没有( ② ),则它必定是叶子结点。每棵树都能唯一地转换成与它对应的二叉树,由一棵树转换成的二叉树中,一个结点N的左孩子是N在原树里对应结点的( ③ ),而N的右孩子是它在原树里对应结点的( ④ )。

①: A.是特殊的树 B.不是树的特殊形式 C.是两棵树的总称 D.有是只有二个根结点的树形结构 ②: A.左子结点 B.右子结点 C.左子结点或者没有右子结点 D.兄弟 ③~④:A.左孩子结点 B.最右子结点 C.最邻近的右兄弟 D.最邻近的左兄弟 E.最左的兄弟 F.最右的兄弟 答:①B ②A ③A ④C

(4)把一棵树转换为二叉树后,这棵二叉树的形态是( )。 A.唯一的 B.有多种 C.有多种,但根结点都没有左孩子 D.有多种,但根结点都没有右孩子 答:A

(5)假定一棵度为3的树中结点数为50,则其最小高度为( )。 A. 3 B. 4 C. 5 D. 6 答:C

(6)若一棵度为7的树有7个度为2的结点,有6个度为3的结点,有5个度为4的结点,有4个度为5的结点,有3个度为6的结点,有2个度为7的结点,该树一共有( )个叶子结点。

A. 35 B. 28 C. 77 D. 78 答:D

(7)下列叙述中,正确的是( )。

数据结构简明教程

A.二叉树就是度为2的树 B.二叉树中不存在度大于2的结点 C.二叉树是有序树 D. 二叉树中每个结点的度均为2 答:B

(8)深度为5的二叉树至多有( )个结点。 A. 16 B. 32 C.31 D.10 答:C

(9)对一个满二叉树,有m个叶子结点,n个结点,深度为h,则( )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 答:D

(10)完全二叉树中,编号为i的结点的层次是( )。 A. i B. ?log2i? C. ?log2(i+1)? D. C. ?log2i?+1 答:D

(11)一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )。 A. 250 B. 501 C. 254 D. 505 答:B

(12)一棵有124个叶结点的完全二叉树,最多有( )个结点。 A. 247 B. 248 C. 249 D. 250 答:B

(13)若唯一确定一棵二叉树,只需要知道该二叉树的( )。 A. 先序序列 B. 中序序列 C. 中序和后序序列 D. 先序和后序序列 答:C (14)一棵二叉树的先序遍历序列和其后序遍历序列正好相反,则该二叉树一定是( )。 A.空树或只有一个结点 B.哈夫曼树 C.完全二叉树 D.高度等于其结点数 答:D

(15)一棵二叉树的后序遍历序列为D、A、B、E、C,中序遍历序列为D、E、B、A、C,则先序遍历序列为( )。

A.A、C、B、E、D B.D、E、C、B、A C.D、E、A、B、C D.C、E、D、B、A 答:D

(16)在线索化二叉树中,p所指结点没有左子树的充要条件是( )。 A.p->lchild == NULL B.p->ltag==1 C.p->ltag==1且p->lchild==NULL D.以上都不对 答:B

(17)根据使用频率为5个字符设计的哈夫曼编码不可能是( )。 A. 111,110,10,01,00 B. 000,001,010,011,1 C. 100,11,10,1,0 D. 001,000,01,11,10 答:C

2. 填空题

(1)由3个结点所构成的二叉树有( )种形态。 答:5

(2)一棵深度为6的满二叉树有( ① )个分支结点和( ② )个叶子结点。 答:①31 ②32

(3)设一棵完全二叉树有700个结点,则共有( )个叶子结点。 答:350

(4)设一棵完全二叉树具有1000个结点,则此完全二叉树有( ① )个叶子结点,有( ② )个度为2的结点,有( ③ )个单分支结点。

答:①500 ②499 ③1

(5)一棵二叉树的第i(i≥1)层最多有( )个结点。 答:2i-1

(6)深度为h的完全二叉树至少有( ① )个结点,至多有( ② )个结点,若按自上而下,从左到右次序给结点编号(从1开始),则编号最小的叶子结点的编号是( ③ )。

答:① 2h-1 ② 2h-1 ③ 2h-1。

(7)对含有n个结点的二叉树进行中序递归遍历,该算法平均空间复杂度为( )。 答:O(n)

(8)用5个权值{3,2,4,5,1}构造的哈夫曼(Huffman)树的带权路径长度是( )。 答:33

3. 简答题

(1)一棵度为2的树与一棵二叉树有何区别?

答:度为2的树从形式上看与二叉树很相似,但它的子树是无序的,而二叉树是有序的,即在一般树中若某结点只有一个孩子,就无需区分其左右次序,而在二叉树中即使是一个孩子也有左右之分。另外,一棵度为2的树至少有3个结点,而一棵二叉树的结点个数可以为0。

(2)试求含有n0个叶子结点的完全二叉树的总结点数。

答:由二叉树的性质可知,n2=n0-1,在完全二叉树中,度为1的结点数n1至多为1,所以具有n0个叶子结点的完全二叉树结点数是n0+(n0-1)+1=2n0或2n0-1。

(3)某二叉树的结点数据采用顺序存储结构如下:

1 E 2 A 3 F 4 # 5 D 6 # 7 H 8 # 9 # 10 C 11 # 12 # 13 # 14 G 15 I 16 # 17 # 18 # 19 # 20 B ① 画出该二叉树;

② 写出结点值为D的双亲结点及左、右子树。 ③ 将此二叉树还原为森林。

答:① 该二叉树如图8.21所示。

数据结构简明教程

A D C B G E F H I E A C D F G H I

B

图8.21 一棵二叉树 图8.2 二叉树还原成的森林

② 结点值为D的结点的双亲结点为结点值为A的结点,其左子树为以C为根结点的子树,其右子树为空。

③ 由此二叉树还原成的森林如图8.2所示。

(4)证明完全二叉树的每棵子树也都是完全二叉树。

证明:让T是一棵完全二叉树,S是它的一棵子树。由子树定义可知,S是由T中某个结点及其所有子孙构成的。由于T是完全二叉树,T的所有叶子结点都在两个相邻的层次上,因此,S的所有叶子结点都在两个相邻的层次上。类似的,如果在S中存在不位于底层上结点层,那么,该层也不位于T的底层上,它必须在T中所有底层叶子结点的右边,因此它也必须在S中所有底层叶子结点的右边。从而得到S是完全二叉树。

(5)一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来。试求出空格处的内容,并画出该二叉树。

先序序列: B F ICEH G 中序序列:D KFIA EJC 后序序列: K FBHJ G A

答:由这些显示部分推出二叉树如图8.3所示。则先序序列为ABDFKICEHJG;中序序列为DBKFIAHEJCG;后序序列为DKIFBHJEGCA。

B D K F I A C G E H J 图8.3 一棵二叉树

(6)如果一棵哈夫曼树T有n0个叶子结点,那么,树T有多少个结点?要求给出求解过程。

答:一棵哈夫曼树中只有度为2和0的结点,没有度为1的结点,由非空二叉树的性质1可知,n0=n2+1,即n2=n0-1,则总结点数n=n0+n2=2n0-1。

4. 算法设计题

(1)已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计一个算法求出离下标分别