【计算机类职业资格】数据库系统工程师-数据结构与算法(一)及答案解析.doc

《【计算机类职业资格】数据库系统工程师-数据结构与算法(一)及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】数据库系统工程师-数据结构与算法(一)及答案解析.doc（34页珍藏版）》请在麦多课文档分享上搜索。

1、数据库系统工程师-数据结构与算法(一)及答案解析(总分：73.00，做题时间：90 分钟)1.若一个具有 n 个结点、k 条边的非连通无向图是一个森林(nk)，则该森林中必有 (63) 棵树。（分数：1.00）A.kB.nC.n-kD.n+k二叉树的前序、中序和后序遍历法最适合采用 (49) 来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为 (50) ，而使上述路径长度总和达到最小的树称为 (51) ，它一定是 (52) 。在关于树的几个叙述中，只有 (53) 是正确的。（分数：5.00）A.递归程序B.迭代程序C.队列操作D.栈操作A.路径和B.内部路径长度C.总深度D.深度和A

2、.B 树B.B+树C.丰满树D.穿线树A.B 树B.平衡树C.非平衡树D.穿线树A.用指针方式存储有 n 个结点的二叉树，至少要有 n+1 个指针B.m 阶 B 树中，每个非叶子结点的后件个数大于等于C.m 阶 B 树中，具有 k 个后件的结点，必含有 k-1 个键值D.平衡树一定是丰满树在图 4-14 中， (39) 是非简单图， (40) 是完全图， (41) 和 (42) 都是哈密尔顿图，其中 (41) 又是欧拉图， (43) 是树。（分数：5.00）A.B.C.D.E.F.A.B.C.D.E.F.A.B.C.D.E.F.A.B.C.D.E.F.A.B.C.D.E.F.设栈 s 和队列

3、q 的初始状态为空，元素 a、b、c、d、e 依次进入栈 s，当一个元素从栈中出来后立即进入队列 q。若从队列的输出端依次得到元素 c、d、b、a、e，则元素的出栈顺序是 (12) ，栈 s 的容量至少为 (13) 。（分数：2.00）A.a、b、c、d、eB.e、d、c、b、aC.c、d、b、a、eD.e、a、b、d、cA.2B.3C.4D.52.若广义表 L(1，2，3)，则 L 的长度和深度分别为 (4) 。（分数：1.00）A.1 和 1B.1 和 2C.1 和 3D.2 和 23.任何一个基于“比较”的内部排序算法，若对 6 个元素进行排序，则在最坏情况下所需的比较次数至少为 (65

4、) 。（分数：1.00）A.10B.11C.21D.364.堆是一种数据结构， (2) 是堆。（分数：1.00）A.(10，50，80，30，60，20，15，18)B.(10，18，15，20，50，80，30，60)C.(10，15，18，50，80，30，60，20)D.(10，30，60，20，15，18，50，80)5.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为 (8) 。（分数：1.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA一棵二叉排序树可顺序存放在一组物理上相邻的存储区中，每个结点及左、右指针依次分别放在该

5、存储区的 3 个连续单元中。现对一棵结点按字母的字典顺序构成的二叉排序树从根结点户开始顺序放在一个存储区中，结果如图 4-13 所示。其中 Li为第 i 个结点的左指针，R i为第 i 个结点的右指针，则 L2应为 (34) ，L 4应为 (35) ，R 1应为 (36) 。该二叉排序树的前序遍历序列为 (37) ，后序遍历序列为 (38) 。1000 P1001 L11002 R11003 B1004 L21005 R21006 Q1007 L31008 R31009 H100A L4100B R4100C C100D L5100E R5100F J10010 L610011 R6图 4-1

6、3 二叉排序树的存储（分数：5.00）A.1003B.1004C.100AD.1009E.1006F.1000G.100CH.100FI.NullA.1003B.1004C.100AD.1009E.1006F.1000G.100CH.100FI.NullA.1003B.1004C.100AD.1009E.1006F.1000G.100CH.100FI.NullA.PBQHCJB.PBHCJQC.BCHJPQD.CJHBQPE.BHCJQPA.PBQHCJB.PBHCJQC.BCHJPQD.CJHBQPE.BHCJQP6.若一棵哈夫曼树共有 9 个顶点，则其叶子结点的个数为 (69) 。（分数：

