1、树与二叉树模拟试卷 2 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 n 个结点的线索二叉树上含有的线索数为（ ）。（A）2n（B） n-1（C） n+1（D）n2 在线索二叉树中，下列说法不正确的是（ ）。（A）在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的最左下结点（B）在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的最右下结点（C）线索二叉树是利用二叉树的 n+1 个空指针来存放结点的前驱和后继信息的（D）每个结点通过线索都可以直接找到它的前驱和后继3 对 n 阶对称矩阵压缩存储时，需要表长为（ ）的顺序表。（A）n2（B） n,n2
2、（C） n(n+1)2（D）n(n-1)24 二叉树在线索化后，仍不能有效求解的问题是（ ）。（A）先序线索二叉树中求先序后继（B）中序线索二叉树中求中序后继（C）中序线索二叉树中求中序前驱（D）后序线索二叉树中求后序后继5 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是（ ）。（A）不确定（B） 0 个（C） 1 个（D）2 个6 若 X 是二叉中序线索树中一个有左孩子的结点，且 x 不为根，则 x 的前驱为（ ）。（A）X 的双亲（B） X 的右子树中最左的结点（C） X 的左子树中最右结点（D）x 的左子树中最右叶结点7 （ ）的遍历仍需要栈的支持。（A）前序线索树（B）中序
3、线索树（C）后序线索树（D）所有线索树8 已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是（ ）。（A）115（B） 116（C） 1895（D）18969 设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p，p 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是（ ）。（A）m-n（B） m-n-1（C） n+1（D）条件不足，无法确定10 森林 T=(T1，T2 ，Tm)转化为二叉树 BT 的过程为若 m=0，则 BT 为空，则（ ）。（A）将中间子树 Tmid(mid=(1+m)2)的根作为 BT 的根；将(T1，T2，
4、Tmid-1)转换为 BT。的左子树；将(Tmid+1 ，Tm)转换为 BT 的右子树（B）将子树 T1 的根作为 BT 的根：将 T1 的子树森林转换成 BT 的左子树；将(T2，T3，Tm) 转换成 BT 的右子树（C）将子树 T1 的根作为 BT 的根；将 T1 的左子树森林转换成 BT 的左子树；将T1 的右子树森林转换为 BT 的右子树；其他依此类推（D）将森林 T 的根作为 BT 的根：将(T1，T2 ，Tm)转化为该根下的结点。得到一棵树，然后将这棵树再转化为二叉树 BT11 设 F 是一个森林， B 是由 F 变换来的二叉树。若 F 中有 n 个非终端结点，则 B中右指针域为空
5、的结点有（ ）个。（A）n-1（B） n（C） n+1（D）n+212 设森林 F 中有 3 棵树，第一、第二、第三棵树的结点个数分别为 M1、M2 和M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（ ）。（A）M1（B） M1+M2（C） M3（D）M2+M313 将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是（ ）。I,父子关系 II,兄弟关系 III,u 的父结点与 v 的父结点是兄弟关系（A）只有 II（B） I 和 II（C） I 和 III（D）I、II 和 III14 利用二叉链表存储森林
6、，则根结点的右指针是（ ）。（A）指向最左兄弟（B）指向最右兄弟（C）一定为空（D）不一定为空15 某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括（ ）棵树。（A）1（B） 2（C） 3（D）416 下列二叉排序树中，满足平衡二叉树定义的是（ ）。17 在下列平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树，在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是（ ）。（A）13，48（B） 24，48（C） 24，53（D）24，9018 对 n 个权值均不相同的字符构成赫夫曼树，关于该树的叙述中，错误的是（ ）。（A）该树
7、一定是一棵完全二叉树（B）树中一定没有度为 1 的结点（C）树中两个权值最小的结点一定是兄弟结点（D）树中任一非叶结点的权值一定不小于下一层任一结点的权值19 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。（A）95，22，91，24，94，71（B） 92，20，91，34，88，35（C） 21，89，77，29，36，38（D）12，25，71，68，33，3420 按（ ）遍历二叉排序树得到的序列是一个有序序列。（A）先序（B）中序（C）后序（D）层次21 在二叉排序树中进行查找的效率与（ ）有关。（A）二叉排序树的深度（B）二叉排序树的结点的个数（C）被查找
8、结点的度（D）二叉排序树的存储结构22 对于二叉排序树，下面的说法（ ）是正确的。（A）二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合（B）对二叉排序树进行层序遍历可得到有序序列（C）用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大（D）在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1223 分别以下列序列构造二叉排序树，与用其他 3 个序列所构造的结果不同的是（ ）。（A）(100 ，80，90，60，120，110，130)（B） (100，120，110，130，80，60，90)（C） (100，60，80，90，120，1
9、10，130)（D）(100 ，80，60，90，120，130，110)24 设二叉排序树中关键字由 1 到 1000 的整数构成，现要查找关键字为 363 的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列是（ ）。（A）2，252，401，398，330，344，397，363（B） 924，220，911，244，898，258，362，363（C） 925，202，911，240，912，245，363（D）2，399，387，219，266，382，381，278， 36325 在含有 n 个结点的二叉排序树中查找某个关键字的结点时，最多进行（ ）次比较。（A）n2（B）
10、log2n（C） log2n+l（D）n26 构造一棵具有 n 个结点的二叉排序树，在最理想的情况下的深度为（ ）。（A）n2（B） n（C） log2(n+1)（D）log 2(n+1)27 从空树开始，依次插入元素 52、26、14、32、71、60、93、58、24 和 41 后构成了一棵二叉排序树。在该树查找 60 要进行比较的次数为（ ）。（A）3（B） 4（C） 5（D）628 不可能生成如图所示的二叉排序树的关键字序列是（ ）。（A）4 ，2， 1，3，5)（B） 4，2，5，3，1)（C） 4，5，2，1，3（D）4 ，5， 1，2，3)29 含有 20 个结点的平衡二叉树的最
11、大深度为（ ）。（A）4（B） 5（C） 6（D）730 具有 5 层结点的 AVL 树至少有（ ）个结点。（A）10（B） 12（C） 15（D）1731 在有 n 个叶子结点的赫夫曼树中，非叶子结点的总数（ ）。（A）n-1（B） n（C） 2n-1（D）2n32 一棵赫夫曼树共有 215 个结点，对其进行赫夫曼编码，共能得到（ ）个不同的码字。（A）107（B） 108（C） 214（D）21533 下列编码中（ ）不是前缀码。（A）00 ，01 ，10，11)（B） 0，1，00，11（C） 0，10，110，111)（D）10 ，110 ，1110，1111)34 设赫夫曼编码的长度
12、不超过 4，若已对两个字符编码为 1 和 01，则还可对（ ）字符编码。（A）2（B） 3（C） 4（D）535 给定整数集合3，5， 6，9，12 ，与之对应的赫夫曼树是（ ）。二、综合题36 已知一具有 n 个顶点的有向图 G=(V，E)采用邻接表存储方法。请写一算法，检查任意给定序列 v1，v 2，v 3，v n(viV，1in)是否为该有向图的一个拓扑序列。若是，算法给出信息 1；否则，给出信息 0。37 写出从图的邻接表表示转换成邻接矩阵表示的算法，用类 PASCAL 语言(或 C语言)写成过程形式。38 编写算法，求有向图 G 中距离顶点 v0 的最短路径长度为 len 的所有顶点
13、。39 试设计一个算法，判断一个无环路有向图 G 中是否存在这样的顶点，该顶点到其他任意顶点都有一条路径可达。40 设无向图 G 已用邻接表结构存储，顶点表为 GLn(n 为图中顶点数)，试用“广度优先搜索” 方法，写出求图 G 中各连通分量的 C 语言描述算法：BFSCOM(GL)。(注：算法中可调用队列操作的基本算法)41 一棵二叉树以二叉链表来表示，求其指定的某一层 k(k1)上的叶予结点的个数。树与二叉树模拟试卷 2 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 C【试题解析】 n 个结点共有链域指针 2n 个，其中，除根结点外，每一个结点都被一
14、个指针指向。剩余的链域建立线索，共 2n-(n-1)=n+1 个线索。【知识模块】 树与二叉树2 【正确答案】 D【试题解析】 不是每个结点通过线索都可以直接找到它的前驱和后继。在先序线索二叉树中查找一个结点的先序后继很简单，而查找先序前驱必须知道该结点的双亲结点。同样，在后序线索二叉树中查找一个结点的后序前驱也很简单，而查找后序后继也必须知道该结点的双亲结点，二叉链表中没有存放双亲的指针。【知识模块】 树与二叉树3 【正确答案】 C【试题解析】 题中所给二叉树的后序序列为 dbca。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结
15、点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。正确选项为 D。【知识模块】 树与二叉树4 【正确答案】 D【知识模块】 树与二叉树5 【正确答案】 D【试题解析】 对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。利用树中空指针指向结点在相应遍历顺序中的前驱和后继结点。对于左子树为空二叉树进行先序线索化，根结点的左子树为空并且也没有前驱结点(先遍历根结点)，先序遍历的最后一个元素为叶结点，左、右子树均为空且有前驱无后继结点，故线索化后，树中空链域有 2 个。【知识模块】 树与二叉树6 【正确答案】 C【试题解析】 在二叉中序线索树中，某结点若
16、有左孩子，则按照中序“左根右”的顺序，该结点的前驱结点为左子树中最右的一个结点。【知识模块】 树与二叉树7 【正确答案】 C【试题解析】 不需要栈的支持仍可遍历则有结点的左子树不为空时，它的前趋是其父结点或者左子树的结点，结点的右子树不为空时，它的后继是其父结点或者右子树的结点。显然，前序和中序线索树都满足这个条件，而后序线索树不满足。【知识模块】 树与二叉树8 【正确答案】 D【知识模块】 树与二叉树9 【正确答案】 A【试题解析】 森林转换成二叉树时采用孩子兄弟表示法，根结点及其左子树为森林中的第一棵树。右子树为其他树。所以，第一棵树的结点个数为 mn。【知识模块】 树与二叉树10 【正确
17、答案】 B【试题解析】 将森林中每棵树的根结点看成是兄弟结点的关系，再按照“左孩子右兄弟”的规则来进行转化。【知识模块】 树与二叉树11 【正确答案】 C【试题解析】 根据森林与二叉树转换规则“左孩子右兄弟”。二叉树 B 中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接在前一棵树根的右孩子上，则最后一棵树根结点的右指针为空。每一个非终端结点，它的所有孩子结点在转换之后，最后一个孩子的右指针也为空，故树 B 中右指针域为空的结点有 n+1 个。【知识模块】 树与二叉树12 【正确答案】 D【试题解析】 森林与二叉树的转换规则同样是“左孩子右兄弟”，不过与普通树不同，
18、森林中每棵树是独立的，因此，先要将每棵树的根结点全部看成是兄弟结点的关系。所以，题中森林转换后，树 2 是作为树 1 根结点的右子树，树 3 是作为树 2根结点的右子树。所以，森林 F 对应的二叉树根结点的右子树上的结点个数是M2+M3。【知识模块】 树与二叉树13 【正确答案】 B【试题解析】 森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应的森林关系中可能是兄弟关系或原本就是父子关系。情形 I：若结点 v 是结点 u 的第二个孩子结点，在转换时，结点 v 就变成结点 u 第一个孩子的右孩子，符合要求。情形 II：结点 u 和 v 是兄弟结点的关系，但二者之中还
19、有一个兄弟结点 k，则转换后，结点 v 就变为结点 k 的右孩子，而结点 k 则是结点u 的右孩子，符合要求。情形I：结点 v 的父结点要么是原先的父结点或兄弟结点。若结点 u 的父结点与 v 的父结点是兄弟关系，则转换之后，不可能出现结点u 是结点 v 的父结点的父结点。【知识模块】 树与二叉树14 【正确答案】 D【试题解析】 森林与二叉树具有对应关系，因此，我们存储森林的时候应先将森林转换成二叉树，转换的方法就是“左孩子右兄弟”，与树不同的是，如果存在第二棵树，二叉链表的根结点的右指针指向的是森林中第二棵树的根结点。若此森林只有一棵树，那么根结点的右指针为空。因此，右指针可能为空也可能不
20、为空。【知识模块】 树与二叉树15 【正确答案】 C【知识模块】 树与二叉树16 【正确答案】 B【试题解析】 根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过 l。而其余 3 个答案均可以找到不符合的结点。【知识模块】 树与二叉树17 【正确答案】 C【试题解析】 插入 48 以后，该二叉树根结点的平衡因子由-1 变为-2，失去平衡，需进行两次旋转(先右旋后左旋)操作。【知识模块】 树与二叉树18 【正确答案】 A【试题解析】 赫夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。赫夫曼树中没有度为 l 的结点，B 正确。构造赫夫曼树时，最先选取两个权值最小的结点作为左、右
21、子树构造一棵新的二叉树，C 正确。赫夫曼树中任一非叶结点 P的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点 P 的左、右子树根结点处于同一层的结点中，若存在权值大于结点 P 权值的结点 Q，那么结点 Q 与其兄弟结点中权值较小的一个应该与结点 P 作为左、右子树构造新的二叉树，综上可知，赫夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值，D 正确。【知识模块】 树与二叉树19 【正确答案】 A【试题解析】 在二叉排序树中，左子树结点值小于根结点，右子树结点值大于根结点。在选项 A 中，当查找到 91 后再向 24 查找，说明这一条路径 (左子树)之后
22、查找的数都要比 91 小，而后面却查找到了 94，因此错误，故选 A。【知识模块】 树与二叉树20 【正确答案】 B【试题解析】 由二叉排序树的定义不难得出选 B。【知识模块】 树与二叉树21 【正确答案】 A【试题解析】 二叉排序树查找算法的平均查找长度，主要取决于树的高度。【知识模块】 树与二叉树22 【正确答案】 C【试题解析】 二叉排序树插入新结点时不会引起树的分裂组合。对二叉排序树进行中序遍历可得到有序序列。当插入的关键字有序时，二叉排序树会形成一个长链，此时深度最大。在此种情况下进行查找，有可能需要比较每个结点的关键字，超过12。【知识模块】 树与二叉树23 【正确答案】 C【试题
23、解析】 按照二叉排序树的构造方法，不难得到 A、B 、D 序列的构造结果相同。【知识模块】 树与二叉树24 【正确答案】 C【试题解析】 在二叉排序树上查找时，先与根结点值进行比较，若相同，则查找结束，否则根据比较结果，沿着左子树或右子树向下继续查找。根据二叉排序树定义，有左子树结点值根结点值右子树结点值。C 序列中，比较 911 关键字后，应转向其左子树比较 240，左子树中不应出现比 911 更大的数值，但是 240 竟有一个右孩子结点值为 912，所以不可能是正确的序列。【知识模块】 树与二叉树25 【正确答案】 D【试题解析】 当输入序列是一个有序序列，构造的二叉排序树是一个单支树，当
24、查找一个不存在的关键字值或最后一个结点的关键字值时，需要 n 次比较。【知识模块】 树与二叉树26 【正确答案】 D【试题解析】 当二二叉排序树的叶子结点全部都在相邻的两层内时，深度最小。理想情况是从第一层到倒数第二层为满二叉树。类比完全二叉树，可得深度为log2(n+1)。【知识模块】 树与二叉树27 【正确答案】 A【知识模块】 树与二叉树28 【正确答案】 D【知识模块】 树与二叉树29 【正确答案】 C【试题解析】 平衡二叉树结点数的递推公式为 N0=0，N 1=1，N 2=2，N h=1+Nh-1+Nh-2(h 为平衡二叉树高度，N h 为构造此高度的平衡二叉树所需最少结点数 )。通
25、过递推公式可得，构造 5 层平衡二叉树至少需 12 个结点，构造 6 层至少需要 20 个。【知识模块】 树与二叉树30 【正确答案】 B【知识模块】 树与二叉树31 【正确答案】 A【试题解析】 赫夫曼树是二叉树。非空二叉树上叶子结点数等于度为 2 的结点数加 1，赫夫曼树中度为 1 的结点个数为 0，所以，叶子结点数-1 即为非叶子结点数。此外，n 个结点构造赫夫曼树需要 n-1 次合并过程，每次合并新建一个分支结点，故选 A。【知识模块】 树与二叉树32 【正确答案】 B【试题解析】 根据上题结论，叶子结点数为(215+1) 2=108，所以共有 108 个不同的码字。【知识模块】 树与
26、二叉树33 【正确答案】 B【试题解析】 如果没有一个编码是另一个编码的前缀，称这样的编码为前缀编码。B 选项中， 0 是 00 的前缀，1 是 11 的前缀。【知识模块】 树与二叉树34 【正确答案】 B【试题解析】 在赫夫曼编码中，一个编码不能是任何其他编码的前缀。3 位数的编码可能是 001，对应的 4 位数编码只能是 0000 和 0001。3 位数的编码也可能是000，对应的 4 位数编码只能是 0010 和 0011。故选 B。【知识模块】 树与二叉树35 【正确答案】 C【试题解析】 先是 3 和 5 构造为一棵子树，其根权值为 8，然后该子树与 6 构成一棵新子树，根权值为 1
27、4，然后 9 与 12 构造为一棵子树，最后两棵子树共同构造为一棵赫夫曼树。【知识模块】 树与二叉树二、综合题36 【正确答案】 算法的基本设计思想：根据拓扑排序的性质，序列中的顶点 vi 满足对任何 vj(ji)都不存在 vj 到 vi 的路径。当删除 vi 前所有顶点及以之为尾的弧后，不存在任何以 vi 为尾的弧。 算法的实现过程如下： 设置变量 vj，令其等于 vi。 遍历邻接表，检查是否存在表结点为 vj。若不存在，则执行下一步，否则返回0。 删除以 vj 为表头的表。若未到序列末，令 vj 为序列中下一顶点，并执行步骤；否则返回 1。 算法的代码： int CheckTopo(ALG
28、raphG ，vexElemV) 检查顶点数组 v 中的序列是否为该图的一个拓扑序列 int i，j ； vexElem vj ; ArcNode*p， *q; for(i=0； iverticesj)firstarc; while(P!=NULL) 遍历边链表。找到序列中当前顶点，说明序列不是拓扑序列 if(vj=Pdata) return 0； P=P-next： for(J=0;JverticesJ) p=(G-verticesJ)firstarc ; while(p !=NULL) 遍历边链表，删除各边结点 q=p; p=p-next； free(q)， (G-verticesj)，f
29、irstarc=NULL； 【知识模块】 树与二叉树37 【正确答案】 算法的基本设计思想：设图的顶点分别存储在 vn数组中。首先初始化数据结构，定义出邻接矩阵。遍历邻接表，在遍历顶点 vi的边链表时，修改邻接矩阵的第 i 行的元素值。若链表边结点的值为 j，则修改 arcsiU=1。遍历完邻接表时，整个转换过程结束。此算法对于无向图、有向图同样适用。算法的代码：VOid Convert(ALGraphG，arcs) 此算法将邻接表方式表示的图 G 转换为邻接矩阵 arcs设图有 n 个项点，图为带权图int i;for(i=0；iverticesi)firstarc；while(p!=NUL
30、L) 遍历边链表arcsip 一data=1；P=P 一next； Convert【知识模块】 树与二叉树38 【正确答案】 算法的基本设计思想：直接使用单源最短路径算法Dijkstra计算各顶点到 v0 的最短距离，然后找到距 v0 为 len 的顶点即可。算法的代码：void ShortestPathDIJ(MGraph G，int v0，int 1en)(全局变量 dist、path及 final。distv存放从 v0 到 v 的最短路径长度。pathvw为 1，则 w 是从 v0 到 v 当前求得最短路径上的顶点finalv 为 1 当且仅当 vS，即已求得从 v0 到 v 的最短路
31、径for(int v=0；vmin+Garcvw) 修改 distw和 pathwdiStW=min+Garcvw；pathW=pathv;pathWw=1 ; pathw=pathv+w if forfor(V=0;vadj data ;if(viSitedW=0)viSitedW=1;cOUnt+；EnQueue(W，Q);elSe P=P-next；if(count=V) V 为有向图结点总数yeS=1；return yeS；rbfS方法二：深度优先遍历(使用栈)int rdfs(ADJLIST g，int vi，int vj)int i，count，yeS；yes=0；Count=1
32、;Stack S；for(i=0；iadjdata)P=P-next：if(p=NULL)Pop(S);e1Sew=p 一adj data;viSitedW=1；COUnt+;PuSh(W，S)；if(count=v; v 为有向图结点总数yeS=1；return yes； rbfs【知识模块】 树与二叉树40 【正确答案】 算法的基本设计思想：用一个数组 visited 口记录顶点是否被访问过，对于顶点 i，如果没有被访问过，算法重复以下过程：标记为已访问，采用队列为辅助结构，将表中所有与其连通的顶点标记为已访问。判断下一个顶点 i+l。算法的代码：VOid BFSCOM() 广度优先搜索，
33、求无向图 G 的连通分量int count=0； 记连通分量个数for(int i=1； iadjvex=0) 如果此顶点还未被访问过printf(”3d”，P-adjvex)；viSitedP-adjvex=1，QueueIn(Q，P-adjvex)， ifP=p-neXt ; while while(!QueueEmpty(Q) bfs【知识模块】 树与二叉树41 【正确答案】 算法的基本设计思想：采用队列结构按层次遍历，遍历 K 层时记录叶子结点个数。算法的代码：int LeafKlevel(BiTree bt， int k)求二叉树 bt 的第 k(k1)层上叶子结点个数if(bt=N
34、ULL 1 I k1retUrn 0；BiTree p=bt，Q ； Q 是队列，元素是二叉树结点指针，容量足够大int front=0，rear=1，1eaf=0 ;front 和 rear 是队头和队尾指针， leaf 是叶子结点数int 1ast=1，1evel=1 ;1ast 是二叉树同层最右结点的指针，level 是二叉树的层数Q1=p；while(frontichild !p-rchild)1ear+； 叶子结点if(p-1chiid)Q+rear：p-lchiid ， 左子女入队if(p-rchiid)Q+rear=p-rchiid； 右子女入队if(front=last)level+； 二叉树同层最右结点已处理，层数增 1last=rear； last 移到指向下层最右一元素if(1evelk) 层数大于 k 后退出运行return leaf； while LeafKLevel【知识模块】 树与二叉树
