【计算机类职业资格】软件设计师-数据结构及答案解析.doc

《【计算机类职业资格】软件设计师-数据结构及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】软件设计师-数据结构及答案解析.doc（27页珍藏版）》请在麦多课文档分享上搜索。

1、软件设计师-数据结构及答案解析(总分：75.00，做题时间：90 分钟)1.一个具有 n(n0)个顶点的连通无向图至少有 (33) 条边。（分数：1.00）A.n+1B.nC.n/2D.n-12.若对 27 个元素只进行三趟多路归并排序，则选取的归并路数为 (62) 。（分数：1.00）A.2B.3C.4D.53. (55) 在其最好情况下的算法时间复杂度为 O(n)。（分数：1.00）A.插入排序B.归并排序C.快速排序D.堆排序给定节点的关键字序列(F,B,J,G,E,A,I,D,C,H)，对它按字母的字典顺序进行排列。采用不同方法，其最终结果相同，但中间结果是不同的。Shell 排序的第

2、一趟扫描(步长为 5)结果应为 (72) 。冒泡排序(大数下沉)的第一趟起泡的效果是 (73) 。快速排序的第一趟结果是 (74) 。二路归并排序的第一趟结果是 (75) 。（分数：4.00）A.(B, F, G, J, A, D, I, E, H, C)B.(B, F, G, J, A, E, D, I, C, H)C.(A, B, D, C, E, E, I, J, G, H)D.(C, B, D, A, E, F, I, G, J, H)A.(A, B, D, C, P, E, I, J, H, G)B.(A, B, D, C, E, F, I, H, G, J)C.(B, P, G,

3、E, A, I, D, C, H, J)D.(B, F, G, J, A, E, D, I, C, H)A.(C, B, D, A, P, E, I, J, G, H)B.(C, B, D, A, E, F, I, G, J, H)C.(B, A, D, E, F, G, I, J, H, C)D.(B, C, D, A, E, F, I, J, G, H)A.(B, F, G, J, A, E, D, I, C, H)B.(B, A, D, E, F, G, I, J, H, C)C.(A, B, D, C, E, F, I, J, G, H)D.(A, B, D, C, P, E, J,

4、I, H, C)4.若广义表 L(1，2，3)，则 L 的长度和深度分别为 (3) 。（分数：1.00）A.1 和 1B.1 和 2C.1 和 3D.2 和 25.拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系， (26) 为图 8-7 所示有向图的一个拓扑序列。（分数：1.00）A.1 2 3 4 5 6 7B.1 5 2 6 3 7 4C.5 1 2 6 3 4 7D.5 1 2 3 7 6 4为在状态空间树中 (34) ，可以利用 LC-检索(Least Cost Search)快速找到一个答案节点。在进行 LC-检索时，为避免算法过

5、分偏向于作纵深检查，应该 (35) 。（分数：2.00）A.找出任一个答案节点B.找出所有的答案节点C.找出最优的答案节点D.进行遍历A.使用精确的成本函数 c(.)来作 LC-检索B.使用广度优先检索C.使用深度优先检索D.进行遍历6.表达式 a*(b+c)-d 的后缀表达形式为 (10) 。（分数：1.00）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd7.在 (48) 存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。（分数：1.00）A.顺序(Sequence)B.链表(Link)C.索引(1ndex)D.散列(Hash)8.堆是一种数据结构

6、， (60) 是堆。（分数：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)9. (61) 从二叉树的任一节点出发到根的路径上，所经过的节点序列必按其关键字降序排列。（分数：1.00）A.二叉排序树B.大顶堆C.小顶堆D.平衡二叉树10.在 11 个元素的有序表 A111)中进行折半查找L(low+high)/2，查找元素 A11时，被比较的元素的下标依次是 (49) 。（分数：1.00）A.6，8，10，11B.6，