7、1.00）A.4B.5C.6D.7在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有 (59) 的二叉树，这是一种采用了 (60) 的算法。（分数：2.00）A.前缀码B.最优前缀码C.后缀码D.最优后缀码A.贪心B.分治C.递推D.回溯7.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素 30 要进行 (10) 次元素间的比较。（分数：1.00）A.4B.5C.6D.78.表达式 a*(b+c)-d 的后缀表达形式为 (7) 。（分数：1.00）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*

8、abcd9.循环链表的主要优点是 (6) 。（分数：1.00）A.不再需要头指针了B.已知某个结点的位置后，能很容易地找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表10.一个具有 767 个结点的完全二叉树，其叶子结点个数为 (62) 。（分数：1.00）A.383B.384C.385D.38611.表达式“XA+B(C-D)/E”的后缀表示形式可以为 (11) (运算符优先级相同时，遵循左结合的原则)。（分数：1.00）A.XAB+CDE/-B.XA+BC-DE/C.XABCD-xE/+D.XABCDE+x-/12.已知有一维数组 A0，mn

9、-1，若要对应为 m 行、n 列的矩阵，则下面的对应关系 (73) 可将元素 Ak(0kmn)表示成矩阵的第 i 行、第 j 列的元素(0im， 0jn)。（分数：1.00）A.i=k/n，j=k%mB.i=k/m，jk%mC.i=k/n，j=k%nD.i=k/m，j=k%n13.关键路径是指 AOE(Activity on Edge)网中 (61) 。（分数：1.00）A.最长的回路B.最短的回路C.从源点到汇点(结束顶点)的最长路径D.从源点到汇点(结束顶点)的最短路径在查找算法中，可用平均查找长度(记为 ASL)来衡量一个查找算法的优劣，其定义为：（分数：5.00）A.O(1)B.O(l

10、og2n)C.O(log2n2)D.O(nlog2n)E.O(n)F.O(n2)A.O(1)B.O(log2n)C.O(log2n2)D.O(nlog2n)E.O(n)F.O(n2)A.O(1)B.O(log2n)C.O(log2n2)D.O(nlog2n)E.O(n)F.O(n2)A.O(1)B.O(log2n)C.O(log2n2)D.O(nlog2n)E.O(n)F.O(n2)A.O(1)B.O(log2n)C.O(log2n2)D.O(nlog2n)E.O(n)F.O(n2)14.若循环队列以数组 Q0，m-1作为其存储结构，变量 rear 表示循环队列中队尾元素的实际位置，其移动按

11、rear=(rear+1)mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 (67) 。（分数：1.00）A.rear-lengthB.(rear-length+m)mod mC.(1+rear+m-length)mod mD.m-length15. (66) 的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。（分数：1.00）A.树形存储结构B.链式存储结构C.索引存储结构D.散列存储结构16.若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 至少有 (64) 个顶点。（分数：1.00）A.11B.

12、10C.9D.8给定数据结构(V，E)，V 为结点的有限集合，VV 1，V 2，V 3，V 4，V 5，V 6，V 7，V 8)，E 是 V 上关系的集合。EV 1，V 2，V 3，V 4，V 5，V 8，V 5，V 6，V 1，V 3，V 4，V 7，V 4，V 5，V 2，V 4，V 4，V 6)，它所对应的图形是 (44) ，这是 (45) 。图的存储结构主要有邻接表和 (46) ，若用邻接表来存储一个图，则需要保存一个 (47) 存储的结点表和若干个 (48) 上存储的关系表(又称边表)。（分数：5.00）(1). （分数：1.00）A.B.C.D.A.无向树B.无向图C.有向图D.有

13、向树A.转移矩阵B.邻接矩阵C.状态矩阵D.优先矩阵A.顺序B.链接C.散列D.分块A.顺序B.链接C.散列D.索引17.若对 27 个元素只进行三趟多路归并排序，则选取的归并路数为 (5) 。（分数：1.00）A.2B.3C.4D.518.设顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找的平均查找长度为 (72) 。（分数：1.00）A.21B.23C.41D.6219.在一棵度为 3 的树中，有 2 个度为 3 的结点，有 1 个度为 2 的结点，则有 (70)

