[考研类试卷]树与二叉树模拟试卷1及答案与解析.doc

1、树与二叉树模拟试卷 1 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 树最适合用来表示（ ）的数据。（A）有序（B）无序（C）任意元素之间具有多种联系（D）元素之间具有分支层次关系2 树中所有结点的度等于所有结点数加（ ）。（A）0（B） 1（C） -1（D）23 树的路径长度是从树根到每一结点的路径长度的（ ）。（A）总和（B）最小值（C）最大值（D）平均值4 度为 4、高度为 h 的树，则（ ）。（A）至少有 h+3 个结点（B）至多有 4h-1 个结点（C）至多有 4h 个结点（D）至少有 h+4 个结点5 对于一棵具有 n 个结点、度为 4 的树来说，（ ）

2、。（A）树的高度至多是 n-3（B）树的高度至多是 n-4（C）第 i 层上至多有 4(i-1)个结点（D）至少在某一层上正好有 4 个结点6 假定一棵度为 3 的树中结点数为 50，则其最小高度为（ ）。（A）3（B） 4（C） 5（D）67 在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点， 10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是（ ）。（A）41（B） 82（C） 113（D）1228 下列关于二叉树的说法中，正确的是（ ）。（A）度为 2 的有序树就是二叉树（B）含有 N 个结点的二叉树其高度为log 2N+1（

3、C）在完全二叉树中，若一个结点没有左孩子，则它必是叶结点（D）在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同9 假设一棵二叉树的结点个数为 50，则它的最小高度是（ ）。（A）4（B） 5（C） 6（D）710 以下说法中，正确的是（ ）。（A）在完全二叉树中，叶子结点的双亲的左兄弟 (如果存在)一定不是叶子结点（B）任何一棵二叉树，叶子结点个数为度为 2 的结点数减 1，即 N0=N2-l（C）完全二叉树不适合顺序存储结构，只有满二叉树适合顺序存储结构（D）结点按完全二叉树层序编号的二叉树中，第 i 个结点的左孩子的编号为 2i11 具有 10

4、个叶子结点的二叉树中有（ ）个度为 2 的结点。（A）8（B） 9（C） 10（D）1112 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二树中所包含的结点数至少为（ ）。（A）h（B） 2h-1（C） 2h+1D。h+113 一个具有 1025 个结点的二叉树的高 h 为（ ）。（A）11（B） 10（C） 111025（D）10102414 设二叉树只有度为 0 和 2 的结点，其结点个数为 15，则该二叉树的最大深度为（ ）。（A）4（B） 5（C） 8（D）915 高度为 h 的完全二叉树最少有（ ）个结点。（A）2 h（B） 2h+1（C） 2h-1（D）2 h-

5、116 已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则该完全二叉树的结点个数最多是（ ）。（A）39（B） 52（C） 111（D）11917 已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则完全二叉树的结点个数最少是（ ）。（A）39（B） 52（C） 11l（D）11918 一棵完全二叉树上有 1001 个结点，其中叶结点的个数是（ ）。（A）250（B） 500（C） 254（D）50119 若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点，则该二叉树共有（ ）个叶子结点。（A）17（B） 18（C） 19（D）2020 若一棵二

6、叉树有 126 个结点，在第 7 层(根结点在第 l 层)至多有（ ）个结点。（A）32（B） 64（C） 63（D）不存在第 7 层21 一棵有 124 个叶子结点的完全二叉树，最多有（ ）个结点。（A）247（B） 248（C） 249（D）25022 在一棵完全二叉树中，其根的序号为 1，（ ）可判定序号为 P 和 q 的两个结点是否在同一层。（A）log 2p3=log2q（B） log2p=log2q（C） log2p+1=log2q（D）log 2p=log2q+123 一棵有 n 个结点的二叉树采用二叉链存储结点，其中空指针数为（ ）。（A）n（B） n+1（C） n-1（D）2

7、n24 若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是（ ）。（A）257（B） 258（C） 384（D）38525 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）次序的遍历实现编号。（A）先序遍历（B）中序遍历（C）后序遍历（D）层次遍历26 在任何一棵二叉树中，如果结点 a 有左孩子 b、右孩子 c，则在结点的先序序列、中序序列、后序序列中，（ ）。（A）结点 b 一定在结点 a 的前面（B）结点 a 一定在结点 c 的前面（C）结点 b 一定在结点 c 的前面（D）

