计算机学科专业基础综合数据结构-4

1、计算机学科专业基础综合数据结构 -4（ 总分： 104.50 ，做题时间： 90 分钟 ）、 单项选择题 （ 总题数： 20 ，分数： 70.00）具有 33 个结点的完全二叉树的深度为 ，有个叶结点，有个度为 1 的结点。（分数：7.50 ）A. 5B. 6 C. 7D. 8A. 14B. 15C. 16D. 17 A. 0 B. 1C. 12D. 16根据二叉树的性质，设度为 O 的结点有 n 0 个，度为 2 的结点有 n 2 个，则有 n 0 =n 2 +1。就是说， n 0 +n2 是一个奇数。 完全二叉树有此外，对于一棵完全二叉树，度为33 个结点， 在该树中应没有度为 11 的结

2、点要么没有，要么只有 1 个。因此，按照题意， 的结点，只有度为 0和度为 2的结点。 设二叉树的结点总数为 n，则有n=n 2 +n 0 =2n 0 -1=33 ，n 0 =17 ，=6。n 2 =160 该完全二叉树的深度 d=设深度为 d 的二叉树上只有度为 0 和度为 2 的结点，则此二叉树中所包含的结点个数至少有 ；已知二叉树有 50 个叶结点，有 30个度为 1 的结点，则该二叉树的总结点数为 。A. 2d+1B. 2d-1 C. 2d-1D. 2d-1A. 129 B. 130C. 131D. 132当树中只有度为 0和度为 2的结点时，未达到深度 d，至少需要 d-1 个度为

3、2的结点（非叶结点 ）和 d个度 为0的结点（叶结点） 。因此，至少有 2d-1 个结点。根据 n 0 =n 2 +1，当 n 0 =50 时，n 2 =49 ，所以二叉 树中结点总数为 50+49+30=129。m1、 m2和 m3。那么在由该森林转化成1. 设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为 的二叉树中根结点的右子树上的结点个数是 。（分数： 2.50 ）A. m1+m2B. m2+m3 C. m3+m1D. m1+m2+m3在由森林转化成的二叉树中根结点的右子树上的结点是除第一棵外其他树上的结点，应有m2+m3个2. 用 n 个权值构造出来的 Huffman 树的结

4、点个数是 。（分数： 2.50 ）A. 2n-1 B. 2nC. 2n+1D. n+1用 n 个权值构造出来的 Huffman 树共有 2n-1 个结点，其中叶结点 n 个，度为 2 的非叶结点 n-1 个。3. 在下列关于二叉树遍历的说法中错误的是 。(分数： 2.50 )A. 在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和后序遍历， 则具有相同的遍历结果 B. 在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行中序遍历和后序遍历， 则具有相同的遍历结果C. 在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和按层遍

5、历， 则具有相同的遍历结果D. 在一棵二叉树中，假定每个结点最多只有右子女，没有左子女，对它分别进行前序遍历和中序遍历， 则具有相同的遍历结果假设在一棵二叉树上最多只有左子女，没有右子女，这是一棵左斜单枝树，遍历过程少了R。前序遍历结果(NL)和后序遍历结果 (LN) 正好相反，所以选项 A是错误的。而中序遍历结果 (LN) 与后序遍历结果 (LN) 相 同，前序遍历结果 (NL) 与按层遍历结果 (NL) 相同。选项 D 描述的是右斜单枝树，遍历过程少了L，前序遍历结果 (NR) 与中序遍历结果 (NR) 相同。4. 在下列关于二叉树遍历的说法中正确的是 。(分数： 2.50 )A. 若有一

6、个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍 历结果序列的最后一个结点B. 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍 历结果序列的最后一个结点C. 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前 序遍历结果序列的最后一个结点 D. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中 序遍历结果序列的最后一个结点二叉树中序遍历的最后一个结点一定是从根开始沿右子女指针链走到底的结点， 设用指针 p 指示。若结点 p 不是叶子结点 (其

7、左子树非空 ) ，则前序遍历的最后一个结点在它的左子树中，选项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 种，其中后序为 CBA的有 4 种，都是单枝树，如下图所示。在一棵非空二叉树的中序遍历序列中，根结点的右边 ；设

8、 n 和 m分别是一棵二叉树上的两个结点，在中序遍历时， n 在 m前面访问的条件是 A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点A. n 在 m右侧分支B. n 是 m祖先C. n 在 m左侧分支 D. n 是 m子孙二叉树的中序遍历顺序是：若二叉树非空，则首先中序遍历根的左子树，然后访问根结点，最后中序遍历 根的右子树。所以在二叉树的中序遍历序列中，根的左侧的数据是根的左子树上的数据，根的右侧的数据 是根的右子树上的数据。因此，若结点 n 位于结点 m左侧的分支，则结点 n 应在结点 m之前访问。如果 n 是 m的祖先，