14、个度为 0 的结点。（分数：1.00）A.4B.5C.6D.720.无向图中一个顶点的度是指图中 (9) 。（分数：1.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数D.与该顶点连通的顶点数21.一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵存储结构中共有 (68) 个零元素。（分数：1.00）A.eB.2eC.n2-eD.n2-2e22. (3) 从二叉树的任一结点出发到根的路径上，所经过的结点序列必须按其关键字降序排列。（分数：1.00）A.二叉排序树B.大顶堆C.小顶堆D.平衡二叉树一棵查找二叉树，其结点 A，B，C，D，E，F 依次存放在一个

15、起始地址为 n(假定地址以字节为单位顺序编号)的连续区域中，每个结点占 4 个字节：前 2 个字节存放结点值，后 2 个字节依次放左指针、右指针。若该查找二叉树的根结点为万，则它的一种可能的前序遍历为 (54) ，相应的层次遍历为 (55) 。在以上两种遍历情况下，结点 C 的左指针 LC的存放地址为 (56) ， L C的内容为 (57) 。结点 A 的右指针凡的内容为 (58) 。（分数：5.00）A.EAFCBDB.EFACDBC.EABCFDD.EACBDFA.EAFCBDB.EFACDBC.EABCFDD.EACBDFA.n+9B.n+10C.n+12D.n+13A.n+4B.n+8

16、C.n+12D.n+16A.n+4B.n+8C.n+12D.n+1623.设结点 x 和 y 是二叉树中任意的两个结点，在该二叉树的先根遍历序列中 x 在 y 之前，而在其后根遍历序列中 x 在 y 之后，则 x 和 y 的关系是 (71) 。（分数：1.00）A.x 是 y 的左兄弟B.x 是 y 的右兄弟C.x 是 y 的祖先D.x 是 y 的后裔24.在一棵完全二叉树中，其根的序号为 1， (1) 可判声序号为 p 和 q 的两个结点是否在同一层。（分数：1.00）A.B.C.D.在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要

17、将序列 Q，H，C，Y，P，A，M，S，R，D，F， X 中的关键码按字母的升序重新排列，则 (24) 是冒泡排序一趟扫描的结果， (25) 是初始步长为 4 的希尔排序一趟扫描的结果， (26) 是两路归并(合并)排序一趟扫描的结果， (27) 是以第一个元素为分界元素的快速排序一趟扫描的结果， (28) 是堆排序初始建堆的结果。（分数：5.00）A.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.A，D，C，R，F，Q，M，S，Y，P，H，XD.H，C，P，A，M，S，R，D，F，X，YE.H，Q，C，Y，A，P，M，S，D，R，F，XA

18、.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.A，D，C，R，F，Q，M，S，Y，P，H，XD.H，C，P，A，M，S，R，D，F，X，YE.H，Q，C，Y，A，P，M，S，D，R，F，XA.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.A，D，C，R，F，Q，M，S，Y，P，H，XD.H，C，P，A，M，S，R，D，F，X，YE.H，Q，C，Y，A，P，M，S，D，R，F，XA.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.A，D

19、，C，R，F，Q，M，S，Y，P，H，XD.H，C，P，A，M，S，R，D，F，X，YE.H，Q，C，Y，A，P，M，S，D，R，F，XA.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.A，D，C，R，F，Q，M，S，Y，P，H，XD.H，C，P，A，M，S，R，D，F，X，YE.H，Q，C，Y，A，P，M，S，D，R，F，X对由 n 个记录所组成的有序关键码排序时，下列各常用排序算法的平均比较次数分别是：二路归并排序为 (29) ，冒泡排序 (30) ，快速排序为 (31) 。其中，归并排序和快速排序所需要的辅助存储分别是 (32) 和

20、(33) 。（分数：5.00）A.O(1)B.O(nlog2n)C.O(n)D.O(n2)E.O(n(log2n)2)F.O(log2n)A.O(1)B.O(nlog2n)C.O(n)D.O(n2)E.O(n(log2n)2)F.O(log2n)A.O(1)B.O(nlog2n)C.O(n)D.O(n2)E.O(n(log2n)2)F.O(log2n)A.O(1)B.O(nlog2n)C.O(n)D.O(n2)E.O(n(log2n)2)F.O(log2n)A.O(1)B.O(nlog2n)C.O(n)D.O(n2)E.O(n(log2n)2)F.O(log2n)已知某图的邻接表如图 4-12