8、结点 a 一定在结点 b 的前面27 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。（A）所有的结点均无左孩子（B）所有的结点均无右孩子（C）只有一个叶结点（D）是任意一棵二叉树28 设 n、m 为一棵二叉树上的两个结点，在中序遍历时， n 在 m 前的条件是（ ）。（A）n 在 m 右方（B） n 是 m 祖先（C） n 在 m 左方（D）n 是 m 子孙29 前序为 A、B、C ，后续为 C、B 、A 的二叉树共有 r)。（A）1 棵（B） 2 棵（C） 3 棵（D）4 棵30 设结点 x 和 Y 是二叉树中任意的两个结点。在该二叉树的先序遍历序列中 x

9、在Y 之前，而在其后序遍历序列中 X 在 Y 之后，则 X 和 Y 的关系是（ ）。（A）X 是 Y 的左兄弟（B） X 是 Y 的右兄弟（C） X 是 Y 的祖先（D）X 是 Y 的后裔31 如果二叉树中结点的先序序列是a.b，中序序列是ba ，则（ ）。（A）结点 a 和结点 b 分别在某结点的左子树和右子树中（B）结点 b 在结点 a 的右子树中（C）结点 b 在结点 a 的左子树中（D）结点 a 和结点 b 分别在某结点的两棵非空子树中32 给定二叉树如图所示。设 N 代表二叉树的根， L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3175624，则其遍历方式是

10、（ ）。（A）LRN（B） NRL（C） RLN（D）RNL33 若一棵二叉树的前序遍历序列和后序遍历序列分别为 1，2，3，4 和4，3，2，1，则该二叉树的中序遍历序列不会是（ ）。（A）1，2，3，4（B） 2，3，4，1（C） 3，2，4，1（D）4，3，2，134 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。（A）前序（B）中序（C）后序（D）按层次35 一棵二叉树的前序遍历序列为 1234567，它的中序遍历序列可能是（ ）。（A）3124567（B） 1234567（C） 4135627（D）143657236 下列序列中，不能唯

11、一地确定一棵二叉树的是（ ）。（A）层次序列和中序序列（B）先序序列和中序序列（C）后序序列和中序序列（D）先序序列和后序序列37 已知一棵二叉树的先序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为（ ）。（A）CBEFDA（B） FEDCBA（C） CBEDFA（D）不确定38 已知一棵二叉树的后序序列为 DABEC，中序序列为 DEBAC，则先序序列为（ ）。（A）ACBED（B） DECAB（C） DEABC（D）CEDBA39 已知一棵二叉树的层次序列为 ABCDEF，中序序列为 BADCFE，则先序遍历序列为（ ）。（A）ACBEDF（B） ABCDEF（

12、C） BDFECA（D）FCEDBA40 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）。（A）都不相同（B）完全相同（C）先序和中序相同，而与后序不同（D）中序和后序相同，而与先序不同41 引入线索二叉树的目的是（ ）。（A）加快查找结点的前驱或后继结点的速度（B）为了能在二叉树中方便插入和删除（C）为了能方便找到双亲（D）使二叉树的遍历结果唯一42 线索二叉树是一种（ ）结构。（A）逻辑（B）逻辑和存储（C）物（D）线性43 判断线索二叉树中*P 结点有右孩子结点的条件是（ ）。（A）p!=NULL（B） p-rehild!=NULL（C） p-rtag=0（D

13、）p-rtag=l树与二叉树模拟试卷 1 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 D【试题解析】 树是一种分层结构，它特别适合组织那些具有分层的数据。【知识模块】 树与二叉树2 【正确答案】 C【试题解析】 除根结点外，其他每个结点都是某个结点的孩子结点。【知识模块】 树与二叉树3 【正确答案】 A【试题解析】 树的路径长度是所有路径长度的总和，树根到每一结点的最大值应该是树高减 l。注意与 Humnan 树的带权路径长度相区别。【知识模块】 树与二叉树4 【正确答案】 A【知识模块】 树与二叉树5 【正确答案】 A【知识模块】 树与二叉树6 【正