9、n 能否在 m之前访问是不一定的；若 m在 n的左子树上， m将先于 n 访问；若 m位于 n 的右子 树上， n 先于 m访问。 n 是 m 的子孙的情形类似。6. 设结点 x和 y是二叉树中任意的两个结点。在该二叉树的前序遍历序列中 x在 y之前，而在其后序遍历 序列中 x 在 y 之后，则 * 和 y 的关系是 。（分数： 2.50 ）是 y 的左兄弟 是 y 的右兄弟 是 y 的祖先 是 y 的后裔A.xB.xC.x遍历序列中 结点数目为 （1）.A nDA.BC分数： 2.50 ）D.x 设二叉树的前序遍历顺序为 NLR，后序遍历顺序为 LRN。根据题意，在前序遍历序列中 x 在 y

10、 前，在后序 x 在 y 之后，若设 x 在根结点的位置， y 在其左子树或右子树中，即满足要求。 n（n 0） 的二叉排序树的最小高度为 ，最大高度为 。B.C.D. (2).A nBC分数： 2.50 ）DA. B.C.D.，这是理想平衡树的情形。注意，不能选C，该公式对于 n=0 不能用；最大高度为 n，最小高度为 这是单枝树的情形。7. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点 （分数： 2.50 ）A. 左指针一定为空B. 右指针一定为空 C. 左右指针均为空D. 左右指针均不为空在二叉排序树的存储结构中， 每个结点由三部分构成， 其中左 （或右）指针指向比结点的关键字

11、值小 （或大） 的结点。 关键字值最大的结点位于二叉排序树的最右下位置上，它的右指针一定为空 （ 注意，有可能不是叶结点 ） 。8. 在下列关于平衡二叉树的说法中正确的是 。（分数： 2.50 ）A. 任意结点的左、右子树结点数目相同B. 任意结点的左、右子树高度相同C. 任意结点的左、右子树高度之差的绝对值不大于 1 D. 不存在度为 1 的结点 平衡二叉树的定义。具有 5层结点的平衡二叉树至少有 个结点。若设树根结点在第 1 层，则深度最小的叶结点应在第层。A. 10B. 12 C. 15D. 17A. 1B. 2C. 3 D. 4若设高度为 h 的平衡二叉树的最少结点数为 N h ，则有

12、：N 0 =0 ， 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 1 =1 ， L 2 =2 ， L h =minL h-1 ， L h-2 +1=L h-2 +1 ， h 29. 设 F是一个森林， B是

13、由 F转换得到的二叉树， F中有 n 个非叶结点，则 B中右指针域为空的结点个数是（分数： 2.50 ）A. n-1B. .nC. n+1 D. n+2F 的每个非叶结点在其二叉树表示 B中有一个子女 （ 兄弟 ）链，每个链最后一个兄弟的右指针为空，而F 的各棵树链在一个兄弟链上，最后一棵树的根结点的右指针为空。所以，总共有 n+1 个空的右指针域。 若设一棵树具有 n 个结点，则它所有结点的度数之和为 。设森林 F 对应的二叉树为 B，它有 m个结点。 B的根为 p，p的右子树中结点个数为 n，则森林 F中第一棵树的结点个数是 。如果 T 2 是由有序树 T转换成的二叉树，那么 T中结点的后

14、序遍历顺序对应 T 2中结点的 遍历顺序。 （分数： 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 的后序

15、遍历顺序对应 T 2 的中序遍历顺序。10. 下面关于 Huffman 树的说法中不正确的是 。(分数： 2.50 )A. 对应一组权值构造出来的 Huffman 树一般不是唯一的B. Huffman 树具有最小的带权路径长度C. Huffman 树中没有度为 1 的结点D. Huffman 树中除了度为 1 的结点之外，还有度为 2 的结点和叶子结点Huffman 树只有度为 0 的结点和度为 2 的结点。度为 0 的结点是外部结点，带有权值。11. 二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是 。(分数： 2.50 )A. 先序遍历二叉树B. 判断两个指定位置的结点是否在

16、同一层上 C. 层次遍历二叉树D. 根据结点的值查找其存储位置选项 A、C、D运算的时间复杂度都是 O(n) ，而选项 B 的运算的时间复杂度为 O(1) ，因为对于指定位置 p 和q的两个结点，判断是否在同一层上，只需判断两者|log 2 p|=|log 2 q| 是否成立。12. 以下叙述不正确的是 。(分数： 2.50 )A. 后序线索二叉树是不完善的，要对它进行遍历，不需使用栈B. 任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈 C. 任何一棵二叉树都可以不用栈实现先序线索树的先序遍历D. 任何一棵二叉树都可以不用栈实现中序线索树的中序遍历B 不需要使用栈。13. 在平衡二叉树中

17、插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知 A 的左孩子的平衡因子为 0，右孩子的平衡因子为 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- 树的叶结点必须

18、在同一层(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；中序序列为： 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)高度是 5。度为 0 的结点个数为 4；度为 1 的结点个数为 5；度为 2 的结点个数为 3。设二叉树根结点所在层次为 0，树的深度 d 为距离根最远的叶结点所在层次，试回答以下问题：(分数： 9.00 )(1). 试精确给出深度为 d 的完全二叉树的不同二叉树棵数(分数： 4.50 ) 这与教材上讲的根结点所在层次为 1 的情形相比，深度差 1。在第 d层最多有 2 d 个结点。因此，深度为 d 的不同完全二叉树