21、 所示。（分数：5.00）(1). （分数：1.00）A.B.C.A.FGILJMKHB.FGILJKHMC.FGILJKMHD.FGHMILJKE.FGHILJKMF.FGHMKLJI(3). （分数：1.00）A.B.C.A.FGILJMKHB.FGILJKHMC.FGILJKMHD.FGHMILJKE.FGHILJKMF.FGHMKLJI(5). （分数：1.00）A.B.C.数据库系统工程师-数据结构与算法(一)答案解析(总分：73.00，做题时间：90 分钟)1.若一个具有 n 个结点、k 条边的非连通无向图是一个森林(nk)，则该森林中必有 (63) 棵树。（分数：1.00）A.k

22、B.nC.n-k D.n+k解析：分析假设该森林中有 s 棵树，分别为 T1，T 2，T s，且每个 Ti有 ni个结点，k i条边(i=1， 2，s)，由树的等价条件可知kin i-1则kk 1+k2+ks(n 1-1)+(n2-1)+(ns-1)n-s故s=n-k所以该森林中必有 n-k 棵树。另外，还可以这样考虑。首先，把 n 个单独的结点看成 n 棵树，然后再逐条加入边。显然，每加入一条边，则树的棵数就减 1(把两棵树合并成一棵树)，而题目告诉我们，总共有 k 条边，所以，树的总数为 n-k。二叉树的前序、中序和后序遍历法最适合采用 (49) 来实现。查找树中，由根结点到所有其他结点的

23、路径长度的总和称为 (50) ，而使上述路径长度总和达到最小的树称为 (51) ，它一定是 (52) 。在关于树的几个叙述中，只有 (53) 是正确的。（分数：5.00）A.递归程序 B.迭代程序C.队列操作D.栈操作解析：A.路径和B.内部路径长度 C.总深度D.深度和解析：A.B 树B.B+树C.丰满树 D.穿线树解析：A.B 树B.平衡树 C.非平衡树D.穿线树解析：A.用指针方式存储有 n 个结点的二叉树，至少要有 n+1 个指针B.m 阶 B 树中，每个非叶子结点的后件个数大于等于C.m 阶 B 树中，具有 k 个后件的结点，必含有 k-1 个键值 D.平衡树一定是丰满树解析：分析由

24、于二叉树的前序、中序和后序遍历方法都是递归定义的，所以最适合采用递归程序来实现。此外，递归程序的实现基础是栈操作，所以二叉树的遍历也可以使用栈操作来完成，但是用栈操作来实现遍历的程序逻辑结构没有递归程序那么清晰，而且用栈来实现的二叉树遍历代码比较难懂，其优点是代码的机器执行效率较高。在查找二叉树中，由根结点到所有其他结点的路径长度总和称为内部路径长度。具有最小内部路径长度的树称为丰满树，对丰满查找树进行插入或者删除操作后，会产生一棵非丰满树。为了保证查找二叉树的高度为 log2n，从而保证在查找二叉树上实现的插入、删除和查找等基本操作的平均时间为 O(log2n)，往树中插入或删除结点时，要调

25、整树的形态来保持树的“平衡”，使之既保持查找二叉树性质不变，又保证树的高度在任何情况下均为 O(log2n)，从而确保树上的基本操作在最坏情况下的时间均为 O(log2n)。平衡二叉树是指树中任一结点的左、右子树的高度大致相同，即平衡树上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近，但是在插入或者删除结点时，平衡树能动态地调整保持平衡的特点。如果任一结点的左、右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为 O(log2n)，就可看做是平衡的。平衡二叉树中任一结点的左、右子树的高度之差的绝对值不超过 1。在最坏情况下，n 个结点的平衡二叉树的高