7、9，10，11C.6，7，9，11D.6，8，9，1111.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为 (11) 。（分数：1.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA12.设节点 x 和 y 是二叉树中任意的两个节点，在该二叉树的先根遍历序列中 x 在 y 之前，而在其后根遍历序列中 x 在 y 之后，则 x 和 y 的关系是 (17) 。（分数：1.00）A.x 是 y 的左兄弟B.x 是 y 的右兄弟C.x 是 y 的祖先D.x 是 y 的后裔13.在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序

8、方法是 (58) 。（分数：1.00）A.基数排序B.快速排序C.堆排序D.归并排序一棵查找二叉树，其节点 A，B，C，D，E，F 依次存放在一个起始地址为 n(假定地址以字节为单位顺序编号)的连续区域中，每个节点占 4 字节，前二字节存放节点值，后二字节依次放左指针、右指针。若该查找二叉树的根节点为 E，则它的一种可能的前序遍历为 (20) ，相应的层次遍历为 (21) 。在以上两种遍历情况下，节点 c 的左指针 LC 的存放地址为 (22) ，LC 的内容为 (23) 。节点 A 的右指针 RA的内容为 (24) 。（分数：5.00）A.EAFCBDB.EFACDBC.EABCFDD.EA

9、CBDFA.EAFCBDB.EFACDBC.EABCFDD.EACBDFA.n+9B.n+10C.n+12D.n+13A.n+4B.n+8C.n+12D.n+16A.n+4B.n+8C.n+12D.n+1614. (51) 的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。（分数：1.00）A.树形存储结构B.链式存储结构C.索引存储结构D.散列存储结构15.已知一个线性表(38，25，74，63，52，48)，假定采用散列函数 h(key)=key%7 计算散列地址，并散列存储在散列表 A06中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (5

10、0) 。（分数：1.00）A.1.5B.1.7C.2.0D.2.316.若循环队列以数组 QOm-1作为其存储结构，变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 (2) 。（分数：1.00）A.rear-lengthB.(rear-length+m) mod mC.(1+rear+m-length) mod mD.m-length17.无向图中一个顶点的度是指图中 (32) 。（分数：1.00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶

11、点相邻接的顶点数D.与该顶点连通的顶点数18.关键路径是指 AOE(Activity On Edge)网中 (38) 。（分数：1.00）A.最长的回路B.最短的回路C.从源点到汇点(结束顶点)的最长路径D.从源点到汇点(结束顶点)的最短路径19.若一个具有 n 个节点、k 条边的非连通无向图是一个森林(nk)，则该森林中必有 (19) 棵树。（分数：1.00）A.kB.nC.n-kD.n+k20.以下序列中不符合堆定义的是 (63) 。（分数：1.00）A.(102，87，100，79，82，62，84，42，22，12，68)B.(102，100，87，84，82，79，68，62，42，

12、22，12)C.(12，22，42，62，68，79，82，84，87，100，102)D.(102，87，42，79，82，62，68，100，84，12，22)21.在常用的描述二叉排序树的存储结构中，关键字值最大的节点 (12) 。（分数：1.00）A.左指针一定为空B.右指针一定为空C.左右指针均为空D.左右指针均不为空22.已知有一维数组 A(0m*n-1，若要对应为 m 行、n 列的矩阵，则下面的对应关系 (4) 可将元素 Ak(0km*n)表示成矩阵的第 i 行、第 j 列的元素(0im，0jn)。（分数：1.00）A.i=k/n,j=k%mB.i=k/m,j=K%mC.i=k/

13、n,j=k%nD.i=k/m,j=k%n23.由权值为 9，2，5，7 的四个叶子构造一棵哈夫曼树，该树的带权路径长度为 (13) 。（分数：1.00）A.23B.37C.44D.4624.对 n 个元素进行快速排序时，最坏情况下的时间复杂度为 (65) 。（分数：1.00）A.O(log2n)B.O(n)C.O(nlog2/t)D.O(n2)对于给定的一组关键字(12,2,16,30,8,28,4,10,20,6,18)，按照下列算法进行递增排序，写出每种算法第一趟排序后得到的结果：希尔排序(增量为 5)得到 (67) ，快速排序(选第一个记录为基准元素)得到 (68) ，链式基数(基数为

14、10 排)序得到 (69) ，二路归并排序得到 (70) ，堆排序得到 (71) 。（分数：5.00）A.2,4,6,8,10,12,16,18,20,28,30B.6,2,10,4,8,12,28,30,20,16,18C.12,2,10,20,6,18,4,16,30,8,28D.30,10,20,12,2,4,16,6,8,28,18A.10,6,18,8,4,2,12,20,16,30,28B.6,2,10,4,8,12,28,30,20,16,10C.2,4,6,8,10,12,16,18,20,28,30D.6,10,8,28,20,18,2,4,12,30,16A.10,6,18

15、,8,4,2,12,20,16,30,28B.1,12,10,20,6,18,4,16,30,8,28C.2,4,6,8,10,12,16,18,20,28,30D.30,10,20,12,2,4,16,6,8,28,18A.2,12,16,8,28,30,4,6,10,18,20B.2,12,16,30,8,28,4,10,6,20,18C.12,2,16,8,28,30,4,6,10,28,18D.12,2,10,20,6,18,4,16,30,8,28A.30,28,20,12,18,16,4,10,2,6,8B.20,30,28,12,18,4,16,10,2,8,6C.2,6,4,1

16、0,8,28,16,30,20,12,18D.2,4,10,6,12,28,16,20,8,30,18简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个节点，其邻接矩阵为A1n, 1n，且压缩存储在 B1k中，则 k 的值至少为 (30) 。若按行压缩存储对称矩阵的上三角元素，则当 n 等于 10 时，边(V 6，V 3)的信息存储在 B (31) 中。（分数：2.00）A.n(n+1)/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/2A.18B.19C.20D.21己知 AOE 网中顶点 v1v7 分别表示 7 个事件，弧 a1a10 分别表示 10

17、个活动，弧上的数值表示每个活动花费的时间，如图 8-9 所示。那么，该网的关键路径的长度为 (40) ，活动 a6 的松弛时间(活动的最迟开始时间活动的最早开始时间)为 (41) 。（分数：2.00）A.7B.9C.10D.11A.3B.2C.1D.0类比二分搜索算法，设计 k 分搜索算法(k 为大于 2 的整数)如下：首先检查 n/k 处(n 为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查 2n/k 处的元素这样，或者找到要搜索的元素，或者把集合缩小到原来的 1/k；如果未找到要搜索的元素，则继续在得到的集合上进行 k 分搜索；如此进行，直到找到要搜索的元素或搜索失败。此 k 分

18、搜索算法在最坏情况下搜索成功的时间复杂度为 (53) ，在最好情况下搜索失败的时间复杂度为 (54) 。（分数：2.00）A.O(logn)B.O(nlogn)C.O(logkn)D.O(nlogkn)A.O(logn)B.O(nlogn)C.O(logkn)D.O(nlogkn)25.某工程计划图如图 8-6 所示，弧上的标记为作业编码及其需要的完成时间(天)，作业 E 最迟应在第 (25) 天开始。（分数：1.00）A.7B.9C.12D.1326.若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。 (56) 排序是稳定的。（分数：1.00）A.归并B.快速C.希尔D.堆

19、27.在一棵完全二叉树中，其根的序号为 1， (14) 可判定序号为 p 和 q 的两个节点是否在同一层。（分数：1.00）A.logp=log2q)B.log2 p=log2 qC.log2 p+1=log2q)D.log2 p=log2 q)+128.已知某二叉树的中序、层序序列分别为 DBAFCE，FDEBCA，则该二叉树的后序序列为 (7) 。（分数：1.00）A.BCDEAFB.ABDCEFC.DBACEFD.DABECF29.由元素序列 27，16，75，38，51 构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入节点最近且平衡因子的绝对值为 2 的节点)为 (9) 。（分