14、确答案】 C【知识模块】 树与二叉树7 【正确答案】 B【知识模块】 树与二叉树8 【正确答案】 C【试题解析】 二叉树是有序树，但是度为 2 的有序树却不是二叉树，A 错；答案B 仅当是完全二叉树时有意义，对于任意一棵二叉树高度可能为log 2N+1N；在二叉排序树上删除结点时可能会调整部分结点的位置，而插入时一定是插在叶结点的位置，故先删除再插入，其结果可能不再一样了，D 错。根据完全二叉树的定义，答案 C 正确。【知识模块】 树与二叉树9 【正确答案】 C【试题解析】 在构成一棵完全二叉树时高度最小，h=log 2N+1=log250+1=6。【知识模块】 树与二叉树10 【正确答案】

15、A【试题解析】 双亲左兄弟的孩子一定在其前面(且一定存在)，故双亲的左兄弟(如果存在)一定不是叶结点，A 正确。N 0 应该等于 N2+1，B 错误。完全二叉树可以采用顺序存储结构，C 错误。因为左孩子不一定存在， D 错误。【知识模块】 树与二叉树11 【正确答案】 B【试题解析】 由性质 N0=N2+1，即 N2=N0-1=10-1=9。【知识模块】 树与二叉树12 【正确答案】 B【知识模块】 树与二叉树13 【正确答案】 C【试题解析】 当二叉树为单侧树时具有最大高度，即每层上只有一个结点，则最大高度为 1025。而当树为完全二叉树时，其高度最小，则最小高度为log 2N+1=11。【

16、知识模块】 树与二叉树14 【正确答案】 C【知识模块】 树与二叉树15 【正确答案】 C【试题解析】 高度为 h 的完全二叉树中，第 1 层第 1rl 层构成一个高度为 h 一1 的满二叉树，结点个数为 2h-1-1。第 h 层至少有一个结点，所以最少的结点个数=(2h-1-1)+1=2h-1。【知识模块】 树与二叉树16 【正确答案】 C【试题解析】 完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7 时结点更多。若第 6 层上有 8个叶结点，则前 6

17、层为满二叉树，而第 7 层缺失了 82=16 个叶结点，故完全二叉树的结点个数最多为 2h7-1-16=111 个结点。【知识模块】 树与二叉树17 【正确答案】 A【试题解析】 第 6 层有叶结点则说明完全二叉树的高度可能为 6 或 7，显然树高为6 时结点最少。若第 6 层上有 8 个叶结点，则前 5 层为满二叉树，故完全二叉树的结点个数最少为 25-1+8=39 个结点。【知识模块】 树与二叉树18 【正确答案】 D【试题解析】 由完全二叉树的性质，最后一个分支结点的序号为10012=500 ，故叶子结点个数为 501。另解 n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-

18、1，因为 n=1001，而在完全二叉树中，n 1 只能取 0 或者 1。当 n1=1 时，n 为小数，不符合题意。所以 n1=0，故 n=501。【知识模块】 树与二叉树19 【正确答案】 A【试题解析】 第 5 层共有结点 24=16 个。第 6 层最左边有 3 个叶子结点，对应第5 层最左边两个结点，所以，第 5 层右边有 16-2=14 个叶子结点，加上第 6 层 3 个，共 17 个叶子结点。【知识模块】 树与二叉树20 【正确答案】 C【试题解析】 要使二叉树在第 7 层达到最多的结点个数，其上面的 6 层必须是一个满二叉树，深度为 6 的满二叉树有 63(26-1)个结点，故第 7

19、 层最多有 126-63=63个结点。【知识模块】 树与二叉树21 【正确答案】 B【试题解析】 由 N0=N2+1 可知 N2=123；N=N 0+N1+N2+1=247+N1，其最大值为248(当 N1=1 时结点最多)。注意，由完全二叉树结点总数的奇偶性可以确定 N1 的值，但不能根据 N0 来确定的 N1 值。【知识模块】 树与二叉树22 【正确答案】 A【试题解析】 由完全二叉树的性质，在一棵完全二叉树第 h(h1)层上的结点 p 和q，它们的序号范围应是 2h-1p，q2 h-1，因此有log 2p=log2q成立。【知识模块】 树与二叉树23 【正确答案】 B【试题解析】 非空指

20、针数=度之和=11-1，空指针数=2结点总数一非空指针数=2n-(n-1)=n+1。【知识模块】 树与二叉树24 【正确答案】 C【试题解析】 求解过程与第 11 题类似。由完全二叉树的性质，最后一个分支结点的序号为7682=384，故叶子结点的个数为 768-384=384。【知识模块】 树与二叉树25 【正确答案】 C【试题解析】 对每个顶点从 1 开始按序编号，要求结点编号大于其左、右孩子编号，并且左孩子编号小于右孩子编号。编号越大说明遍历顺序越靠后，因此，三者遍历顺序为先左子树再右子树后根结点，4 个选项中仅后序遍历满足要求。【知识模块】 树与二叉树26 【正确答案】 C【试题解析】