26、度约为 1.44log2n。而完全平衡的二叉树高度约为 log2n，平衡二叉树是接近最优的。根据丰满树和平衡树的定义可知，丰满树一定是平衡树，但平衡树不一定是丰满树。m 阶 B 树是一种平衡的 m 叉树，具有如下的性质：(1)每个结点的后件(孩子)个数不大于 m。(2)除根结点和叶子结点外，每个结点的后件个数不大于*。(3)具有 k 个后件的非叶子结点含有 k-1 个键值。(4)所有叶子结点在同一层上，而且不包含任何关键字信息，不附有信息。在图 4-14 中， (39) 是非简单图， (40) 是完全图， (41) 和 (42) 都是哈密尔顿图，其中 (41) 又是欧拉图， (43) 是树。（

27、分数：5.00）A.B. C.D.E.F.解析：A. B.C.D.E.F.解析：A. B.C.D.E.F.解析：A.B. C.D.E.F.解析：A.B.C.D. E.F.解析：分析本题主要考查一些特殊图的概念，下面分别进行介绍。非简单图：既无平行边也无环的无向图称为简单无向图，有平行边或有环的图是非简单图。在本题中，只有 B 有环，其余的 5 个图都既无平行边也无环，因而(26)的答案应为 B。完全图：每个顶点度数都等于 n-1 的 n 阶无向简单图称为 n 阶无向完全图，并记为 k n。在给定的 6 个图中，只有 A 图满足要求，它是 k5，所以(27)的答案为 A。哈密尔顿图：通过连通图中

28、所有结点一次且仅一次的回路称为哈密尔顿回路，具有哈密尔顿回路的图称为哈密尔顿图。一个图是哈密尔顿图的必要条件(注意：不是充分条件)是图的连通性和图中不存在度数为 1的顶点。在本题中，E 图是分离的 k3，即 E 是非连通图，而 C、D、F 均有度数为 1 的顶点，所以C、D、E、F 都不是哈密尔顿图。 A、B 中均存在哈密尔顿回路，因而 A、B 均为哈密尔顿图。所以(28)、(29)的答案可以为 A、B。欧拉图：通过连通图(有向图或无向图)中每条边一次且仅一次遍历图中所有顶点的回路，称为欧拉回路，存在欧拉回路的图称为欧拉图。设 G 是连通图，则 G 是欧拉图，当且仅当 G 的所有顶点都是偶顶点

29、(度数为偶数的顶点)。在本题中，只有 A 连通且无奇度顶点，因而 A 为欧拉图，在其余各图中，E 无奇度顶点，但它不连通，所以不是欧拉图。而 B、C、D、F 中都有奇度顶点，因而它们也不是欧拉图，所以(28)的答案为 A，(29)的答案为 B。树：连通且无回路的无向图称为无向树。在本题中，只有 D 满足要求，其余 5 个图中均有回路，因而都不是树，(30)的答案为 D。另外，还有一些特殊的图，我们也简单介绍一下。平面图：平面图是指一个图能画在平面上，除顶点之外，再没有边与边相交。在本题中，B、C、D、F 为平面图。二部图：若能将无向图的顶点集 V 划分成两个子集 V1和 V2，使得 G 中任何

30、一条边的两个端点一个属于V1，另一个属于 V2，则称 G 为二部图(也称为偶图)。在本题中， D 为二部图。设栈 s 和队列 q 的初始状态为空，元素 a、b、c、d、e 依次进入栈 s，当一个元素从栈中出来后立即进入队列 q。若从队列的输出端依次得到元素 c、d、b、a、e，则元素的出栈顺序是 (12) ，栈 s 的容量至少为 (13) 。（分数：2.00）A.a、b、c、d、eB.e、d、c、b、aC.c、d、b、a、e D.e、a、b、d、c解析：A.2B.3 C.4D.5解析：分析(1)队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插