20、数：1.00）A.27B.38C.51D.7530.设顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索引表采用顺序查找方法来确定子块，且在确 (52) 。（分数：1.00）A.21B.23C.41D.6231.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素 30 要进行 (57) 次元素间的比较。（分数：1.00）A.4B.5C.6D.732.以比较为基础的排序算法在最坏情况下的计算时间下界为 (59) 。（分数：1.00）A.O(n)B.O(n2)C.O(logn)D.O(nlogn)33.在一棵

21、度为 3 的树中，若有 2 个度为 3 的节点，有 1 个度为 2 的节点，则有 (16) 个度为 0 的节点。（分数：1.00）A.4B.5C.6D.734.若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 至少有 (39) 个顶点。（分数：1.00）A.11B.10C.9D.835.给定一个有 n 个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动 (47) 个元素。（分数：1.00）A.(n+1)/2B.n/2C.(n-1)/2D.136.若一棵哈夫曼(Huffman)树共有 9 个顶点，则其叶子节点的个数为 (15) 。

22、（分数：1.00）A.4B.5C.6D.737.循环链表的主要优点是 (1) 。（分数：1.00）A.不再需要头指针了B.已知某个节点的位置后，能很容易找到它的直接前驱节点C.在进行删除操作后，能保证链表不断开D.从表中任一节点出发都能遍历整个链表在活动图 8-8 中，节点表示项目中各个工作阶段的里程碑，连接各个节点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从 A 到 J 的关键路径是 (27) ，关键路径长度是 (28) ，从 E 开始的活动启动的最早时间是 (29) 。（分数：3.00）A.ABEGJB.ADFHJC.ACFGJD.ADFBA.22B.49C.19D.3

23、5A.10B.12C.13D.1538.若采用邻接矩阵来存储简单有向图，则其某一个顶点 i 的入度等于该矩阵 (37) 。（分数：1.00）A.第 i 行中值为 1 的元素个数B.所有值为 1 的元素总数C.第 i 行及第 i 列中值为 1 的元素总个数D.第 i 列中值为 1 的元素个数39.在平衡二叉树中， (6) 。（分数：1.00）A.任意节点的左、右子树节点数目相同B.任意节点的左、右子树高度相同C.任意节点的左、右子树高度之差的绝对值不大于 1D.不存在度为 1 的节点40.任何一个基于“比较”的内部排序的算法，若对 6 个元素进行排序，则在最坏情况下所需的比较次数至少为 (66)

24、 。（分数：1.00）A.10B.11C.21D.3641.一个具有 767 个节点的完全二叉树，其叶子节点个数为 (18) 。（分数：1.00）A.383B.384C.385D.38642.为便于存储和处理一般树结构形式的信息，常采用孩子-兄弟表示法将其转换成二叉树(左子关系表示父子、右子关系表示兄弟)，与图 8-2 所示的树对应的二叉树是 (5) 。（分数：1.00）A.B.C.D.给定数据结构(V，E)，y 为节点的有限集合，V=V 1，V 2，V 3，V 4，V 5，V 6，V 7，V 8)，E 是 V 上关系的集合。E=V 1，V 2，V 3，V 4)，V 5，V 6，V 5，V 6

25、，V 1，V 3，V 4，V 7，V 4，V 5，V 2，V 4，V 4，V 6)，它所对应的图形是 (42) ，这是 (43) 。图的存储结构主要有邻接表和 (44) ，若用邻接表来存储一个图，则需要保存一个 (45) 存储的节点表和若干个 (46) 存储的关系表(又称边表)。（分数：5.00）(1). （分数：1.00）A.B.C.D.A.树B.无向图C.有向图D.无向图A.转移矩阵B.邻接矩阵C.状态矩阵D.优先矩阵A.顺序B.连接C.散列D.分块A.顺序B.连接C.散列D.索引43.将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较 (64) 次