21、这 3 种遍历方式中无论哪种遍历方式，都是先遍历左子树，再遍历右子树，所以结点 b 一定在结点 c 的前面访问。【知识模块】 树与二叉树27 【正确答案】 C【试题解析】 非空树的先序和后序相反，即“根左右”与“左右根”顺序相反，因此，树只有根结点，或者根结点只有左子树或右子树，依此类推，其子树有同样的性质。因此，树中所有非叶结点的度均为 1，即二叉树仅有一个叶结点。【知识模块】 树与二叉树28 【正确答案】 C【知识模块】 树与二叉树29 【正确答案】 D【知识模块】 树与二叉树30 【正确答案】 C【知识模块】 树与二叉树31 【正确答案】 C【知识模块】 树与二叉树32 【正确答案】 D

22、【试题解析】 分析遍历后的结点序列，可以看出根结点是在中间被访问的，而且右子树结点在左子树之前，则遍历的方法是 RNL。本题考查的遍历方法并不是二叉树遍历的 3 种基本遍历方法，对于考生而言，重要的是掌握遍历的思想。【知识模块】 树与二叉树33 【正确答案】 C【试题解析】 前序序列为 LRN，后序序列为 NLR，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时有左右孩子，即二叉树的高度为 4.1 为根结点，由于根结点只能有左孩子(或右孩子)，因此，在中序序列中，1 或在序列首或在序列尾，ABCD 皆满足要求。仅考虑以 1 的孩子结点 2 为根结点的子树，它也只能有左孩子(或右孩子)

23、，因此，在中序序列中，2 或在序列首或序列尾，ABD 皆满足要求，故选 C。【知识模块】 树与二叉树34 【正确答案】 C【试题解析】 要交换分支结点的左、右子树，应该最后访问分支结点。应采用后序遍历。【知识模块】 树与二叉树35 【正确答案】 B【试题解析】 由题可得 1 为根结点，并且 2 为 1 的孩子结点。对于 A 选项，3 应为 1 的左孩子，前序遍历序列应为 13，不符。对于 B 选项，当 2 为 1 的右孩子，3 为 2 的右孩子时满足题目要求。对于 C 选项，类似 A 选项，前序遍历序列应该为 14。对于 D 选项，若 1 为中序第一个字母，则所有结点在 1 的右子树中，右子树

24、根结点为 2，而 34 在 2 的左子树中，567 在 2 右子树中才可满足前序序列，与中序遍历序列不符。【知识模块】 树与二叉树36 【正确答案】 D【知识模块】 树与二叉树37 【正确答案】 A【试题解析】 对于这种遍历序列问题，先根据遍历的性质排除若干项，若还无法确定答案，再根据遍历结果得到二叉树，找到对应遍历序列。如本题中，已知先序和中序遍历结果，可知本树根结点为 A，左子树有 C 和 B，其余为右子树，则后序遍历结果中，A 一定在最后，并且 C 和 B 一定在前面，排除答案 B 和 D。又因先序中有 DEF，中序中有 EDF，则 D 为这个子树的根，所以 D 在后序中排在 EF之后，

25、故答案为 A。【知识模块】 树与二叉树38 【正确答案】 D【知识模块】 树与二叉树39 【正确答案】 B【知识模块】 树与二叉树40 【正确答案】 B【试题解析】 由于左子树的访问始终在右子树之前，所以不管采用何种遍历方式，所有叶结点被访问的前后顺序是不变的。【知识模块】 树与二叉树41 【正确答案】 A【试题解析】 线索是前驱结点和后继结点的指针，引入线索的目的是加快对二叉树的遍历。【知识模块】 树与二叉树42 【正确答案】 C【试题解析】 二叉树是一种逻辑结构，但线索二叉树是加上线索后的链表结构，也就是说，它是二叉树在计算机内部的一种存储结构，所以是一种物理结构。【知识模块】 树与二叉树43 【正确答案】 C【试题解析】 线索二叉树中用 ltagnag 标识结点的左右指针域是否为线索，当其值为 0 时，则对应指针域为线索，其值为 1 时，则为左右孩子。【知识模块】 树与二叉树