31、入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列具有先进先出(FIFO)的特点。队列空的条件：frontrear队列满的条件：rearMAXSIZE队列可以用数组 Q1m来存储，数组的上界 m 即是队列所允许的最大容量。在队列的运算中需设两个指针：head，队头指针，指向实际队头元素的前一个位置；tall，队尾指针，指向实际队尾元素所在的位置。一般情况下，两个指针的初值设为 0，这时队列为空，没有元素。队列中拥有的元素个数为：L=tail-head。现在要让排头的元素出队，则需将头指针加 1。如果想让一个新元素入队，则需将尾指针向上移动一个位置。(

32、2)栈是一种只能在叫做栈的一段进行进栈或者出栈操作的线性数据结构。栈的主要特点是“后进先出”，即后进栈的元素先处理。通常栈用顺序表存储，分配一块连续的内存区域存放栈中的元素，并用一个变量指向当前的栈顶。栈的基本操作：置空栈 initStack(s)：设置一个空栈 s。进栈 push(s,x)：将元素 x 进到栈 s 中，栈指针递增。pop(s,x)：将栈 s 的栈顶元素赋给 x，栈指针递减。判断栈空 stackempty(s)：若栈为空，返回 1，否则返回 0。根据队列的特点，从队列的输出端依次得到元素 c、d、b、a、e，则在从队列的输入端应依次输入元素c、d、b、a、e，则元素的出栈顺序是

33、 c、d、b、a、e，由于 C 是第一个出栈，而 C 是第三个出栈，所以栈 s 的容量至少为 3。2.若广义表 L(1，2，3)，则 L 的长度和深度分别为 (4) 。（分数：1.00）A.1 和 1B.1 和 2 C.1 和 3D.2 和 2解析：分析广义表一般记作LS(a1，a2，an)其中 n 是它的长度，ai 可以是单个元素(原子)，也可以是广义表(子表)，当广义表非空时，称第一个元素 a1 为 LS 的表头，称其余元素组成的表为 LS 的表尾。注意：表头是元素(可以是原子，也可以是广表)，而表尾一定是广义表。例如：C(a)，a)的表头是(a)，表尾是(a)。(a)的表头是(a)，表尾

34、是()。广义表的深度定义为所含括弧的重数。注意：原子的深度为 0，空表的深度为 1。例如：E(a，E)是一个递归的广义表，长度为 2，深度为 1。D()，(e)，(a，(b，c，d)是多层次的广义表，长度为 3，深度为 3。3.任何一个基于“比较”的内部排序算法，若对 6 个元素进行排序，则在最坏情况下所需的比较次数至少为 (65) 。（分数：1.00）A.10 B.11C.21D.36解析：分析基于关键字的比较操作排序方法，其排序过程均可以利用判定树来描述。判定树上所有叶子结点恰好表示所有排序结果，每个初始序列经过排序达到有序所需要进行的比较次数，正好等于从树根到和该序列相应的叶子结点的路径

35、长度。由于含 n 个记录的序列可能出现的初始状态有 n!个，则描述 n 个记录排序过程的判定树必须有 n!个叶结点。因为，若少一个叶结点，则说明尚有两种状态没有分辨出来。由于若二叉树高度为 h，则叶子结点的个数不超过 2h-1个；反之，若有 u 个结点，则二叉树的高度至少为*。因此，描述 n 个记录排序的判定树上必定存在一条长度为*的路径。由此可知：任何一个借助比较进行排序的算法，在最坏情况下所需进行比较次数至少为*。在本题中，n=6，因此，*，因此，正确的答案为 10 次。4.堆是一种数据结构， (2) 是堆。（分数：1.00）A.(10，50，80，30，60，20，15，18)B.(10

36、，18，15，20，50，80，30，60) C.(10，15，18，50，80，30，60，20)D.(10，30，60，20，15，18，50，80)解析：分析一个有 n 个元素的序列k 1，k 2，k n)如果满足*则称为小顶堆：如果满足*则称为大顶堆。由堆的定义可以看出，在大顶堆中，第 1 个元素是所有元素的最大值。在小顶堆中，第 1 个元素是所有元素的最小值。根据这个定义，从给定的 4 个选项来看，如果是堆的话，一定是小顶堆，因为第 1 个元素 10 是所有元素中最小的元素。首先看选项 A。第 1 个元素小于第 2 个元素 50 和第 3 个元素 80，第 2 个元素 50 大于第