26、。（分数：1.00）A.1B.n-1C.nD.2/944.一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵存储结构中共有 (36) 个零元素。（分数：1.00）A.eB.2eC.n2-eD.n2-2e45.在二叉树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个节点，采用三叉链表存储时，每个节点的数据域需要 d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个节点下标为 k(起始下标为 1)，那么 (8) 时采用顺序存储更节省空间。（分数：1.00）A.d12n/(k-n)B.d12n/

27、(k-n)C.d12n/(k+n)D.d12n/(k+n)软件设计师-数据结构答案解析(总分：75.00，做题时间：90 分钟)1.一个具有 n(n0)个顶点的连通无向图至少有 (33) 条边。（分数：1.00）A.n+1B.nC.n/2D.n-1 解析：分析 在无向图中，如果从一个顶点到另一个顶点有路径，则称这两个顶点是连通的。如果图中任意两个顶点都是连通的，则称该无向图是连通的。因此具有 n 个顶点的连通无向图至少有 n-1 条边。2.若对 27 个元素只进行三趟多路归并排序，则选取的归并路数为 (62) 。（分数：1.00）A.2B.3 C.4D.5解析：分析 归并就是将两个或两个以上的

28、有序表组合成一个新的有序表。设三趟归并中每次归并 x 个有序表，则第一趟归并后剩余 27/x 个表，第二趟归并后剩余 27/(x2)个表，归并三次后剩余 27/(x 3)。令27/(x3)=1，则 x=3。故选取的归并路数为 3。3. (55) 在其最好情况下的算法时间复杂度为 O(n)。（分数：1.00）A.插入排序 B.归并排序C.快速排序D.堆排序解析：分析 各种常用排序方法在最好情况下的时间复杂度如表 8-2 所示。表 8-2 时间复杂度排序方法 最好时间直接插入 O(n)简单选择 O(n2)冒泡排序 O(n)希尔排序 快速排序 O(nlogn)堆排序 O(nlogn)归并排序 O(n

29、logn)基数排序 Od(n+rd)给定节点的关键字序列(F,B,J,G,E,A,I,D,C,H)，对它按字母的字典顺序进行排列。采用不同方法，其最终结果相同，但中间结果是不同的。Shell 排序的第一趟扫描(步长为 5)结果应为 (72) 。冒泡排序(大数下沉)的第一趟起泡的效果是 (73) 。快速排序的第一趟结果是 (74) 。二路归并排序的第一趟结果是 (75) 。（分数：4.00）A.(B, F, G, J, A, D, I, E, H, C)B.(B, F, G, J, A, E, D, I, C, H)C.(A, B, D, C, E, E, I, J, G, H) D.(C, B

30、, D, A, E, F, I, G, J, H)解析：A.(A, B, D, C, P, E, I, J, H, G)B.(A, B, D, C, E, F, I, H, G, J)C.(B, P, G, E, A, I, D, C, H, J) D.(B, F, G, J, A, E, D, I, C, H)解析：A.(C, B, D, A, P, E, I, J, G, H)B.(C, B, D, A, E, F, I, G, J, H) C.(B, A, D, E, F, G, I, J, H, C)D.(B, C, D, A, E, F, I, J, G, H)解析：A.(B, F,

31、 G, J, A, E, D, I, C, H) B.(B, A, D, E, F, G, I, J, H, C)C.(A, B, D, C, E, F, I, J, G, H)D.(A, B, D, C, P, E, J, I, H, C)解析：分析 分别根据各种排序方法的排序原则，我们可以得到正确结果。4.若广义表 L(1，2，3)，则 L 的长度和深度分别为 (3) 。（分数：1.00）A.1 和 1B.1 和 2 C.1 和 3D.2 和 2解析：分析 广义表的长度定义为表中元素的个数，而深度定义为广义表展开后括号的最大嵌套层数。5.拓扑序列是无环有向图中所有顶点的一个线性序列，图中任

