软件设计师-数据结构(一)
(总分75,考试时间90分钟)
1. 循环链表的主要优点是 (1) 。
A．不再需要头指针了
B．已知某个节点的位置后，能很容易到它的直接前驱节点
C．在进行删除操作后，能保证链表不断开
D．从表中任一节点出发都能遍历整个链表
2. 若循环队列以数组-1]作为其存储结构，变量rear表示循环队列中队尾元素的实际位置，其移动按rear=(rear+1) mod m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 (2) 。
A．rear-length B．(rear-length+m) mod m
C．(1+rear+m-length) mod m D．m-length
3. 若广义表L((1，2，3))，则L的长度和深度分别为 (3) 。
A．1和1 B．1和2 C．1和3 D．2和2
4. 已知有一维数组*n-1]，若要对应为m行、n列的矩阵，则下面的对应关系 (4) 可将元素A[k](0≤k＜m*n)表示成矩阵的第i行、第j列的元素(0≤i＜m，0≤j＜n)。
A．i=k/n,j=k%m B．i=k/m,j=K%m
C．i=k/n,j=k%n D．i=k/m,j=k%n
5. 为便于存储和处理一般树结构形式的信息，常采用孩子-兄弟表示法将其转换成二叉树(左子关系表示父子、右子关系表示兄弟)，与图8-2所示的树对应的二叉树是 (5) 。
6. 在平衡二叉树中， (6) 。
A．任意节点的左、右子树节点数目相同
B．任意节点的左、右子树高度相同
C．任意节点的左、右子树高度之差的绝对值不大于1
D．不存在度为1的节点
7. 已知某二叉树的中序、层序序列分别为DBAFCE，FDEBCA，则该二叉树的后序序列为 (7) 。
A．BCDEAF B．ABDCEF C．DBACEF D．DABECF
8. 在二叉树的顺序存储中，每个节点的存储位置与其父节点、左右子树节点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个节点，采用三叉链表存储时，每个节点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个节点下标为k(起始下标为1)，那么 (8) 时采用顺序存储更节省空间。
A．d＜12n/(k-n) B．d＞12n/(k-n) C．d＜12n/(k+n) D．d＞12n/(k+n)
9. 由元素序列27，16，75，38，51构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入节点最近且平衡因子的绝对值为2的节点)为 (9) 。
A．27 B．38 C．51 D．75
10. 表达式a*(b+c)-d的后缀表达形式为 (10) 。
A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd
11. 若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为
(11) 。
A．DEBAFC B．DEFBCA C．DEBCFA D．DEBFCA
12. 在常用的描述二叉排序树的存储结构中，关键字值最大的节点 (12) 。
A．左指针一定为空 B．右指针一定为空
C．左右指针均为空 D．左右指针均不为空
13. 由权值为9，2，5，7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为 (13) 。
A．23 B．37 C．44 D．46
14. 在一棵完全二叉树中，其根的序号为1， (14) 可判定序号为p和q的两个节点是否在同一层。
A．[logp]=[log2q) B．log2 p=log2 q
C．[log2 p]+1=[log2q) D．[log2 p]=[log2 q)+1
二叉树的深度为k15. 若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子节点的个数为 (15) 。
A．4 B．5 C．6 D．7
16. 在一棵度为3的树中，若有2个度为3的节点，有1个度为2的节点，则有 (16) 个度为0的节点。
A．4 B．5 C．6 D．7
17. 设节点x和y是二叉树中任意的两个节点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是 (17) 。
A．x是y的左兄弟 B．x是y的右兄弟
C．x是y的祖先 D．x是y的后裔
18. 一个具有767个节点的完全二叉树，其叶子节点个数为 (18) 。
A．383 B．384 C．385 D．386
19. 若一个具有n个节点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有 (19) 棵树。
A．k B．n C．n-k D．n+k
一棵查二叉树，其节点A，B，C，D，E，F依次存放在一个起始地址为n(假定地址以字节为单位顺序编号)的连续区域中，每个节点占4字节，前二字节存放节点值，后二字节依次放左指针、右指针。
若该查二叉树的根节点为E，则它的一种可能的前序遍历为 (20) ，相应的层次遍历为 (21) 。在以上两种遍历情况下，节点c的左指针LC的存放地址为 (22) ，LC的内容为 (23) 。节点A的右指针RA的内容为 (24) 。
20. A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
21. A．EAFCBD B．EFACDB C．EABCFD D．EACBDF
22. A．n+9 B．n+10 C．n+12 D．n+13
23. A．n+4 B．n+8 C．n+12 D．n+16
24. A．n+4 B．n+8 C．n+12 D．n+16
25. 某工程计划图如图8-6所示，弧上的标记为作业编码及其需要的完成时间(天)，作业E最迟应在第 (25) 天开始。
A．7 B．9 C．12 D．13
26. 拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系， (26) 为图8-7所示有向图的一个拓扑序列。
A．1 2 3 4 5 6 7 B．1 5 2 6 3 7 4 C．5 1 2 6 3 4 7 D．5 1 2 3 7 6 4
在活动图8-8中，节点表示项目中各个工作阶段的里程碑，连接各个节点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从A到J的关键路径是 (27) ，关键路径长度是 (28) ，从E开始的活动启动的最早时间是 (29) 。
27. A．ABEGJ B．ADFHJ C．ACFGJ D．ADFB
28. A．22 B．49 C．19 D．35
29. A．10 B．12 C．13 D．15
简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个节点，其邻接矩阵为, 1..n]，且压缩存储在B[1..k]中，则k的值至少为 (30) 。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[ (31) ]中。
30. A．n(n+1)/2 B．n2/2 C．(n-1)(n+1)/2 D．n(n-1)/2
31. A．18 B．19 C．20 D．21
32. 无向图中一个顶点的度是指图中 (32) 。
A．通过该顶点的简单路径数 B．通过该顶点的回路数
C．与该顶点相邻接的顶点数 D．与该顶点连通的顶点数
33. 一个具有n(n＞0)个顶点的连通无向图至少有 (33) 条边。
A．n+1 B．n C．n/2 D．n-1
为在状态空间树中 (34) ，可以利用LC-检索(Least Cost Search)快速到一个答案节点。在进行LC-检索时，为避免算法过分偏向于作纵深检查，应该 (35) 。
34. A．出任一个答案节点 B．出所有的答案节点
C．出最优的答案节点 D．进行遍历
35. A．使用精确的成本函数c(.)来作LC-检索
B．使用广度优先检索
C．使用深度优先检索
D．进行遍历
36. 一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有 (36) 个零元素。
A．e B．2e C．n2-e D．n2-2e
37. 若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵 (37) 。
A．第i行中值为1的元素个数
B．所有值为1的元素总数
C．第i行及第i列中值为1的元素总个数
D．第i列中值为1的元素个数
38. 关键路径是指AOE(Activity On Edge)网中 (38) 。
A．最长的回路 B．最短的回路
C．从源点到汇点(结束顶点)的最长路径 D．从源点到汇点(结束顶点)的最短路径
39. 若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G至少有 (39) 个顶点。
A．11 B．10 C．9 D．8
己知AOE网中顶点v1～v7分别表示7个事件，弧a1～a10分别表示10个活动，弧上的数值表示每个活动花费的时间，如图8-9所示。那么，该网的关键路径的长度为 (40) ，活动 a6的松弛时间(活动的最迟开始时间—活动的最早开始时间)为 (41) 。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论