37、4 个元素 30，因此不是堆。按照这种方式，考察所有选项，可以得出 B 是堆。其对应的树形表示如图 4-1 所示。*5.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为 (8) 。（分数：1.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA 解析：分析本题要求根据二叉树的先序遍历和中序遍历求后序遍历。我们可以根据这棵二叉树的先序和中序遍历画出这棵二叉树，然后再得出其后序遍历结果。根据先序和中序来构造二叉树的规则是这样的：首先看先序遍历序列 ABDECF，先序遍历中第一个访问的结点是 A，这说明 A 是二叉树的根结点(因为先序遍历顺序

38、是：根，左，右)。然后看中序遍历序列 DBEAFC，中序中 A 前面有结点 DBE，后面有结点 FC。这说明 DBE 是 A 的左子树，FC 是 A 的右子树(因为中序遍历顺序是：左，根，右)。再回到先序遍历序列中看 DBE 的排列顺序(此时可以不看其他的结点)，我们发现在先序遍历序列中 B 排在最前面，所以 B 是 A 的左子树的根结点。接下来又回到了中序遍历序列，中序遍历序列中 D 在 B 的前面，E 在 B 的后面，所以 D 是 B 的左子树，E是 B 的右子树。对于 A 的右子树，可同样依此规则得出。由此，可构造二叉树，如图 4-8 所示。*然后对这棵二叉树进行后序遍历，得到 DEBF

39、CA。一棵二叉排序树可顺序存放在一组物理上相邻的存储区中，每个结点及左、右指针依次分别放在该存储区的 3 个连续单元中。现对一棵结点按字母的字典顺序构成的二叉排序树从根结点户开始顺序放在一个存储区中，结果如图 4-13 所示。其中 Li为第 i 个结点的左指针，R i为第 i 个结点的右指针，则 L2应为 (34) ，L 4应为 (35) ，R 1应为 (36) 。该二叉排序树的前序遍历序列为 (37) ，后序遍历序列为 (38) 。1000 P1001 L11002 R11003 B1004 L21005 R21006 Q1007 L31008 R31009 H100A L4100B R41

40、00C C100D L5100E R5100F J10010 L610011 R6图 4-13 二叉排序树的存储（分数：5.00）A.1003B.1004C.100AD.1009E.1006F.1000G.100CH.100FI.Null 解析：A.1003B.1004C.100AD.1009E.1006F.1000G.100C H.100FI.Null解析：A.1003B.1004C.100AD.1009E.1006 F.1000G.100CH.100FI.Null解析：A.PBQHCJB.PBHCJQ C.BCHJPQD.CJHBQPE.BHCJQP解析：A.PBQHCJB.PBHCJQC

41、.BCHJPQD.CJHBQP E.BHCJQP解析：分析解答本题最关键的一步是要构造出与题目对应的二叉树，可以利用的条件有 4 个：二叉排序树、顺序存放、根结点 P，以及存储结构图中出现的结点关键字。构造树的过程是这样的： 首先画出根结点 P，然后在存储结构图 4-13 中找出下一个结点关键字 B(因为题目告诉我们，二叉排序树是顺序存放在一组物理上相邻的存储区中的)，由于 BP，所以 B 以左子结点的身份加入排序二叉树；接着从结构图中找下一个结点关键字 Q，Q P，所以 Q 以右子结点的身份加入排序二叉树。接下来的结点是 H，因为 HP，则 H 在 P 的左子树中，又因为 HB，所以 H 最

42、终作为 B 的右子树。再下一个结点是巴同理，因为 CP，CB，CH，则 C 最终作为 H 的左子树。最后一个结点是J，JP，JB，JH，则 J 最终作为 H 的右子树。得到的二叉排序树如图 4-19 所示。*由图 4-19 可得出，L 2指向 Null；L 4指向巴即 100C；R 1指向 Q，即 1006；该二叉排序树的前序遍历序列为 PBHCJQ，后序遍历序列为 CJHBQP。6.若一棵哈夫曼树共有 9 个顶点，则其叶子结点的个数为 (69) 。（分数：1.00）A.4B.5 C.6D.7解析：分析哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树