32、意路径中的各个顶点在该图的拓扑序列中保持先后关系， (26) 为图 8-7 所示有向图的一个拓扑序列。（分数：1.00）A.1 2 3 4 5 6 7B.1 5 2 6 3 7 4 C.5 1 2 6 3 4 7D.5 1 2 3 7 6 4解析：分析 拓扑排序是将 AOV 网中所有顶点排成一个线性序列，该序列满足：若在 AOV 网中从顶点 vi到 vj有一条路径，则在该线性序列中，顶点 vi必然在顶点 vj之前。拓扑排序即指对 AOV 网构造拓扑序列的操作。对 AOV 网进行拓扑排序的方法如下。(1)在 AOV 网中选择一个入度为零的顶点且输出它；(2)从网中删除该顶点及与该顶点有关的所有边

33、；(3)重复上述两步，直至网中不存在入度为零的顶点为止。若在 AOV 网中考查各项点的出度，并按下列步骤进行排序，则称为逆拓扑排序。(1)在 AOV 网中选择一个没有后继的顶点且输出它；(2)从网中删除该顶点，并删去所有到达该顶点的弧；(3)重复上述两步，直至网中不存在出度为零的顶点为止。为在状态空间树中 (34) ，可以利用 LC-检索(Least Cost Search)快速找到一个答案节点。在进行 LC-检索时，为避免算法过分偏向于作纵深检查，应该 (35) 。（分数：2.00）A.找出任一个答案节点B.找出所有的答案节点C.找出最优的答案节点 D.进行遍历解析：A.使用精确的成本函数

34、c(.)来作 LC-检索B.使用广度优先检索C.使用深度优先检索D.进行遍历 解析：分析 LC-检索使用一个成本估计函数来选取下一个 E-节点，以加快达到一个答案节点的速度，所以 LC-检索适用于解决在状态空间树中找出任一个答案节点的问题。在状态空间树中，定义 c(.)为节点的成本函数，g(x)为从节点 X 到达一个答案节点所需做的附加工作的估计函数，h(x)为从根节点到节点 X 的成本，则用成本估计函数 c(X)=f(h(X)+g(x)选择下一个 E节点的检索策略总是选取 c(.)值最小的活节点作为下一个 E-节点，因此这种检索策略称为最小成本检索，简称 LC-检索。那么在状态空间树中找出最

35、优的答案节点，就可以利用 LC-检索快速找到一个答案节点。根据定义，在进行 LC-检索的时候，为避免算法过分偏向于作纵深检查，应该在成本估计函数 c(.)中考虑根节点到当前节点的成本(距离)。6.表达式 a*(b+c)-d 的后缀表达形式为 (10) 。（分数：1.00）A.abcd*+-B.abc+*d- C.abc*+d-D.-+*abcd解析：分析 一个表达式可用一棵二叉树表示，其中的叶子节点表示操作数，内部节点表示操作符或中间结果，根节点表示整个表达式的值，对此二叉树分别进行前序、中序和后序遍历，恰好为表达式的前缀表示、中缀表示和后缀表示(逆波兰式)。其中表达式的前缀和后缀表示均可以将

36、表达式中的括号省去而不影响次序和结果。7.在 (48) 存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。（分数：1.00）A.顺序(Sequence)B.链表(Link)C.索引(1ndex)D.散列(Hash) 解析：分析 Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入(又叫做预映射，pre-image)，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来惟一地确定输入值。8.堆是一种数据结构， (60) 是堆。（分数：1.

37、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)解析：分析 堆的定义：对于 n 个元素的关键字序列 K1，K 2，K n，当且仅当满足下列关系时，称之为堆。*可将此序列看做一棵完全二叉树，则堆的定义表明，完全二叉树中所有非终端节点的值均不大于(或小于)其左右孩子节点的值。据此可判定上述各序列是否符合堆的定义。9. (61) 从二叉树的任一节点出发到根的路径上，所经过的节点序列必按其关键字降序排列。（分数：1.00）A.二

