1、软件设计师-数据结构(一)及答案解析(总分：75.00，做题时间：90 分钟)1.循环链表的主要优点是 (1) 。A不再需要头指针了B已知某个节点的位置后，能很容易找到它的直接前驱节点C在进行删除操作后，能保证链表不断开D从表中任一节点出发都能遍历整个链表（分数：1.00）A.B.C.D.2.若循环队列以数组 QOm-1作为其存储结构，变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 (2) 。Arear-length B(rear-length+m) m
2、od mC(1+rear+m-length) mod m Dm-length（分数：1.00）A.B.C.D.3.若广义表 L(1，2，3)，则 L 的长度和深度分别为 (3) 。A1 和 1 B1 和 2 C1 和 3 D2 和 2（分数：1.00）A.B.C.D.4.已知有一维数组 A(0m*n-1，若要对应为 m 行、n 列的矩阵，则下面的对应关系 (4) 可将元素 Ak(0km*n)表示成矩阵的第 i 行、第 j 列的元素(0im，0jn)。Ai=k/n,j=k%m Bi=k/m,j=K%mCi=k/n,j=k%n Di=k/m,j=k%n（分数：1.00）A.B.C.D.5.为便于存
3、储和处理一般树结构形式的信息，常采用孩子-兄弟表示法将其转换成二叉树(左子关系表示父子、右子关系表示兄弟)，与图 8-2 所示的树对应的二叉树是 (5) 。（分数：1.00）A.B.C.D.6.在平衡二叉树中， (6) 。A任意节点的左、右子树节点数目相同B任意节点的左、右子树高度相同C任意节点的左、右子树高度之差的绝对值不大于 1D不存在度为 1 的节点（分数：1.00）A.B.C.D.7.已知某二叉树的中序、层序序列分别为 DBAFCE，FDEBCA，则该二叉树的后序序列为 (7) 。ABCDEAF BABDCEF CDBACEF DDABECF（分数：1.00）A.B.C.D.8.在二叉
4、树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个节点，采用三叉链表存储时，每个节点的数据域需要d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个节点下标为 k(起始下标为 1)，那么 (8) 时采用顺序存储更节省空间。Ad12n/(k-n) Bd12n/(k-n) Cd12n/(k+n) Dd12n/(k+n)（分数：1.00）A.B.C.D.9.由元素序列 27，16，75，38，51 构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入节点最近且平衡因子的绝对值为 2 的节点)为 (9
5、) 。A27 B38 C51 D75（分数：1.00）A.B.C.D.10.表达式 a*(b+c)-d 的后缀表达形式为 (10) 。Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd（分数：1.00）A.B.C.D.11.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为 (11) 。ADEBAFC BDEFBCA CDEBCFA DDEBFCA（分数：1.00）A.B.C.D.12.在常用的描述二叉排序树的存储结构中，关键字值最大的节点 (12) 。A左指针一定为空 B右指针一定为空C左右指针均为空 D左右指针均不为空（分数：1.0
6、0）A.B.C.D.13.由权值为 9，2，5，7 的四个叶子构造一棵哈夫曼树，该树的带权路径长度为 (13) 。A23 B37 C44 D46（分数：1.00）A.B.C.D.14.在一棵完全二叉树中，其根的序号为 1， (14) 可判定序号为 p 和 q 的两个节点是否在同一层。Alog p=log2q) Blog 2 p=log2 qClog 2 p+1=log2q) Dlog 2 p=log2 q)+1（分数：1.00）A.B.C.D.15.若一棵哈夫曼(Huffman)树共有 9 个顶点，则其叶子节点的个数为 (15) 。A4 B5 C6 D7（分数：1.00）A.B.C.D.16.
7、在一棵度为 3 的树中，若有 2 个度为 3 的节点，有 1 个度为 2 的节点，则有 (16) 个度为 0 的节点。A4 B5 C6 D7（分数：1.00）A.B.C.D.17.设节点 x 和 y 是二叉树中任意的两个节点，在该二叉树的先根遍历序列中 x 在 y 之前，而在其后根遍历序列中 x 在 y 之后，则 x 和 y 的关系是 (17) 。Ax 是 y 的左兄弟 Bx 是 y 的右兄弟Cx 是 y 的祖先 Dx 是 y 的后裔（分数：1.00）A.B.C.D.18.一个具有 767 个节点的完全二叉树，其叶子节点个数为 (18) 。A383 B384 C385 D386（分数：1.00
8、）A.B.C.D.19.若一个具有 n 个节点、k 条边的非连通无向图是一个森林(nk)，则该森林中必有 (19) 棵树。Ak Bn Cn-k Dn+k（分数：1.00）A.B.C.D.一棵查找二叉树，其节点 A，B，C，D，E，F 依次存放在一个起始地址为 n(假定地址以字节为单位顺序编号)的连续区域中，每个节点占 4 字节，前二字节存放节点值，后二字节依次放左指针、右指针。若该查找二叉树的根节点为 E，则它的一种可能的前序遍历为 (20) ，相应的层次遍历为 (21) 。在以上两种遍历情况下，节点 c 的左指针 LC 的存放地址为 (22) ，LC 的内容为 (23) 。节点 A 的右指针
9、 RA的内容为 (24) 。（分数：5.00）(1).AEAFCBD BEFACDB CEABCFD DEACBDF（分数：1.00）A.B.C.D.(2).AEAFCBD BEFACDB CEABCFD DEACBDF（分数：1.00）A.B.C.D.(3).An+9 Bn+10 Cn+12 Dn+13（分数：1.00）A.B.C.D.(4).An+4 Bn+8 Cn+12 Dn+16（分数：1.00）A.B.C.D.(5).An+4 Bn+8 Cn+12 Dn+16（分数：1.00）A.B.C.D.20.某工程计划图如图 8-6 所示，弧上的标记为作业编码及其需要的完成时间(天)，作业 E
10、 最迟应在第 (25) 天开始。（分数：1.00）A.B.C.D.21.拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系， (26) 为图 8-7 所示有向图的一个拓扑序列。（分数：1.00）A.B.C.D.在活动图 8-8 中，节点表示项目中各个工作阶段的里程碑，连接各个节点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从 A 到 J 的关键路径是 (27) ，关键路径长度是 (28) ，从 E 开始的活动启动的最早时间是 (29) 。（分数：3.00）(1).AABEGJ BADFHJ CACFGJ DADFB（分数：1.
11、00）A.B.C.D.(2).A22 B49 C19 D35（分数：1.00）A.B.C.D.(3).A10 B12 C13 D15（分数：1.00）A.B.C.D.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个节点，其邻接矩阵为A1n, 1n，且压缩存储在 B1k中，则 k 的值至少为 (30) 。若按行压缩存储对称矩阵的上三角元素，则当 n 等于 10 时，边(V 6，V 3)的信息存储在 B (31) 中。（分数：2.00）(1).An(n+1)/2 Bn2/2 C(n-1)(n+1)/2 Dn(n-1)/2（分数：1.00）A.B.C.D.(2).A18
12、B19 C20 D21（分数：1.00）A.B.C.D.22.无向图中一个顶点的度是指图中 (32) 。A通过该顶点的简单路径数 B通过该顶点的回路数C与该顶点相邻接的顶点数 D与该顶点连通的顶点数（分数：1.00）A.B.C.D.23.一个具有 n(n0)个顶点的连通无向图至少有 (33) 条边。An+1 Bn Cn/2 Dn-1（分数：1.00）A.B.C.D.为在状态空间树中 (34) ，可以利用 LC-检索(Least Cost Search)快速找到一个答案节点。在进行 LC-检索时，为避免算法过分偏向于作纵深检查，应该 (35) 。（分数：2.00）(1).A找出任一个答案节点 B
13、找出所有的答案节点C找出最优的答案节点 D进行遍历（分数：1.00）A.B.C.D.(2).A使用精确的成本函数 c(.)来作 LC-检索B使用广度优先检索C使用深度优先检索D进行遍历（分数：1.00）A.B.C.D.24.一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵存储结构中共有 (36) 个零元素。Ae B2e Cn 2-e Dn 2-2e（分数：1.00）A.B.C.D.25.若采用邻接矩阵来存储简单有向图，则其某一个顶点 i 的入度等于该矩阵 (37) 。A第 i 行中值为 1 的元素个数B所有值为 1 的元素总数C第 i 行及第 i 列中值为 1 的元素总个数D第 i
14、列中值为 1 的元素个数（分数：1.00）A.B.C.D.26.关键路径是指 AOE(Activity On Edge)网中 (38) 。A最长的回路 B最短的回路C从源点到汇点(结束顶点)的最长路径 D从源点到汇点(结束顶点)的最短路径（分数：1.00）A.B.C.D.27.若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 至少有 (39) 个顶点。A11 B10 C9 D8（分数：1.00）A.B.C.D.己知 AOE 网中顶点 v1v7 分别表示 7 个事件，弧 a1a10 分别表示 10 个活动，弧上的数值表示每个活动花费的时间，如图 8-9 所示。那么，该
15、网的关键路径的长度为 (40) ，活动 a6 的松弛时间(活动的最迟开始时间活动的最早开始时间)为 (41) 。（分数：2.00）(1).A7 B9 C10 D11（分数：1.00）A.B.C.D.(2).A3 B2 C1 D0（分数：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，V 1，V 3，V 4，V 7，V 4，V 5，V 2，V 4，V 4，V 6)，它所对应的图形是 (42) ，这是 (43)
16、 。图的存储结构主要有邻接表和 (44) ，若用邻接表来存储一个图，则需要保存一个 (45) 存储的节点表和若干个 (46) 存储的关系表(又称边表)。（分数：5.00）(1). （分数：1.00）A.B.C.D.(2).A树 B无向图 C有向图 D无向图（分数：1.00）A.B.C.D.(3).A转移矩阵 B邻接矩阵 C状态矩阵 D优先矩阵（分数：1.00）A.B.C.D.(4).A顺序 B连接 C散列 D分块（分数：1.00）A.B.C.D.(5).A顺序 B连接 C散列 D索引（分数：1.00）A.B.C.D.28.给定一个有 n 个元素的有序线性表。若采用顺序存储结构，则在等概率前提下
17、，删除其中的一个元素平均需要移动 (47) 个元素。A(n+1)/2 Bn/2 C(n-1)/2 D1（分数：1.00）A.B.C.D.29.在 (48) 存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。A顺序(Sequence) B链表(Link) C索引(1ndex) D散列(Hash)（分数：1.00）A.B.C.D.30.在 11 个元素的有序表 A111)中进行折半查找L(low+high)/2，查找元素 A11时，被比较的元素的下标依次是 (49) 。A6，8，10，11 B6，9，10，11 C6，7，9，11 D6，8，9，11（分数：1.00）A.B.C.
18、D.31.已知一个线性表(38，25，74，63，52，48)，假定采用散列函数 h(key)=key%7 计算散列地址，并散列存储在散列表 A06中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 (50) 。A1.5 B1.7 C2.0 D2.3（分数：1.00）A.B.C.D.32. (51) 的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。A树形存储结构 B链式存储结构 C索引存储结构 D散列存储结构（分数：1.00）A.B.C.D.33.设顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索引表采用顺序查找方法来
19、确定子块，且在确 (52) 。A21 B 23 C41 D62（分数：1.00）A.B.C.D.类比二分搜索算法，设计 k 分搜索算法(k 为大于 2 的整数)如下：首先检查 n/k 处(n 为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查 2n/k 处的元素这样，或者找到要搜索的元素，或者把集合缩小到原来的 1/k；如果未找到要搜索的元素，则继续在得到的集合上进行 k 分搜索；如此进行，直到找到要搜索的元素或搜索失败。此 k 分搜索算法在最坏情况下搜索成功的时间复杂度为 (53) ，在最好情况下搜索失败的时间复杂度为 (54) 。（分数：2.00）(1).AO(logn) BO(n
20、logn) CO(log kn) DO(nlog kn)（分数：1.00）A.B.C.D.(2).AO(logn) BO(nlogn) CO(log kn) DO(nlog kn)（分数：1.00）A.B.C.D.34. (55) 在其最好情况下的算法时间复杂度为 O(n)。A插入排序 B归并排序 C快速排序 D堆排序（分数：1.00）A.B.C.D.35.若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。 (56) 排序是稳定的。A归并 B快速 C希尔 D堆（分数：1.00）A.B.C.D.36.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，3
21、0)对应的二叉排序树以后，查找元素 30 要进行 (57) 次元素间的比较。A4 B5 C6 D7（分数：1.00）A.B.C.D.37.在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是 (58) 。A基数排序 B快速排序 C堆排序 D归并排序（分数：1.00）A.B.C.D.38.以比较为基础的排序算法在最坏情况下的计算时间下界为 (59) 。AO(n) BO(n 2) CO(logn) D O(nlogn)（分数：1.00）A.B.C.D.39.堆是一种数据结构， (60) 是堆。A(10，50，80，30，60，20，15，18) B(10，18，15，20，50，
22、80，30，60)C(10，15，18，50，80，30，60，20) D(10，30，60，20，15，18，50，80)（分数：1.00）A.B.C.D.40. (61) 从二叉树的任一节点出发到根的路径上，所经过的节点序列必按其关键字降序排列。A二叉排序树 B大顶堆 C小顶堆 D平衡二叉树（分数：1.00）A.B.C.D.41.若对 27 个元素只进行三趟多路归并排序，则选取的归并路数为 (62) 。A2 B3 C4 D5（分数：1.00）A.B.C.D.42.以下序列中不符合堆定义的是 (63) 。A(102，87，100，79，82，62，84，42，22，12，68)B(102，1
23、00，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)（分数：1.00）A.B.C.D.43.将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较 (64) 次。A1 Bn-1 Cn D2/9（分数：1.00）A.B.C.D.44.对 n 个元素进行快速排序时，最坏情况下的时间复杂度为 (65) 。AO(log 2n) BO(n) CO(nlog 2/t) D O(n 2)（分数：1.00）A.B.C.D
24、.45.任何一个基于“比较”的内部排序的算法，若对 6 个元素进行排序，则在最坏情况下所需的比较次数至少为 (66) 。A10 B11 C21 D36（分数：1.00）A.B.C.D.对于给定的一组关键字(12,2,16,30,8,28,4,10,20,6,18)，按照下列算法进行递增排序，写出每种算法第一趟排序后得到的结果：希尔排序(增量为 5)得到 (67) ，快速排序(选第一个记录为基准元素)得到 (68) ，链式基数(基数为 10 排)序得到 (69) ，二路归并排序得到 (70) ，堆排序得到 (71) 。（分数：5.00）(1).A2,4,6,8,10,12,16,18,20,28
25、,30 B6,2,10,4,8,12,28,30,20,16,18C12,2,10,20,6,18,4,16,30,8,28 D30,10,20,12,2,4,16,6,8,28,18（分数：1.00）A.B.C.D.(2).A10,6,18,8,4,2,12,20,16,30,28 B6,2,10,4,8,12,28,30,20,16,10C2,4,6,8,10,12,16,18,20,28,30 D6,10,8,28,20,18,2,4,12,30,16（分数：1.00）A.B.C.D.(3).A10,6,18,8,4,2,12,20,16,30,28 B1,12,10,20,6,18,4
26、,16,30,8,28C2,4,6,8,10,12,16,18,20,28,30 D30,10,20,12,2,4,16,6,8,28,18（分数：1.00）A.B.C.D.(4).A2,12,16,8,28,30,4,6,10,18,20 B2,12,16,30,8,28,4,10,6,20,18C12,2,16,8,28,30,4,6,10,28,18 D12,2,10,20,6,18,4,16,30,8,28（分数：1.00）A.B.C.D.(5).A30,28,20,12,18,16,4,10,2,6,8 B20,30,28,12,18,4,16,10,2,8,6C2,6,4,10,8
27、,28,16,30,20,12,18 D2,4,10,6,12,28,16,20,8,30,18（分数：1.00）A.B.C.D.给定节点的关键字序列(F,B,J,G,E,A,I,D,C,H)，对它按字母的字典顺序进行排列。采用不同方法，其最终结果相同，但中间结果是不同的。Shell 排序的第一趟扫描(步长为 5)结果应为 (72) 。冒泡排序(大数下沉)的第一趟起泡的效果是 (73) 。快速排序的第一趟结果是 (74) 。二路归并排序的第一趟结果是 (75) 。（分数：4.00）(1).A(B, F, G, J, A, D, I, E, H, C)B(B, F, G, J, A, E, D,
28、 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)（分数：1.00）A.B.C.D.(2).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)（分数：1.00）A.B.C.D.(3).A(C, B, D, A, P, E, I, J, G, H)B(C, B, D, A, E, F, I, G, J, H)C
29、(B, A, D, E, F, G, I, J, H, C)D(B, C, D, A, E, F, I, J, G, H)（分数：1.00）A.B.C.D.(4).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, I, H, C)（分数：1.00）A.B.C.D.软件设计师-数据结构(一)答案解析(总分：75.00，做题时间：90 分钟)1.循环链表的主要优点是 (1) 。A不再需要头指针了B已知某个节点的位置后，
30、能很容易找到它的直接前驱节点C在进行删除操作后，能保证链表不断开D从表中任一节点出发都能遍历整个链表（分数：1.00）A.B.C.D. 解析：解析 链表或设头指针或设尾指针，因此选项 A 被排除。选项 B 指的是双向循环链表。由于链表都要保证删除操作后，仍为链表，因此选项 C 也被排除。2.若循环队列以数组 QOm-1作为其存储结构，变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 (2) 。Arear-length B(rear-length+m) mo
31、d mC(1+rear+m-length) mod m Dm-length（分数：1.00）A.B.C. D.解析：解析 按照循环队列的定义，因为元素移动按照 rear=(rear+1)mod m 进行，则当数组 Qm-1存放了元素之后，下一个入队的元素将存放到 Q0中，因此队列的首元素的实际位置是 (regr+1-1ength+m)mod m。3.若广义表 L(1，2，3)，则 L 的长度和深度分别为 (3) 。A1 和 1 B1 和 2 C1 和 3 D2 和 2（分数：1.00）A.B. C.D.解析：解析 广义表的长度定义为表中元素的个数，而深度定义为广义表展开后括号的最大嵌套层数。4
32、.已知有一维数组 A(0m*n-1，若要对应为 m 行、n 列的矩阵，则下面的对应关系 (4) 可将元素 Ak(0km*n)表示成矩阵的第 i 行、第 j 列的元素(0im，0jn)。Ai=k/n,j=k%m Bi=k/m,j=K%mCi=k/n,j=k%n Di=k/m,j=k%n（分数：1.00）A.B.C. D.解析：解析 此题是求一维数组向二维数组转化的问题。最原始的方法就是把数组 A 的前 n 个元素放到数组 B 的第一行，数组 A 的第 n 个元素放到数组 B 的第二行中，依次类推，数组 A 的最后 n 个元素放到数组 B 的最后一行中。求且幻在数组 B 中的位置，应先确定 Ak处
33、在哪一行，显然应该是 k/n 行，然后再确定处在 k/n 行的哪一列，显然是 k%n 列。5.为便于存储和处理一般树结构形式的信息，常采用孩子-兄弟表示法将其转换成二叉树(左子关系表示父子、右子关系表示兄弟)，与图 8-2 所示的树对应的二叉树是 (5) 。（分数：1.00）A. B.C.D.解析：解析 树的孩子兄弟表示法又称二叉链表表示法。在链表的节点中设置两个指针域，分别指向该节点的第一个孩子和下一个兄弟，利用这种存储结构便于实现树的各种操作。6.在平衡二叉树中， (6) 。A任意节点的左、右子树节点数目相同B任意节点的左、右子树高度相同C任意节点的左、右子树高度之差的绝对值不大于 1D不
34、存在度为 1 的节点（分数：1.00）A.B.C. D.解析：解析 平衡二叉树又称 AVL 树。它或者是一棵空树，或者是具有下列性质的二叉树。左子树和右子树都是平衡二叉树；左子树和右子树的深度之差的绝对值不超过 1；二叉树上节点的平衡因子定义为该节点的左子树的深度减去它的右子树的深度。由此可见，平衡二叉树上所有节点的平衡因子只可能是-1，0，1。只要二叉树上有一个节点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。7.已知某二叉树的中序、层序序列分别为 DBAFCE，FDEBCA，则该二叉树的后序序列为 (7) 。ABCDEAF BABDCEF CDBACEF DDABECF（分数：1.0
35、0）A.B. C.D.解析：解析 按照遍历左子树要在遍历右子树之前进行的原则，根据访问根节点位置的不同，可得到二叉树的前序、中序和后序 3 种遍历方法。层序遍历是从根节点(第 1 层)出发，首先访问第 1 层的树根节点，然后从左到右依次访问第 2 层上的节点，再次是第三层上的节点，依次类推，自上而下、自左向右逐层访问各层上的节点。对二叉树而言，第 n 层节点最多为 2n-1。由层序序列可得；F 是树根节点，D，E 是第 2 层节点；结合中序序列有 DBA 构成 F 的左子树，CE 构成 F的右子树，进一步有 C 是 E 的左节点，E 无右节点；这样 A 是第 4 层节点，据 DBA 序列有 B
36、 是 D 的右节点，A 是 B 的右节点。由此易知后序序列为 ABDCEF。8.在二叉树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个节点，采用三叉链表存储时，每个节点的数据域需要d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个节点下标为 k(起始下标为 1)，那么 (8) 时采用顺序存储更节省空间。Ad12n/(k-n) Bd12n/(k-n) Cd12n/(k+n) Dd12n/(k+n)（分数：1.00）A. B.C.D.解析：解析 顺序存储所需空间为 kd，三叉链存储所需空间为 n(
37、d+43)，当 kdn(d+12)，即9.由元素序列 27，16，75，38，51 构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入节点最近且平衡因子的绝对值为 2 的节点)为 (9) 。A27 B38 C51 D75（分数：1.00）A.B.C.D. 解析：解析 二叉排序树的构造方法如下：每读入一个数据，建立一个新节点，若二叉排序树非空，则将新节点的值与根节点的值比较，。如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新节点作为二叉排序树的根节点。节点的平衡因子是指节点右子树深度与左子树深度之差。由数据27，16，75，38，51构造平衡二叉树，插入 5
38、1 后首次出现不平衡子树，易知最小不平衡子树的节点为 75。10.表达式 a*(b+c)-d 的后缀表达形式为 (10) 。Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd（分数：1.00）A.B. C.D.解析：解析 一个表达式可用一棵二叉树表示，其中的叶子节点表示操作数，内部节点表示操作符或中间结果，根节点表示整个表达式的值，对此二叉树分别进行前序、中序和后序遍历，恰好为表达式的前缀表示、中缀表示和后缀表示(逆波兰式)。其中表达式的前缀和后缀表示均可以将表达式中的括号省去而不影响次序和结果。11.若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则
39、其后序遍历序列为 (11) 。ADEBAFC BDEFBCA CDEBCFA DDEBFCA（分数：1.00）A.B.C.D. 解析：解析 由先序遍历序列和中序遍历序列可惟一确定一棵二叉树。同时，中序序列和后序序列也惟一确定一棵二叉树。本题的二叉树形状如图 8-3 所示。12.在常用的描述二叉排序树的存储结构中，关键字值最大的节点 (12) 。A左指针一定为空 B右指针一定为空C左右指针均为空 D左右指针均不为空（分数：1.00）A.B. C.D.解析：解析 在二叉排序树的存储结构中，每节点山三部分构成，其中左(或右)指针指向比节点的关键值小(或大)的节点。关键字值最大的节点位于二叉排序树的最
40、右位置上，因此它的右指针一定为空。13.由权值为 9，2，5，7 的四个叶子构造一棵哈夫曼树，该树的带权路径长度为 (13) 。A23 B37 C44 D46（分数：1.00）A.B.C. D.解析：解析 哈夫曼树的形状如图 8-4 所示。14.在一棵完全二叉树中，其根的序号为 1， (14) 可判定序号为 p 和 q 的两个节点是否在同一层。Alog p=log2q) Blog 2 p=log2 qClog 2 p+1=log2q) Dlog 2 p=log2 q)+1（分数：1.00）A. B.C.D.解析：解析 由完全二叉树的性质可知，在一棵完全二叉树第 h(h1)层上的节点 p 和 q
41、，它们的序号范围应是 2h-1p，q2 h-1，因此log p=log2q)成立。15.若一棵哈夫曼(Huffman)树共有 9 个顶点，则其叶子节点的个数为 (15) 。A4 B5 C6 D7（分数：1.00）A.B. C.D.解析：解析 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子节点。N 个权值分别设为 w1，w 2， w n，则哈夫曼树的构造规则如下。第一步：将 w1，w 2，w n看成是有 n 棵树的森林；第二步：在森林中选出两个根节点的权值最小的树合并，作为一棵新树的左
42、、右子树，且新树的根节点权值为其左右子树根节点权值之和；第三步：从森林中删除选取的两棵树，并将新树加入森林：第四步：重复第二步和第三步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为 1 的分支节点。n 个叶子的哈夫曼树要经过n-1 次合并，产生 n-1 个新节点，最后求得的哈夫曼树中共有 2n-1 个节点。16.在一棵度为 3 的树中，若有 2 个度为 3 的节点，有 1 个度为 2 的节点，则有 (16) 个度为 0 的节点。A4 B5 C6 D7（分数：1.00）A.B.C. D.解析：解析 节点的度是指一个节点子树的个数。度为
43、3 就是这个节点有 3 个子树节点，而度为 2 是这个节点有 2 个子树节点。因此度为 0 的节点有 6 个。17.设节点 x 和 y 是二叉树中任意的两个节点，在该二叉树的先根遍历序列中 x 在 y 之前，而在其后根遍历序列中 x 在 y 之后，则 x 和 y 的关系是 (17) 。Ax 是 y 的左兄弟 Bx 是 y 的右兄弟Cx 是 y 的祖先 Dx 是 y 的后裔（分数：1.00）A.B.C. D.解析：解析 先序遍历的递归算法定义为若二叉树非空，则依次执行如下操作：访问根节点，遍历左子树，遍历右子树。后序遍历的递归算法定义为若二叉树非空，则依次执行如下操作：遍历左子树，遍历右子树，访
44、问根节点。18.一个具有 767 个节点的完全二叉树，其叶子节点个数为 (18) 。A383 B384 C385 D386（分数：1.00）A.B. C.D.解析：解析 设二叉树中总节点数，以及度为 0、度为 1 和度为 2 的节点数分别为 n，n 0，n 1和 n2，依据二叉树的性质可得到下列等式：n=n0+n1+n2n=768n-1=n1+2n2通过化简可得到769=2n0+n1在完全二叉树中，度为 1 的节点要么没有，要么有 1 个。上面等式左边为一个奇数，等式右边 2n0是一个偶数，要使等式成立，n 1只能为奇数，即是 1，所以叶子节点个数 n0=384。19.若一个具有 n 个节点、
45、k 条边的非连通无向图是一个森林(nk)，则该森林中必有 (19) 棵树。Ak Bn Cn-k Dn+k（分数：1.00）A.B.C. D.解析：解析 设该森林共有 m 棵树，每棵树有 ni(1im)个节点，依据树的性质有n=n1+n2+nmk=(n1-1)+(n2-1)+(nm-1)上面两式相减得n-k=1+1+1=m而 m 就是树的个数，所以该森林共有 n-k 棵树。一棵查找二叉树，其节点 A，B，C，D，E，F 依次存放在一个起始地址为 n(假定地址以字节为单位顺序编号)的连续区域中，每个节点占 4 字节，前二字节存放节点值，后二字节依次放左指针、右指针。若该查找二叉树的根节点为 E，则
46、它的一种可能的前序遍历为 (20) ，相应的层次遍历为 (21) 。在以上两种遍历情况下，节点 c 的左指针 LC 的存放地址为 (22) ，LC 的内容为 (23) 。节点 A 的右指针 RA的内容为 (24) 。（分数：5.00）(1).AEAFCBD BEFACDB CEABCFD DEACBDF（分数：1.00）A.B.C.D. 解析：(2).AEAFCBD BEFACDB CEABCFD DEACBDF（分数：1.00）A. B.C.D.解析：(3).An+9 Bn+10 Cn+12 Dn+13（分数：1.00）A.B. C.D.解析：(4).An+4 Bn+8 Cn+12 Dn+1
47、6（分数：1.00）A. B.C.D.解析：(5).An+4 Bn+8 Cn+12 Dn+16（分数：1.00）A.B. C.D.解析：解析 此题最主要的条件就是“查找二叉树”。查找二叉树中每一个节点的左子树节点关键值小于节点本身，而右子树节点大于节点本身。题目中又给出条件“根节点为 E”，所以比 E 小的节点A，B，C，D 都是 E 的左子树节点，而 F 是右子树节点，又因为前序遍历顺序为：根、左、右，所以前序遍历的第一个节点是 E，最后一个节点是 F。因此对于空(1)，选项 D 满足。由上述分析知道，前序遍历序列为 EACBDF，且知道二叉树的左子树是 ACBD，再根据前序遍历的性质和 A
48、是左子树的根节点，可知 C，B，D 均是 A 节点下的右子树。同理 B 和 D 分别是 C 的左子树和右子树。最后所得的二叉树如图 8-5 所示。20.某工程计划图如图 8-6 所示，弧上的标记为作业编码及其需要的完成时间(天)，作业 E 最迟应在第 (25) 天开始。（分数：1.00）A.B.C.D. 解析：解析 3+5+5=1321.拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系， (26) 为图 8-7 所示有向图的一个拓扑序列。（分数：1.00）A.B. C.D.解析：解析 拓扑排序是将 AOV 网中所有顶点排成一个线性序列，该序列满足：若在 AOV 网中从顶点 vi到 vj有一条路径，则在
