数据结构与算法分析 第五章 树和二叉树 作业讲解

单选题1

在下述结论中,正确的是(   )①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A. ①②③
B. ②③④
C. ②④
D. ①④

正确答案：D

思路：

（1）度的概念：

结点的度: 结点拥有的子树数称为结点的度。

树的度: 树的度是树内各结点度的最大值。

（2）完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号丛1至n的结点一一对应时，称之为完全二叉树。

单选题2

有关二叉树下列说法正确的是(   )
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2

正确答案：B

思路：

单选题3

在完全二叉树中，若一个结点是叶结点，则它没有(   )。
A. 左子结点
B. 右子结点
C. 左子结点和右子结点
D. 左子结点,右子结点和兄弟结点

正确答案：C

思路：

叶结点:度为0的结点称为叶子或终端结点。

单选题4

由3个结点可以构造出(   )种不同形态的二叉树。
A. 2
B. 3
C. 4
D. 5

正确答案：D

多选题5

二叉树由(    )三个基本单元组成。(多选题）
A. 左子树
B. 右子树
C. 根结点

正确答案：A;B;C

单选题6

对于一个具有n个结点的二元树，当它为一棵完全二元树时具有最小高度，当它为一棵单支树时具有最大高度。(   )
A. 正确
B. 错误

正确答案：A

单选题7

假设根结点的层数为1，具有n个结点的二叉树的最大高度是(   )。
A. n
B. n+1
C. n-1
D. 未知

正确答案：A

思路：

每层只有一个结点。

单选题8

一个具有1025个结点的二叉树的高h为(   )
A. 11
B. 10
C. 11至1025之间
D. 10至1024之间

正确答案：C

思路：

树最低时：如果当前二叉树是完全二叉树，则树高=  +1 = 11

树最高时：如果当前二叉树的每层只有一个结点，则树高=结点数= 1025

单选题9

对于有n个结点的二叉树,  其高度为(     )
A. nlog2n
B. log2n
C. 向下取整(log2n)+1
D. 不确定

正确答案：D

单选题10

一棵二叉树高度为h（h>0），所有结点的度或为0，或为2，则这棵二叉树最少有(   )结点
A. 2h
B. 2h-1
C. 2h+1
D. h+1

正确答案：B

思路：

方法1：特殊值法

假设当前树只有一个根结点，则它满足所有结点的度或为0或为2：此时高度h=1且结点数为1，则四个选项：A. 2 ×；B. 1 √；C. 3 ×；D.2 ×；所以答案选B。

方法2：满足题意的树的结构应为：

则第一层有1个结点，剩下的从第二层到第h层，共h-1层都有两个结点，所以一共有1+2×(h-1)= 2h-1，所以答案选B。

单选题11

深度为h的满m叉树的第k层有(   )个结点。(1<=k<=h)
A. m^(k-1)
B. (m^k)-1
C. (m^h)-1
D. m^(h-1)

正确答案：A

思路：

深度h是个迷惑信息。

单选题12

一棵树高为K的完全二叉树至少有(    )个结点
A. (2^k)–1
B. (2^(k-1))–1
C. 2^(k-1)
D. 2^k

正确答案：C

思路：

单选题13

如果结点A有3个兄弟，而且B是A的双亲，则B的度是(   )。
A. 3
B. 4
C. 5
D. 未知

正确答案：B

思路：

B的孩子为结点A+结点A的3个兄弟，所以B一共有4个孩子，度为4。

单选题14

具有n个结点的满二叉树，其叶子结点的个数是( )。
A. n/2
B. (n-1)/2
C. (n+1)/2
D. 未知

正确答案：C

思路：

满二叉树只有度为0或者度为2的结点，且满足n0=n2+1，又根据题意n0+n2=n, 所以n0 = (n+1)/2。

单选题15

引入二叉线索树的目的是(    )
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
D. 使二叉树的遍历结果唯一

正确答案：A

思路：

当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到，为此引人线索二叉树来保存这些在动态过程中得到的有关前驱和后继的信息。

单选题16

在二叉树中,指针p所指结点为叶子结点的条件是p->lchild==null && p->rchlid==null。(   )
A. 正确
B. 错误

正确答案：A

思路：

叶子结点没有左右孩子。

单选题17

深度为k的完全二叉树至少有(2^(k-1))个结点,至多有((2^k)-1)个结点。(   )
A. 正确
B. 错误

正确答案：A

思路：

① 至多：

② 至少：深度为k-1的满二叉树 + 第k层仅有一个结点 = (2^(k-1) -1)+1 = 2^(k-1)

单选题18

具有N个结点的二叉树,采用二叉链表存储，共有(   )个空链域。
A. N
B. N+1
C. N-1
D. 未知

正确答案：B

思路：

注意区分，题中问的是二叉树的二叉链表存储，链表中每个链域指向的是当前结点的左右孩子；而不是树的二叉链表表示法（孩子兄弟表示法），它的结点的链域指向的是第一个孩子结点和下一个兄弟结点。

一个度为0的结点产生两个空链域，度为1的结点产生一个空链域。所以树中的空链域个数= 2n0+n1 ①

又由N = n0+n1+n2 且n2 = n0-1，得到N= 2n0+n1-1, 即式①=N+1。所以答案选B

单选题19

设森林F中有三棵树，第一，第二，第三棵树总的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(     )。
A. M1
B. M1+M2
C. M3
D. M2+M3

正确答案：D

思路：

单选题20

设F是由T1，T2，T3三棵树组成的森林，与F对应的二叉树为B，已知T1，T2，T3的结点数分别为n1，n2和n3，则二叉树B的左子树中有n1-1个结点，右子树中有n2+n3个结点。(   )
A. 正确
B. 错误

正确答案：A

思路：

单选题21

设给定权值总数为n个，则其构建的哈夫曼树的结点总数为(   )
A. 不确定
B. 2n
C. 2n+1
D. 2n-1

正确答案：D

单选题22

含有n个叶子的哈夫曼树的结点总数为(   )。
A. 不确定
B. 2n
C. 2n+1
D. 2n-1

正确答案：D

思路：

单选题23

下面几个符号串的编码集合中，不是前缀编码的是(   )。
A. { 0，10，110，1111 }
B. { 11，10，001，101，0001 }
C. { 00，010，0110，1000 }
D. { b，c，aa，ac，aba，abb，abc }

正确答案：B

思路：

前缀编码无前缀。{ 11，10，001，101，0001 }

单选题24

利用二叉链表存储树，则根结点的右指针是(       )。
A. 指向最左孩子
B. 指向最右孩子
C. 空
D. 非空

正确答案：C

思路：

用二叉链表存储树时，结点的两个链域分别指向第一个孩子结点和下一个兄弟结点。而根结点没有兄弟结点，所以根结点的右指针指向为空。

单选题25

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

正确答案：B

思路：

树的后根遍历：先依次后根遍历每棵子树，然后访问根结点。如下图中，树的后根遍历序列为：BCDA

树转化成二叉树：当前结点的孩子结点成为其左孩子，兄弟结点变成其右孩子。将下图中树转为二叉树后，对二叉树进行中序遍历得到的结果为：BCDA

单选题26

在下列存储形式中，哪一个不是树的存储形式?(   )
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法

正确答案：D

思路：

（1）双亲表示法：

这种表示方法中，以一组连续的存储单元存储树的结点，每个结点除了数据域data 外，还附设一个parent 域用以指示其双亲结点的位置。

（2）孩子表示法：

由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。

（3）孩子兄弟法：

又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild 域和 nextsibling域。

单选题27

树在计算机内的表示方式有(   )。
A. 双亲链表表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 以上都是

正确答案：D

思路：

（1）双亲表示法：

这种表示方法中，以一组连续的存储单元存储树的结点，每个结点除了数据域data 外，还附设一个parent 域用以指示其双亲结点的位置。

（2）孩子表示法：

由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。

（3）孩子兄弟法：

又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild 域和 nextsibling域。

单选题28

利用树的孩子兄弟表示法存储，可以将一棵树转换为二叉树。(   ）
A. 正确
B. 错误

正确答案：A

思路：

① 树的孩子兄弟法：即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild 域和 nextsibling域。

② 二叉树的二叉链表表示法，链表中的结点的两个链域分别指向该结点的左右孩子：

③ 树转化成二叉树：当前结点的第一个孩子结点成为其左孩子，其兄弟结点变成其右孩子。

这种存储结构的优点是便于将一般的树结构转换为二叉树进行处理，利用二叉树的算法来实现对树的操作。

单选题29

先根次序周游树林正好等同于按先根次序遍历对应的二叉树；后根次序遍历树林正好等同于按中根次序遍历对应的二叉树。(   )
A. 正确
B. 错误

正确答案：A

森林转化成二叉树：

① 先根次序周游树林：对于森林中的每棵树，都先访问根结点，再以先根次序访问其子树。

② 先根次序遍历二叉树：先访问根结点，再以先根次序访问其左子树和其右子树。

③ 后根次序遍历森林：对于森林中的每棵树，都以后根次序访问其子树，再访问其根结点。

④ 中根次序遍历二叉树：先以中根次序访问左子树，再访问根结点，最后以中根次序访问右子树。

单选题30

设森林F对应的二叉树为B，F有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是(     )
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定

正确答案：A

单选题31

二叉树的第I层上最多含有结点数为(   )
A. 2^I
B. (2^(I-1)) -1
C. 2^(I-1)
D. (2^I)-1

正确答案：C

思路：

单选题32

在一棵高度为k的满二叉树中，结点总数为(     )
A. 2^(k-1)
B. 2^k
C. (2^k)-1
D. log2k+1

正确答案：C

思路：

单选题33

高度为K的二叉树最大的结点数为(   )。
A. 2^k
B. 2^(k-1)
C. (2^k)-1
D. (2^(k-1))-1

正确答案：C

思路：

要达到二叉树中结点数最多，这个二叉树就是一个满二叉树。

单选题34

若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是(   )
A. 9
B. 11
C. 15
D. 不确定

正确答案：B

思路：

n0 = n2 + 1 = 10 + 1 = 11

单选题35

具有10个叶结点的二叉树中有(   )个度为2的结点。
A. 8
B. 9
C. 10
D. ll

正确答案：B

思路：

n2 = n0 – 1 = 10 – 1 = 9

单选题36

如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为(   )。
A. 69
B. 70
C. 71
D. 未知

正确答案：A

思路：

 n0=20; n1=30; n2= n0-1 = 19；所以二叉树中总结点数=n2+n1+n0=69

单选题37

含4个度为2的结点和5个叶子结点的二叉树，可有0至多个度为1的结点。(   )
A. 正确
B. 错误

正确答案：A

思路：

单选题38

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

正确答案：D

思路：

单选题39

一棵具有 n个结点的完全二叉树的树高度(深度)是(. )
A. 向下取整(logn)+1
B. 向上取整(logn)+1
C. logn
D. logn-1

正确答案：A

思路：

单选题40

具有256个结点的完全二叉树的深度为(   )。
A. 9
B. 8
C. 10
D. 未知

正确答案：A

思路：

单选题41

将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是(   )
A. 4
B. 5
C. 6
D. 7

正确答案：C

思路：

单选题42

一个有2001个结点的完全二叉树的高度为(   )。
A. 10
B. 12
C. 11
D. 未知

正确答案：C

思路：

单选题43

设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为(N/2)(向下取整)。(   )
A. 正确
B. 错误

正确答案：A

思路：

下标值最大的叶子结点是N，这个叶子结点的父结点就是下标值最大的分支结点，序号为(N/2)(向下取整)

单选题44

当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为(   )
A. A[2i]   (2i<=n)
B. A[2i+1]   (2i+1<=n)
C. A[i/2]
D. 无法确定

正确答案：D

思路：

举例：

单选题45

已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有(   )个叶子结点。
A. 10
B. 12
C. 11
D. 未知

正确答案：B

思路：

根据题意n1=2, n2=3, n3= 4;假设总结点数为n,则

n = n0+n1+n2+n3 ①

且除根结点外，其余结点都有一个分支进入，设B为分支总数，则

n=B+1 ②

由于这些分支是由度为1,2,3的结点射出的，因此又有B=n1+2n2+3n3 = 2+2*3+3*4 = 20。则根据式②：n=B+1= 21。进一步的，根据式①可得n0 = n-n1-n2-n3 = 21-2-3-4=12，即叶子结点有12个

单选题46

设树T的度为4,其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为(   )
A. 5
B. 6
C. 7
D. 8

正确答案：D

思路：

根据题意n1=4, n2=2, n3=1，n4= 1;假设总结点数为n,则

n = n0+n1+n2+n3 ①

且除根结点外，其余结点都有一个分支进入，设B为分支总数，则

n=B+1 ②

由于这些分支是由度为1,2,3,4的结点射出的，因此又有B=n1+2n2+3n3+4n4 = 4+2×2+3×1+4×1 = 15。则根据式②：n=B+1= 16。进一步的，根据式①可得n0 = n-n1-n2-n3-n5 = 16-4-2-1-1=8，即叶子结点有8个

单选题47

已知算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )
A. -A+B*C/DE
B. -A+B*CD/E
C. -+*ABC/DE
D. -+A*BC/DE

正确答案：D

单选题48

对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A. 先序
B. 中序
C. 后序
D. 从根开始按层次遍历

正确答案：C

思路：

单选题49

已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为(  )。
A. CBEFDA
B. FEDCBA
C. CBEDFA
D. 不定

正确答案：A

单选题50

已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac，它的前序遍历是(   )。
A. acbed
B. decab
C. deabc
D. cedba

正确答案：D

单选题51

下面的说法中正确的是( )。(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变;(2)按二叉树定义,具有三个结点的二叉树的形态共有6种。
A. (1)(2)
B. (1)
C. (2)
D. (1)、(2)都错

正确答案：B

单选题52

某二叉树的前序序列和后序序列正好相反,则该二叉树一定是(  )的二叉树。
A. 空或只有一个结点
B. 任一结点无左子树
C. 高度等于其结点数
D. 任一结点无右子树

正确答案：C

前序：根左右；后续：左右根

单选题53

已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg,则该二叉树的根为a。( ）
A. 正确
B. 错误

正确答案：A