38、叉排序树B.大顶堆C.小顶堆 D.平衡二叉树解析：分析 当堆为小顶堆时，任意一棵子树的根点比其左右子节点要小，所以从任意节点出发到根的路径上，所经过的节点序列必按其关键字降序排列。10.在 11 个元素的有序表 A111)中进行折半查找L(low+high)/2，查找元素 A11时，被比较的元素的下标依次是 (49) 。（分数：1.00）A.6，8，10，11B.6，9，10，11 C.6，7，9，11D.6，8，9，11解析：分析 折半查找方法：对表 r1n，首先将待查的 key 值与表 r 中间位置(位置 mid)的记录的 key 进行比较，若相等，则查找成功：若 keyrmid). ke

39、y，则说明待查记录只可能在后半个子表rmid+1n(注意：是 mid+1，而不是 mid)，若 keyrmid.key，则说明待查记录只可能在后半个子表r1mid-1(注意：是 mid-1，而不是 mid)。*11.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为 (11) 。（分数：1.00）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA 解析：分析 由先序遍历序列和中序遍历序列可惟一确定一棵二叉树。同时，中序序列和后序序列也惟一确定一棵二叉树。本题的二叉树形状如图 8-3 所示。*12.设节点 x 和 y 是二叉树中任意的两个节点，

40、在该二叉树的先根遍历序列中 x 在 y 之前，而在其后根遍历序列中 x 在 y 之后，则 x 和 y 的关系是 (17) 。（分数：1.00）A.x 是 y 的左兄弟B.x 是 y 的右兄弟C.x 是 y 的祖先 D.x 是 y 的后裔解析：分析 先序遍历的递归算法定义为若二叉树非空，则依次执行如下操作：访问根节点，遍历左子树，遍历右子树。后序遍历的递归算法定义为若二叉树非空，则依次执行如下操作：遍历左子树，遍历右子树，访问根节点。13.在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是 (58) 。（分数：1.00）A.基数排序B.快速排序C.堆排序D.归并排序 解析：分

41、析 基数排序在最好和最坏情况下的时间复杂度均为 Od(n+rd)，快速排序在最好和最坏情况下的时间复杂度分别为 O(nlogn)和 O(n2)且不稳定，堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)但不稳定，归并排序在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定。一棵查找二叉树，其节点 A，B，C，D，E，F 依次存放在一个起始地址为 n(假定地址以字节为单位顺序编号)的连续区域中，每个节点占 4 字节，前二字节存放节点值，后二字节依次放左指针、右指针。若该查找二叉树的根节点为 E，则它的一种可能的前序遍历为 (20) ，相应的层次遍历为 (21) 。在以上两种遍历情况下

42、，节点 c 的左指针 LC 的存放地址为 (22) ，LC 的内容为 (23) 。节点 A 的右指针 RA的内容为 (24) 。（分数：5.00）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF 解析：A.EAFCBD B.EFACDBC.EABCFDD.EACBDF解析：A.n+9B.n+10 C.n+12D.n+13解析：A.n+4 B.n+8C.n+12D.n+16解析：A.n+4B.n+8 C.n+12D.n+16解析：分析 此题最主要的条件就是“查找二叉树”。查找二叉树中每一个节点的左子树节点关键值小于节点本身，而右子树节点大于节点本身。题目中又给出条件“根节点为 E

43、”，所以比 E 小的节点A，B，C，D 都是 E 的左子树节点，而 F 是右子树节点，又因为前序遍历顺序为：根、左、右，所以前序遍历的第一个节点是 E，最后一个节点是 F。因此对于空(1)，选项 D 满足。由上述分析知道，前序遍历序列为 EACBDF，且知道二叉树的左子树是 ACBD，再根据前序遍历的性质和 A是左子树的根节点，可知 C，B，D 均是 A 节点下的右子树。同理 B 和 D 分别是 C 的左子树和右子树。最后所得的二叉树如图 8-5 所示。*根据图 8-5，我们立即得到该二叉树的层次遍历序列为 EAFCBD。根据试题条件，节点 A，B，C，D，E，F 依次存放，且每个节点占 4

