1、树模拟试卷 1 及答案与解析一、单项选择题1 树是结点的有限集合，一棵树中有( )根结点。（A）有 0 个或 1 个（B）有 0 个或多个（C）有且只有一个（D）有 1 个或 1 个以上2 已知一棵二叉树，第 m 层上最多含有结点数为( )。（A）2m（B） 2m-1-1（C） 2m-1（D）2 m-13 把树的根结点的层数定义为 1，其他结点的层数等于其父结点所在层数加上 1。设 T 是一棵二叉树，K i 和 Kj 是 T 中子结点数小于 2 的结点中的任意两个，它们所在的层数分别为 Ki 和 Kj，当关系式 Ki-Kj1一定成立时，则称 T 为一棵( )。（A）满二叉树（B）二叉查找树（C
2、）平衡二叉树（D）完全二叉树4 对于非空满 k 叉树，其分支结点数目为 rt，则其叶结点数目为 ( )。（A）krt+1（B） (k+1)rt+1（C） (k-1)rt+1（D）以上都不对5 完全二叉树的叶结点没有( )。（A）左孩子结点（B）右孩子结点（C）左孩子结点、右孩子结点（D）左孩子结点、右孩子结点、右兄弟结点6 线索二叉树是一种( ) 结构。（A）逻辑（B）物理（C）线性（D）树形7 在下列存储形式中，不属于树的存储形式的是( )。（A）双亲表示法（B）孩子链表表示法（C）孩子兄弟表示法（D）顺序存储表示法8 深度为 h 的满 m 叉树第后层至多有( )个结点(1kh)。（A）m
3、k-1（B） mk 一 1（C） mh-1（D）m h 一 l9 已知一棵完全二叉树中共有 626 个结点，叶结点的个数应为( )。（A）311（B） 312（C） 313（D）31410 含 9 个叶子结点的三叉树中至少有( )个非叶子结点。（A）2（B） 3（C） 4（D）611 含 10 个叶子结点的 3 阶叉树中至多有( )个非叶子结点。（A）9（B） 6（C） 5（D）712 以下叙述不正确的是( )。（A）后序线索二叉树是不完善的，要对它进行遍历，不需使用栈（B）任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈（C）任何一棵二叉树都可以不用栈实现先序线索树的先序遍历（D）任何一
4、棵二叉树都可以不用栈实现中序线索树的中序遍历13 某二叉树中序序列为 A，B，C，D，E，F，G，后序序列为B，D，C ，A，F ，G，E，则前序序列是( )。（A）B，A，F ，G，E ，D，C（B） E，A，B，C ，D， G，F（C） E，A，C，B ，D， G，F（D）B，C ， D，A，F ，G，E14 若一棵二叉树中有 24 个叶结点，有 28 个仅有一个孩子的结点，则该二叉树中总共有( ) 个结点。（A）48（B） 69（C） 75（D）7815 具有 11 个叶结点的二叉树中有( )个度为 2 的结点。（A）8（B） 9（C） 10（D）1116 已知一棵二叉树，共有 n 个结
5、点，那么此二叉树的高度为( )。（A）nlog 2n（B） 1og2n（C） log2n+1（D）不确定17 已知一个二叉树有 513 个结点，那么由此推断二叉树的高 h 为( )。（A）9（B） 10（C） 9513（D）1051318 一棵有 n 个结点的完全二叉树度为 2 的结点数共有( )个。（A）n2（B） n（C） (n 一 1)2（D）(n+1) 219 一棵二叉树如下图所示，其中序遍历序列为( )。 （A）abdgcefh（B） dgbaechf（C） gdbehfca（D）abcdefgh20 在一棵树中，度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1
6、的结点数为 2 个，则度为 0 的结点数为( )个。（A）4（B） 5（C） 6（D）721 深度为 5 的二叉树其结点数最多为( )。（A）16（B） 30（C） 31（D）3222 n 个结点的线索二叉树中，线索的数目为( )。（A）n 一 1（B） n+1（C） n（D）2n23 在二叉树的先序序列、中序序列和后序序列中，所有的叶子结点的先后顺序( )。（A）都不相同（B）完全相同（C）先序和中序相同而与后序不同（D）中序和后序相同而与先序不同24 某二叉树中序序列为 A，B，C，D，E，F，G，后序序列为B，D，C ，A，F ，G，E，则该二叉树对应的森林包括( )棵树。（A）1（B）
7、 2（C） 3（D）425 引入线索二叉树的目的是( )。（A）加快查找结点的前驱或者后继的速度（B）为了能在二叉树中方便地进行插入和删除（C）为了方便地查找到双亲（D）使二叉树的遍历结果唯一26 若二叉树的前序序列为 DABCEFG，中序序列为 BACDFGE，则其层次序列为( )。（A）BCAGFED（B） DAEBCFG（C） ABCDEFG（D）BCAEFGD27 前序遍历和后序遍历结果相同的二叉树为( )。（A）只有根结点的二叉树（B）根结点无左孩子的二叉树（C）根结点无右孩子的二叉树（D）所有结点只有左子树的二叉树28 若森林共有 n 个结点和 b 条边(bn)，则该森林中有( )
8、棵树。（A）b（B） n（C） nb（D）n+b29 设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 P，P 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是 ( )。（A）mn（B） mn 一 1（C） n+1（D）条件不足，无法确定30 设森林 F 中有三棵树，第一、第二、第三棵树的结点个数分别为 M1，M 2 和M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是( )。（A）M 1（B） M1+M2（C） M3（D）M 2+M331 将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是
9、( )。父子关系 兄弟关系 u 的父结点与 v 的父结点是兄弟关系（A）只有（B） 和（C） 和（D）、和32 在由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5。当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为( )。（A）20（B） 29（C） 30（D）3533 假设存在一棵哈夫曼树 T，它具有 m 个叶结点，则该树的结点总数为( )。（A）2m（B） m+1（C） 2m-1（D）不能唯一34 高度为 h 的 AVL 树上的最少结点个数是( )个，最多结点个数是( )。（A）2 h 一 1，2 (h-2)+2(h-3)一 1（B）
10、 2h 一 1，2 (h-2)+2(h-3)+1（C） 2(h-2)+2(h-3)+12 h 一 1（D）2 (h-2)+2(h-3)一 1，2 h 一 135 下列二叉排序树中，满足平衡二叉树定义的是( )。36 在下列所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树，在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是( )。 （A）13，48（B） 24，48（C） 24，53（D）24，9037 n(n2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( )。（A）该树一定是一棵完全二叉树（B）树中一定没有度为 1 的结点（C）树中两个权值
11、最小的结点一定是兄弟结点（D）树中任一非叶结点的权值一定不小于下一任一结点的权值二、综合题38 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构?【北京科技大学1998 一、1(3 分) 】【同济大学 1998】39 对于一个数据结构，一般包括哪三个方面的讨论?【北京科技大学 1999 一、1(2分)】40 当你为解决某一问题而选择数据结构时，应从哪些方面考虑?【西安电子科技大学 2000】41 若将数据结构定义为一个二元组(D，R)，说明符号 D、R 应分别表示什么?【北京科技大学 2001 一、1(2 分)】42 阅读下面程序，根据输入写出输出结果：#include“iostream
12、h”void swap(intx， intimi;change(m，0，n 一 1)；for(i=0；in；i+)coutmi”；coutendl；输入：101 2 3 4 5 6 7 8 9 10输出：【北京邮电大学 2006 五、1(10 分)】43 该二叉平衡树的高度是多少44 其根结点是谁?45 左子树中的数据是什么?46 右子树中的数据是什么?47 有 5 个字符，根据其使用频率，设计对应的哈夫曼编码，以下哪些是可能的哈夫曼编码?(1)000，001 ，010，011，1(2)0000，0001 ，001，01，1(3)000，001 ，01，10，11(4)00，100， 101，
13、110，11147 按字典序依次插入以下关键词：RAT OX TIGER RABBIT DRAGON SNAKE HORSE GOAT MON KEY ROOSTER DOG PIG 组成 AVL 树。48 不考虑 AVL 树对高度的平衡，将此树看作半伸展树，画出查找一次 PIG 后此半伸展树的形态。49 画出这棵 AVL 树。50 已知长度为 12 的线性表(Nov， Dec， Jul，Feb，Oct，Sept，Aug，Apr，May，Jun，Jan，Mar)，请按照表中各数据元素的第一个字母在英文字母表中的先后顺序构造一棵二叉排序树，然后求出在等概率情况下成功查找一个元素的 ASL。51
14、深度为 6 的平衡二叉树最少有多少个结点?说明你的推理方法。树模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 C【试题解析】 根据树的基本定义可知，每个树只能有且只有一个根节点【知识模块】 树2 【正确答案】 C【试题解析】 根据二叉树的性质，二叉树的第 m 层上最多有 2m，一 1。【知识模块】 树3 【正确答案】 C【试题解析】 此题干的叙述符合平衡二叉树的定义。【知识模块】 树4 【正确答案】 C【试题解析】 非空满 k 叉树，只有度为后和度为 O 的两种结点；满 k 叉树的结点总个数为： 其中，k n 为叶子节点的数目。n 为分叶子节点的数目，根据公式可以得出如下结论： 则可以
15、得出：1 一 kn+1 一(1 一 k)rt=(kn 一 kn+1)，1 一 kn=(1-k)rt1 一(1-k)rt=k n 即答案为：(k 一 1)rt+1【知识模块】 树5 【正确答案】 C【试题解析】 此题是对完全二叉树的考查。关于完全二叉树，考生一定要知道：它的叶子可能出现在倒数第一层或第二层，其中最后一层的叶子结点的左边一定是有其他叶子结点的，只有最后一个叶子结点才没有。【知识模块】 树6 【正确答案】 B【试题解析】 本题较难，因为考生可能都记得对二叉树进行线索化实际上是对二叉树进行线性化的过程而误选选项 C。但是线索二叉树本质上是利用了二叉树的链式存储时的空链域来保存按照某种策
16、略遍历时得到的线性序列的前驱和后继结点的地址，所以它是物理结构，也即存储结构。【知识模块】 树7 【正确答案】 D【试题解析】 本题考查的是树的存储形式。不是树的存储形式的是顺序存储方式，只有满二叉树或完全二叉树可以利用顺序存储，但并不常用。【知识模块】 树8 【正确答案】 A【试题解析】 满 m 叉树第 k 层至多有 mk-1 个结点。【知识模块】 树9 【正确答案】 C【试题解析】 本题依据二叉树的性质。设这棵完全二叉树中度为 O 的结点个数为n0，度为 1 的结点个数为 n1，度为 2 的结点个数为 n2，那么 626=n0+n1+n2，其中n1 为 0 或者为 1，n 2=n01，代入
17、公式后，n 0=313。【知识模块】 树10 【正确答案】 C【试题解析】 当这棵树是完全三叉树时，非叶子节点的个数最少为 4 个。【知识模块】 树11 【正确答案】 D【试题解析】 当这棵树有 5 个二叉结点，2 个三叉结点，非叶子结点的个数最多为 7 个。【知识模块】 树12 【正确答案】 B【试题解析】 任何一棵二叉树，在进行前序遍历、中序遍历、后序遍历，都不需要使用栈。【知识模块】 树13 【正确答案】 C【试题解析】 先根据中序和后序序列画出树，再推导即可。二叉树如下图所示： 据此可以得出前序编列的序列。【知识模块】 树14 【正确答案】 C【试题解析】 24 个叶结点代表有 23
18、个子树为 2 的结点，则总结点=23+24+28=75。【知识模块】 树15 【正确答案】 C【试题解析】 根据二叉树的性质 n0=n2+1，可知度为 2 的结点个数为 10。【知识模块】 树16 【正确答案】 D【试题解析】 已知一棵二叉树共有 n 个结点，但二叉树的形式没有给出，因此，二叉树的高度不能确定。【知识模块】 树17 【正确答案】 D【试题解析】 由完全二叉树中 5132 9，即最少需要 10 层，最多需要 513 层。【知识模块】 树18 【正确答案】 C【试题解析】 此问题可以利用二叉树及完全二叉树的性质来求解。设 ij、k 分别为度为 0、1、2 的结点数目，则 n=i+j
19、+k。根据二叉树的性质有 i=k+1，即 k=i 一1，代入上式，得 n=2i+j 一 1，即 i=(n 一 i+1)2。由于完全二叉树中最多只有一个度为 1 的结点，同时考虑到 i 为整数， (1)当 j=0 时，此时 n=i+k=2k+1 为奇数，则 i=(n+1) 2，k=i 一 1=(n+1)2 一 1=(n1)2 ； (2) 当 j=1 时，此时n=i+k+1=2k+2 为偶数，则 i=(n+1)2 向下取整，尼=i 一 1=(n+1)21=(n 一 1)2，也要向下取整。所以选 C。【知识模块】 树19 【正确答案】 B【试题解析】 由中序遍历过程可知本题答案应为 B。【知识模块】
20、 树20 【正确答案】 C【试题解析】 为了叙述的方便，定义树中两个结点之间的连线为分支。一方面，从树根向下看：很明显每个度为 3 的结点的分支是 3 个，每个度为 2 的结点分支为2 个，每个度为为 1 的结点的分支为 1 个，叶子结点不再有分支。假设该树中的分支为 n，则有 n=32+21+12。另一方面，从叶子往树根看，除了根结点之外每个结点都有一个分支将其连在树上，假设度为 O 的结点为 x，则有 n=2+1+2+x 一1。将这两个式子联立解得 x=6，即度为 0 的结点为 6。所以选项 C 正确。【知识模块】 树21 【正确答案】 C【试题解析】 本题有两个关键点：第一，深度为 5
21、的二叉树其实就是深度为 5 的满二叉树；第二，利用满二叉树的结点总数与深度的关系，套用公式 n=2k 一 1 即可，其中 k 为二叉树的深度，n 为结点数。【知识模块】 树22 【正确答案】 B【试题解析】 本题设置了两个障碍：第一，必须明白含有几个结点的二叉树有多少个空链域；第二，所谓线索就是利用二叉树中的空链域来保存其所在结点的前驱结点或后继结点。很显然，含有 n 个结点的二叉树有 2n 个链域，其中有 n 一 1 个链域表示有 n 一 1 个分支，其余 n+1 个链域为空，可以用其表示线索。【知识模块】 树23 【正确答案】 B【试题解析】 此题有两种解决方案：第一，从二叉树的左边向右看
22、，任意两个相邻的叶子结点都在一个最小的二叉子树之中。在这个最小的二叉子树中，这两个相邻的叶子必然一个位于其左子树，一个位于其右子树。这样，无论是先序、中序、后序遍历，左子树永远先于右子树访问，所以左边的叶子也就永远在右边叶子的前面。所以答案为选项 B。第二，由于本题是选择题，考生只需任意画出一棵二叉树，然后写出它的三种遍历序列即可选出选项 B。【知识模块】 树24 【正确答案】 B【试题解析】 此题考查的知识点有三个：一是只通过一种遍历序列不能确定二叉树的形态。二是知道先序遍历序列和后序遍历序列不能确定一棵二叉树。在二叉树的三种遍历方式中，只有同时知道两种遍历序列并且其中有一个是中序序列才能唯
23、一确定一棵二叉树。三是要清楚森林和二叉树的对应转化关系。【知识模块】 树25 【正确答案】 A【试题解析】 由于用递归算法遍历二叉树的效率较低，并且用二叉链表存储二叉树时还有大量的指针没有用，造成了存储空间的浪费，因此为了加快对二叉树遍历的速度，引入了二叉线索树这个存储结构。【知识模块】 树26 【正确答案】 B【试题解析】 由前序序列和中序序列先构造出二叉树，然后按层次序列进行访问。也可以使用排除法，由于前序序列第一个访问的结点必定是根结点，即 D 为根结点。而层次序列首先也必须访问根结点，可排除 A，C ，D。【知识模块】 树27 【正确答案】 A【试题解析】 使用特值法，排除 B，C，D
24、 选项。【知识模块】 树28 【正确答案】 C【试题解析】 森林中的结点个数和边数之差等于森林中树的值。【知识模块】 树29 【正确答案】 A【试题解析】 F 对应的二叉树共有 m 个结点，右子树上 n 个，左子树上有(m 一n 一 1)个，第一棵树包括根和左子树，共(m 一 n)个。【知识模块】 树30 【正确答案】 D【试题解析】 森林转换成对应的二叉树，第一棵树的根节点作为此二叉树的根结点，第一棵树除根结点外其他结点是此二叉树的左子树。二叉树的右子树是由第二棵树和第二棵树构成的，因此结点数为 M2+M3。【知识模块】 树31 【正确答案】 B【试题解析】 考查森林和二叉树的转换。森林与二
25、叉树的转换规则为左孩子右兄弟。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。 情形：若结点 v 是结点 u 的第二个孩子结点，在转换时，结点 v就变成结点 u 第一个孩子的右孩子，符合要求。 情形：结点 u 和v 是兄弟结点的关系，但二者之中还有一个兄弟结点 k，则转换后，结点 v 就变为结点 k 的右孩子，而结点 k 则是结点 u 的右孩子，符合要求。 情形：结点 v 的父结点要么是原先的父结点或兄弟结点。若结点 u 的父结点与 v的父结点是兄弟关系，则转换之后，不可能出现结点 u 是结点 v 的父结点的父结点。 【知识模块】 树32 【正确答案】 B【试题
26、解析】 森林转化成二叉树后，左子树即为原来的第一棵树(除根结点外)，其结点个数要除去根结点。【知识模块】 树33 【正确答案】 C【试题解析】 考查叶结点与总数之间的关系公式 n0+n1+n2=n1+2n2+1=n，n 0=n2+1=m 且 n1=0，则结点总数 2m 一 1。【知识模块】 树34 【正确答案】 D【试题解析】 高度为 h 的 AVL 树上的最少结点个数是 2(h-2)+2(h-3)一 1；高度为 h的 AVL 树上的最多结点个数是达到满二叉树的情况，结点个数为 2h 一 1。【知识模块】 树35 【正确答案】 B【试题解析】 考查平衡二叉树的定义。根据平衡二叉树的定义有，任意
27、结点的左右子树高度差的绝对值不超过 1。而其余三个答案均可以找到不符合的结点。【知识模块】 树36 【正确答案】 C【试题解析】 考查平衡二叉树的插入算法。插入 48 以后，该二叉树根结点的平衡因子由一 1 变为一 2，失去平衡，需进行两次旋转(先右旋后左旋)操作。 【知识模块】 树37 【正确答案】 A【试题解析】 考查哈夫曼树的特性。哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为 1 的结点，B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点 P 的权值为其左右子树根结点权值之和，其权值不小于其左
28、右子树根结点的权值，在与结点 P 的左右子树根结点处于同一层的结点中，若存在权值大于结点 P 权值的结点 Q，那么结点 Q 的兄弟结点中权值较小的一个应该与结点 P 作为左右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。【知识模块】 树二、综合题38 【正确答案】 集合、线性结构、树形结构、图形或网状结构。39 【正确答案】 逻辑结构、存储结构、操作(运算)。40 【正确答案】 通常考虑算法运行所需要的存储空间量和时间量。后者又涉及四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。4
29、1 【正确答案】 D 是数据对象，是数据元素的有限集合， R 是 D 上数据元素之间关系的有限集合。42 【正确答案】 1 0 8 2 6 4 5 7 3 9 143 【正确答案】 构造出的平衡二叉树为： 故：高度为 3。 在严蔚敏的数据结构(C 语言版)中二叉树的深度定义是这样的：“结点的层次从根开始定义，根为第一层，树中结点的最大层次为树的深度或高度”。【知识模块】 树44 【正确答案】 根结点是 24。【知识模块】 树45 【正确答案】 左子树上的数据为 13。【知识模块】 树46 【正确答案】 右子树中的数据为 53，31，90。【知识模块】 树47 【正确答案】 如果在对字符的二进制
30、编码中不存在某一个字符的编码是另一个字符编码的前缀，那么就称这种编码方式为非前缀编码，Huffman 编码就是一种非前缀编码。比如 A：00 B：10 C：0100 D：0101，则这种编码为非前缀编码；A：01 B：10 C ：010 D ：0000，则这种编码为前缀编码。 先判断(1)，(2)，(3)，(4)种情况均为非前缀编码。下面我们查看是否为哈夫曼树。 由编码恢复出树，分别为： 可见，这 4 棵树都满足哈夫曼树的定义，故它们都是哈夫曼编码。【知识模块】 树【知识模块】 树48 【正确答案】 为方便起见，只保留前三位字母，并不影响最终排序。【知识模块】 树49 【正确答案】 【知识模块】 树50 【正确答案】 成功查找一个元素的ASL=11+22+33+43+52+61=42。【知识模块】 树51 【正确答案】 要想让平衡二叉树的结点数最少，应该尽量让结点向深度方向分布，但是还得保持平衡。 如下图所示： 深度为 1 时： 深度为 2 时： 深度为 3 时： 深度为 4 时： 深度为 5时： 深度为 6 时： 【知识模块】 树
