1、计算机学科专业基础综合数据结构-4 及答案解析(总分：104.50，做题时间：90 分钟)一、单项选择题(总题数：20，分数：70.00)具有 33个结点的完全二叉树的深度为_，有_个叶结点，有_个度为 1的结点。（分数：7.50）A.5B.6C.7D.8A.14B.15C.16D.17A.0B.1C.12D.16设深度为 d的二叉树上只有度为 0和度为 2的结点，则此二叉树中所包含的结点个数至少有_；已知二叉树有 50个叶结点，有 30个度为 1的结点，则该二叉树的总结点数为_。（分数：5.00）A.2d+1B.2d-1C.2d-1D.2d-1A.129B.130C.131D.1321.设森
2、林中有三棵树，第一、第二和第三棵树中的结点个数分别为 m1、m2 和 m3。那么在由该森林转化成的二叉树中根结点的右子树上的结点个数是_。（分数：2.50）A.m1+m2B.m2+m3C.m3+m1D.m1+m2+m32.用 n个权值构造出来的 Huffman树的结点个数是_。（分数：2.50）A.2n-1B.2nC.2n+1D.n+13.在下列关于二叉树遍历的说法中错误的是_。（分数：2.50）A.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果B.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行中序遍历和后序遍
3、历，则具有相同的遍历结果C.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的遍历结果D.在一棵二叉树中，假定每个结点最多只有右子女，没有左子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果4.在下列关于二叉树遍历的说法中正确的是_。（分数：2.50）A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点C.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的
4、最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点D.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点5.前序为 A、B、C，后序为 C、B、A 的二叉树共有_。（分数：2.50）A.1棵B.2棵C.3棵D.4棵在一棵非空二叉树的中序遍历序列中，根结点的右边_；设 n和 m分别是一棵二叉树上的两个结点，在中序遍历时，n 在 m前面访问的条件是_（分数：5.00）A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点A.n在 m右侧分支B.n是 m祖先C.n在 m左侧
5、分支D.n是 m子孙6.设结点 x和 y是二叉树中任意的两个结点。在该二叉树的前序遍历序列中 x在 y之前，而在其后序遍历序列中 x在 y之后，则*和 y的关系是_。（分数：2.50）A.x是 y的左兄弟B.x是 y的右兄弟C.x是 y的祖先D.x是 y的后裔结点数目为 n(n0)的二叉排序树的最小高度为_，最大高度为_。（分数：5.00）(1).An B C D （分数：2.50）A.B.C.D.(2).An B C D （分数：2.50）A.B.C.D.7.在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。（分数：2.50）A.左指针一定为空B.右指针一定为空C.左右指针均为空D.
6、左右指针均不为空8.在下列关于平衡二叉树的说法中正确的是_。（分数：2.50）A.任意结点的左、右子树结点数目相同B.任意结点的左、右子树高度相同C.任意结点的左、右子树高度之差的绝对值不大于 1D.不存在度为 1的结点具有 5层结点的平衡二叉树至少有_个结点。若设树根结点在第 1层，则深度最小的叶结点应在第_层。（分数：5.00）A.10B.12C.15D.17A.1B.2C.3D.49.设 F是一个森林，B 是由 F转换得到的二叉树，F 中有 n个非叶结点，则 B中右指针域为空的结点个数是_。（分数：2.50）A.n-1BnC.n+1D.n+2若设一棵树具有 n个结点，则它所有结点的度数之
7、和为_。设森林 F对应的二叉树为 B，它有 m个结点。B 的根为 p，p 的右子树中结点个数为 n，则森林 F中第一棵树的结点个数是_。如果 T 2 是由有序树 T转换成的二叉树，那么 T中结点的后序遍历顺序对应 T 2 中结点的_遍历顺序。（分数：7.50）A.2nB.2n-1C.n+1D.n-1A.m-nB.m-n-1C.n+1D.无法确定A.前序B.中序C.后序D.层次序10.下面关于 Huffman树的说法中不正确的是_。（分数：2.50）A.对应一组权值构造出来的 Huffman树一般不是唯一的B.Huffman树具有最小的带权路径长度C.Huffman树中没有度为 1的结点D.Hu
8、ffman树中除了度为 1的结点之外，还有度为 2的结点和叶子结点11.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是_。（分数：2.50）A.先序遍历二叉树B.判断两个指定位置的结点是否在同一层上C.层次遍历二叉树D.根据结点的值查找其存储位置12.以下叙述不正确的是_。（分数：2.50）A.后序线索二叉树是不完善的，要对它进行遍历，不需使用栈B.任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈C.任何一棵二叉树都可以不用栈实现先序线索树的先序遍历D.任何一棵二叉树都可以不用栈实现中序线索树的中序遍历13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A
9、，并已知 A的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应作_型调整以使其平衡。（分数：2.50）A.LLB.LRC.RLD.RR14.下列叙述正确的个数是_。 (1)m=2的平衡 m路查找树是 AVL树 (2)m=3的平衡 m路查找树是 2-3树 (3)m=2的平衡 m路查找树的叶结点不一定在同一层 (4)m阶 B-树的叶结点必须在同一层 (5)m阶 B-树是平衡 m路查找树 (6)平衡 m路查找树不一定是 B-树（分数：2.50）A.3B.4C.5D.6二、综合应用题(总题数：3，分数：34.50)已知一棵二叉树的前序序列为：A，B，D，G，J，E，H，C，F，I，K，L；中序序列
10、为：D，J，G，B，E，H，A，C，K，I，I，F。（分数：13.50）(1).写出该二叉树的后序序列（分数：4.50）_(2).画出该二叉树（分数：4.50）_(3).求该二叉树的高度以及该二叉树中度为 2，1，0 的结点个数（分数：4.50）_设二叉树根结点所在层次为 0，树的深度 d为距离根最远的叶结点所在层次，试回答以下问题：（分数：9.00）(1).试精确给出深度为 d的完全二叉树的不同二叉树棵数（分数：4.50）_(2).试精确给出深度为 d的满二叉树的不同二叉树棵数（分数：4.50）_如果一棵有 n个结点的满二叉树的高度为 h(根结点所在的层次为 1)，则：（分数：12.00）(
11、1).用高度如何表示结点总数 n?用结点总数 n如何表示高度 h?（分数：6.00）_(2).若对该树的结点从 0开始按中序遍历次序进行编号，则如何用高度 h表示根结点的编号?如何用高度h表示根结点的左子女结点的编号和右子女结点的编号?（分数：6.00）_计算机学科专业基础综合数据结构-4 答案解析(总分：104.50，做题时间：90 分钟)一、单项选择题(总题数：20，分数：70.00)具有 33个结点的完全二叉树的深度为_，有_个叶结点，有_个度为 1的结点。（分数：7.50）A.5B.6 C.7D.8解析：A.14B.15C.16D.17 解析：A.0 B.1C.12D.16解析：解析
12、根据二叉树的性质，设度为 O的结点有 n 0 个，度为 2的结点有 n 2 个，则有 n 0 =n 2 +1。就是说，n 0 +n 2 是一个奇数。此外，对于一棵完全二叉树，度为 1的结点要么没有，要么只有 1个。因此，按照题意，完全二叉树有 33个结点，在该树中应没有度为 1的结点，只有度为 0和度为 2的结点。设二叉树的结点总数为 n，则有 n=n 2 +n 0 =2n 0 -1=33，n 0 =17，n 2 =160该完全二叉树的深度d= 设深度为 d的二叉树上只有度为 0和度为 2的结点，则此二叉树中所包含的结点个数至少有_；已知二叉树有 50个叶结点，有 30个度为 1的结点，则该二
13、叉树的总结点数为_。（分数：5.00）A.2d+1B.2d-1 C.2d-1D.2d-1解析：A.129 B.130C.131D.132解析：解析 当树中只有度为 0和度为 2的结点时，未达到深度 d，至少需要 d-1个度为 2的结点(非叶结点)和 d个度为 0的结点(叶结点)。因此，至少有 2d-1个结点。根据 n 0 =n 2 +1，当 n 0 =50时，n 2 =49，所以二叉树中结点总数为 50+49+30=129。1.设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为 m1、m2 和 m3。那么在由该森林转化成的二叉树中根结点的右子树上的结点个数是_。（分数：2.50）A.m1
14、+m2B.m2+m3 C.m3+m1D.m1+m2+m3解析：解析 在由森林转化成的二叉树中根结点的右子树上的结点是除第一棵外其他树上的结点，应有m2+m3个。2.用 n个权值构造出来的 Huffman树的结点个数是_。（分数：2.50）A.2n-1 B.2nC.2n+1D.n+1解析：解析 用 n个权值构造出来的 Huffman树共有 2n-1个结点，其中叶结点 n个，度为 2的非叶结点n-1个。3.在下列关于二叉树遍历的说法中错误的是_。（分数：2.50）A.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果 B.在一棵二叉树中，假
15、定每个结点最多只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果C.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的遍历结果D.在一棵二叉树中，假定每个结点最多只有右子女，没有左子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果解析：解析 假设在一棵二叉树上最多只有左子女，没有右子女，这是一棵左斜单枝树，遍历过程少了R。前序遍历结果(NL)和后序遍历结果(LN)正好相反，所以选项 A是错误的。而中序遍历结果(LN)与后序遍历结果(LN)相同，前序遍历结果(NL)与按层遍历结果(NL)相同。选项 D描述的是右斜
16、单枝树，遍历过程少了 L，前序遍历结果(NR)与中序遍历结果(NR)相同。4.在下列关于二叉树遍历的说法中正确的是_。（分数：2.50）A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点C.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点 D.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最
17、后一个结点解析：解析 二叉树中序遍历的最后一个结点一定是从根开始沿右子女指针链走到底的结点，设用指针p指示。若结点 p不是叶子结点(其左子树非空)，则前序遍历的最后一个结点在它的左子树中，选项A、B 错；若结点 p是叶子结点，则前序与中序遍历的最后一个结点就是它，选项 C对。若中序遍历的最后一个结点 p不是叶子结点，它还有一个左子女 q，结点 q是叶子结点，那么结点 q是前序遍历的最后一个结点，但不是中序遍历的最后一个结点，选项 D错。5.前序为 A、B、C，后序为 C、B、A 的二叉树共有_。（分数：2.50）A.1棵B.2棵C.3棵D.4棵 解析：解析 前序为 ABC的不同二叉树有 5种，
18、其中后序为 CBA的有 4种，都是单枝树，如下图所示。 在一棵非空二叉树的中序遍历序列中，根结点的右边_；设 n和 m分别是一棵二叉树上的两个结点，在中序遍历时，n 在 m前面访问的条件是_（分数：5.00）A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点解析：A.n在 m右侧分支B.n是 m祖先C.n在 m左侧分支 D.n是 m子孙解析：解析 二叉树的中序遍历顺序是：若二叉树非空，则首先中序遍历根的左子树，然后访问根结点，最后中序遍历根的右子树。所以在二叉树的中序遍历序列中，根的左侧的数据是根的左子树上的数据，根的右侧的数据是根的右子
19、树上的数据。因此，若结点 n位于结点 m左侧的分支，则结点 n应在结点 m之前访问。如果 n是 m的祖先，n 能否在 m之前访问是不一定的；若 m在 n的左子树上，m 将先于 n访问；若m位于 n的右子树上，n 先于 m访问。n 是 m的子孙的情形类似。6.设结点 x和 y是二叉树中任意的两个结点。在该二叉树的前序遍历序列中 x在 y之前，而在其后序遍历序列中 x在 y之后，则*和 y的关系是_。（分数：2.50）A.x是 y的左兄弟B.x是 y的右兄弟C.x是 y的祖先 D.x是 y的后裔解析：解析 设二叉树的前序遍历顺序为 NLR，后序遍历顺序为 LRN。根据题意，在前序遍历序列中 x在
20、y前，在后序遍历序列中 x在 y之后，若设 x在根结点的位置，y 在其左子树或右子树中，即满足要求。结点数目为 n(n0)的二叉排序树的最小高度为_，最大高度为_。（分数：5.00）(1).An B C D （分数：2.50）A.B.C.D. 解析：(2).An B C D （分数：2.50）A. B.C.D.解析：解析 最小高度为7.在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。（分数：2.50）A.左指针一定为空B.右指针一定为空 C.左右指针均为空D.左右指针均不为空解析：解析 在二叉排序树的存储结构中，每个结点由三部分构成，其中左(或右)指针指向比结点的关键字值小(或大)的
21、结点。关键字值最大的结点位于二叉排序树的最右下位置上，它的右指针一定为空(注意，有可能不是叶结点)。8.在下列关于平衡二叉树的说法中正确的是_。（分数：2.50）A.任意结点的左、右子树结点数目相同B.任意结点的左、右子树高度相同C.任意结点的左、右子树高度之差的绝对值不大于 1 D.不存在度为 1的结点解析：解析 平衡二叉树的定义。具有 5层结点的平衡二叉树至少有_个结点。若设树根结点在第 1层，则深度最小的叶结点应在第_层。（分数：5.00）A.10B.12 C.15D.17解析：A.1B.2C.3 D.4解析：解析 若设高度为 h的平衡二叉树的最少结点数为 N h ，则有： N 0 =0
22、，N 1 =1，N h =N h-1 +N h-2 +1(h1) 逐项推导：N 2 =N 1 +N 0 +1=2，N 3 =N 2 +N 1 +1=4，N 4 =N 3 +N 2 +1=7，N 5 =N 4 +N 3 +1=12。 深度最小的叶结点在第 3层。计算平衡二叉树深度最小的叶结点所在层次的方法与推导高度为 h的平衡二叉树的最少结点个数的过程类似。如下图所示，若设高度为 h的平衡二叉树的深度最小的叶结点所在层次为 L h ，则有：L 1 =1，L 2 =2，L h =minL h-1 ，L h-2 +1=L h-2 +1，h2 因此 9.设 F是一个森林，B 是由 F转换得到的二叉树，
23、F 中有 n个非叶结点，则 B中右指针域为空的结点个数是_。（分数：2.50）A.n-1BnC.n+1 D.n+2解析：解析 F 的每个非叶结点在其二叉树表示 B中有一个子女(兄弟)链，每个链最后一个兄弟的右指针为空，而 F的各棵树链在一个兄弟链上，最后一棵树的根结点的右指针为空。所以，总共有 n+1个空的右指针域。若设一棵树具有 n个结点，则它所有结点的度数之和为_。设森林 F对应的二叉树为 B，它有 m个结点。B 的根为 p，p 的右子树中结点个数为 n，则森林 F中第一棵树的结点个数是_。如果 T 2 是由有序树 T转换成的二叉树，那么 T中结点的后序遍历顺序对应 T 2 中结点的_遍历
24、顺序。（分数：7.50）A.2nB.2n-1C.n+1D.n-1 解析：A.m-n B.m-n-1C.n+1D.无法确定解析：A.前序B.中序 C.后序D.层次序解析：解析 树中所有结点的度数之和为它们发出的边数的总和，树中总共有 n-1条边，所以树中所有结点度数的总和为 n-1。森林 F对应的二叉树 B有 m个结点，该二叉树的右子树有 n个结点，根据森林和对应二叉树的转换规则，这是森林中除第一棵树外其他树的结点个数，剩下的 m-n个结点是森林第一棵树的结点个数。树的后序遍历结果与其对应二叉树的中序遍历结果相同，所以 T的后序遍历顺序对应 T 2 的中序遍历顺序。10.下面关于 Huffman
25、树的说法中不正确的是_。（分数：2.50）A.对应一组权值构造出来的 Huffman树一般不是唯一的B.Huffman树具有最小的带权路径长度C.Huffman树中没有度为 1的结点D.Huffman树中除了度为 1的结点之外，还有度为 2的结点和叶子结点 解析：解析 Huffman 树只有度为 0的结点和度为 2的结点。度为 0的结点是外部结点，带有权值。11.二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是_。（分数：2.50）A.先序遍历二叉树B.判断两个指定位置的结点是否在同一层上 C.层次遍历二叉树D.根据结点的值查找其存储位置解析：解析 选项 A、C、D 运算的时间复
26、杂度都是 O(n)，而选项 B的运算的时间复杂度为 O(1)，因为对于指定位置 p和 q的两个结点，判断是否在同一层上，只需判断两者|log 2 p|=|log 2 q|是否成立。12.以下叙述不正确的是_。（分数：2.50）A.后序线索二叉树是不完善的，要对它进行遍历，不需使用栈B.任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈 C.任何一棵二叉树都可以不用栈实现先序线索树的先序遍历D.任何一棵二叉树都可以不用栈实现中序线索树的中序遍历解析：解析 B 不需要使用栈。13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A的左孩子的平衡因子为 0，右孩子的平衡
27、因子为 1，则应作_型调整以使其平衡。（分数：2.50）A.LLB.LRC.RL D.RR解析：解析 最低的不平衡结点为 A，并已知 A的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则意味着在结点 A的右孩子的左子树上进行插入，插入使结点 A失去平衡，与 LR型正好对称。14.下列叙述正确的个数是_。 (1)m=2的平衡 m路查找树是 AVL树 (2)m=3的平衡 m路查找树是 2-3树 (3)m=2的平衡 m路查找树的叶结点不一定在同一层 (4)m阶 B-树的叶结点必须在同一层 (5)m阶 B-树是平衡 m路查找树 (6)平衡 m路查找树不一定是 B-树（分数：2.50）A.3B.4C.
28、5D.6 解析：解析 本题主要考查平衡树定义。二、综合应用题(总题数：3，分数：34.50)已知一棵二叉树的前序序列为：A，B，D，G，J，E，H，C，F，I，K，L；中序序列为：D，J，G，B，E，H，A，C，K，I，I，F。（分数：13.50）(1).写出该二叉树的后序序列（分数：4.50）_正确答案：()解析：此题只需从前序序列、中序序列得到唯一确定的二叉树即可。 J，G，D，H，E，B，K，L，I，F，C，A；(2).画出该二叉树（分数：4.50）_正确答案：()解析：二叉树的形式如下图所示。 (3).求该二叉树的高度以及该二叉树中度为 2，1，0 的结点个数（分数：4.50）_正确答
29、案：()解析：高度是 5。 度为 0的结点个数为 4； 度为 1的结点个数为 5； 度为 2的结点个数为 3。设二叉树根结点所在层次为 0，树的深度 d为距离根最远的叶结点所在层次，试回答以下问题：（分数：9.00）(1).试精确给出深度为 d的完全二叉树的不同二叉树棵数（分数：4.50）_正确答案：()解析：这与教材上讲的根结点所在层次为 1的情形相比，深度差 1。在第 d层最多有 2 d 个结点。因此，深度为 d的不同完全二叉树有 2 d 棵。(2).试精确给出深度为 d的满二叉树的不同二叉树棵数（分数：4.50）_正确答案：()解析：深度为 d的满二叉树只有 1棵。如果一棵有 n个结点的
30、满二叉树的高度为 h(根结点所在的层次为 1)，则：（分数：12.00）(1).用高度如何表示结点总数 n?用结点总数 n如何表示高度 h?（分数：6.00）_正确答案：()解析：按照题意，该满二叉树的高度为 h，结点总数为 n，那么： 按照二叉树的性质，n=2 h -1，反之，h=log 2 (n+1)。(2).若对该树的结点从 0开始按中序遍历次序进行编号，则如何用高度 h表示根结点的编号?如何用高度h表示根结点的左子女结点的编号和右子女结点的编号?（分数：6.00）_正确答案：()解析：用高度 h确定根结点编号的依据有三：从满二叉树推知，结点数有 n=2 h -1个，编号从 0到 n-1(=2 h -2)；由于是按中序遍历次序所做的编号，根结点的左、右子树的结点数相等，根结点的编号应位于正中；按照求中点的公式，中点的编号应为 mid=(low+high)/2=(0+2 h -2)/2：2 h-1 -1，此即满二叉树根结点的编号。依次类推，根结点左子树有 2 h-1 -1个结点，其结点编号从 0到 2 h-1 -2，左子树根结点即根结点左子女结点的编号为 2 h-2 -1；而右子女结点的编号为 2 h-1 +(2 h-2 -1)=32 h-2 -1。