43、称为哈夫曼树。具体过程请读者参考本节练习 10 的分析。从哈夫曼树的构造过程可知，哈夫曼树是严格的二叉树(即没有度数为 1 的分支结点)。设哈夫曼树的 0 度结点(即叶子结点)个数为 n0，2 度结点个数为 n2，则哈夫曼树的总结点数 nn 0+n2。又因为对任何一棵二叉树，如果其叶子结点数为 n0，度为 2 的结点数为 n2，则 n 0n 2+1。所以n=n2+1+n2。即 9=n2+1+n2，故 n24，n 0=5。在数据压缩编码的应用中，哈夫曼(Huffman)算法可以用来构造具有 (59) 的二叉树，这是一种采用了 (60) 的算法。（分数：2.00）A.前缀码B.最优前缀码 C.后缀

44、码D.最优后缀码解析：A.贪心 B.分治C.递推D.回溯解析：分析给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉 20%至 90%，其压缩效率取决于被压缩文件的特征。在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心

45、算法。哈夫曼树的具体构造过程如下：假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。n 个权值分别设为 w1， w 2，w n，则哈夫曼树的构造规则为：(1)将 w1，w 2，w n看成是有 n 棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取两棵树，并将新树加入森林；(4)重复第(2)和(3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。7.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查

46、找元素 30 要进行 (10) 次元素间的比较。（分数：1.00）A.4B.5 C.6D.7解析：分析首先，利用逐点插入法对给出的序列建立排序二叉树，如图 4-11 所示。从图 4-11 中我们可以看出，要查找元素 30，其步骤如下：(1)首先，要与 50 比较，因为 3050，所以进入结点 50 的左子树；(2)接着，与 43 比较，因为 3043，所以进入结点 43 左子树；(3)然后，与 20 比较，3020 所以进入结点 20 的右子树；(4)再和 35 比较，因为 3035，所以进入结点 35 的左子树；(5)最后与 30 比较，结果相等，查找结束。所以此查找过程要进行 5 次比较。

47、*8.表达式 a*(b+c)-d 的后缀表达形式为 (7) 。（分数：1.00）A.abcd*+-B.abc+*d- C.abc*+d-D.-+*abcd解析：分析题目要求根据已知的表达式写对应后缀表达式。解这种题，如果考生知道了前缀、中缀、后缀表达式有何关联，有什么特点，那么解题就非常轻松了。其实前缀、中缀、后缀的得名，是从二叉树而来的，也就是把一个表达式转化为一棵二叉树后，对二叉树进行前序遍历得到前缀表达式，对二叉树进行中序遍历得到中缀表达式(也就是一般形式的表达式)，对二叉树进行后序遍历得到后缀表达式。因此，我们只要把表达式转换成二叉树的形式，再对二叉树进行后序遍历，即可得到正确答案。但

48、现在最主要的问题是如何构造这棵树。构造的规则是这样的，所有的操作数只能在叶子结点上，操作符是它们的根结点，括号不构造到二叉树中去，构造树的顺序要遵循运算的顺序。在表达式 a*(b+c)-d 中最先计算 b+c，所以先构造图 4-5 的部分。*然后，把 b+c 的结果与。进行运算，所以有图 4-6 所示的结果。*最后，把运算结果和 d 相减，最终得到的二叉树如图 4-7 所示。*对图 4-7 的二叉树进行后序遍历得到序列 abc+*d-，所以正确答案应是 B。9.循环链表的主要优点是 (6) 。（分数：1.00）A.不再需要头指针了B.已知某个结点的位置后，能很容易地找到它的直接前驱结点C.在进

49、行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表 解析：分析本题考查循环链表的基础知识，所以我们来了解一下什么是循环链表。一个带头结点的线性链表如图 4-3所示。*若将此链表的最后一个结点 d 的 next 域指向头结点，则形成了循环链表，如图 4-4 所示。*对照图 4-4，我们现在来分析题目的备选答案。选项 A“不再需要头指针了”，言下之意就是线性链表一定需要头指针，但实际上不管是非循环的线性链表还是循环链表，头指针都是可要可不要的，所以选项 A错误。再来看 B 选项，“已知某个结点的位置后，能很容易地找到它的直接前驱结点”，题目中只说是循环链表，没有说是双向的循环链表，在单向循环链表中，已知某个结点的位置很难得到它的直接前驱结点，所以 B选项不对。接着看 C 选项，“在进行删除操作后，能保证链表不断开”。在进行结点删除操作后，原则上链表都是断开的，关键是靠