44、字节，所以 C 的起始地址为 n+8，Lc的地址为 n+10。根据图 8-5 所示，Lc 中应存放 B 的地址，由于起始地址为 n，因此 B 的地址为 n+4，Lc上的内容是 n+4。节点 A 的右指针 Ra 中应存放 C 的地址，而 C 的地址为 n+8，即 Ra 的内容是 n+8。14. (51) 的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。（分数：1.00）A.树形存储结构B.链式存储结构C.索引存储结构D.散列存储结构 解析：分析 很显然这是散列存储结构。散列存储结构将节点按其关键字的散列地址存储到散列表中。常用的散列函数有除余法、基数转换法、平方取中法、折叠法、移

45、位法和随机数法等。15.已知一个线性表(38，25，74，63，52，48)，假定采用散列函数 h(key)=key%7 计算散列地址，并散列存储在散列表 A06中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (50) 。（分数：1.00）A.1.5B.1.7C.2.0 D.2.3解析：分析 按照散列函数 h(key)：key%7 和线性探测方法解决冲突，将线性表(38,25,74,63,52,48)散列存储在散列表 A06中，如图 8-10 所示。*16.若循环队列以数组 QOm-1作为其存储结构，变量 rear 表示循环队列中队尾元素的实际位置，其移动按

46、rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 (2) 。（分数：1.00）A.rear-lengthB.(rear-length+m) mod mC.(1+rear+m-length) mod m D.m-length解析：分析 按照循环队列的定义，因为元素移动按照 rear=(rear+1)mod m 进行，则当数组 Qm-1存放了元素之后，下一个入队的元素将存放到 Q0中，因此队列的首元素的实际位置是 (regr+1-1ength+m)mod m。17.无向图中一个顶点的度是指图中 (32) 。（分数：1.

47、00）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻接的顶点数 D.与该顶点连通的顶点数解析：分析 图中顶点的度定义为与该顶点相关联的边的数目。在无向图中就是与该顶点相邻接的顶点数，而与该顶点连通的顶点数可能就非常多厂。18.关键路径是指 AOE(Activity On Edge)网中 (38) 。（分数：1.00）A.最长的回路B.最短的回路C.从源点到汇点(结束顶点)的最长路径 D.从源点到汇点(结束顶点)的最短路径解析：分析 在 AOE 网中，用顶点表示活动，用有向边vi，vi表示活动 vi 必须先于活动 vi 进行。如果在有向环的带权有向图中用有向边表示一个工程中的各

48、项活动，用有向边上的权值表示活动的持续时间，用顶点表示事件，则这种有向图叫做用边表示活动的网络，简称 AOE 网络。关键路径是指在 AOE 网络中从源点到汇点的最长路径。拓扑排序、最短路径和计算关键路径都是有向图的重要运算。根据关键路径的定义，正确答案为 C。19.若一个具有 n 个节点、k 条边的非连通无向图是一个森林(nk)，则该森林中必有 (19) 棵树。（分数：1.00）A.kB.nC.n-k D.n+k解析：分析 设该森林共有 m 棵树，每棵树有 ni(1im)个节点，依据树的性质有n=n1+n2+nmk=(n1-1)+(n2-1)+(nm-1)上面两式相减得n-k=1+1+1=m而

49、 m 就是树的个数，所以该森林共有 n-k 棵树。20.以下序列中不符合堆定义的是 (63) 。（分数：1.00）A.(102，87，100，79，82，62，84，42，22，12，68)B.(102，100，87，84，82，79，68，62，42，22，12)C.(12，22，42，62，68，79，82，84，87，100，102)D.(102，87，42，79，82，62，68，100，84，12，22) 解析：分析 根据堆的定义，n 个关键字序列 k1，k 2，K n。称为堆的条件是，当且仅当该序列满足 kik 2i且 kik 2i+1或 kik 2i且 kik 2i+1，(1in/2)。当 i=1，2 时，4 个选项都满足条件 (其中A，B，D 为大根堆，C 为小根堆)。但当 i=3 时，D 不满足条件。21.在常用的描述二叉排序树的存储结构中