2018年中国海洋大学基础教学中心教育系938数据结构与程序设计之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 下列寄存器中, 汇编语言程序员可见的是（ ）。
A. 存储器地址寄存器(MAR)
B. 程序计数器(PC)
C. 存储器数据寄存器(MDR)
D. 指令寄存器(IR)
【答案】B
【解析】CPU 有5个专用寄存器, 它们是程序计数器(PC)、指令寄存器(IR)、存储器地址寄存器(MAR)、存储器数据寄存器(MBR)和状态标志寄存器(PSWR), 这些寄存器中有些是CPU 的内部工作寄存器, 对汇编语言程序员来说是透明的, 在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值, 所以程序计数器(PC)对于汇编语言程序员可见的。
2． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11
B.12
C.13
D.14
【答案】B
3． 已知小根堆为8, 15, 10, 21, 34, 16, 12, 删除关键字8之后需重建堆, 在此过程中, 关键字之间的比较数是（ ）。
A.1
B.2
C.3
D.4
【答案】C
【解析】堆排序中, 依次输出堆顶的最小值, 然后重新调整堆, 如此反复执行, 便得到一个有序序列。本题中, 删除堆顶元素8后将最后一个元素12置于堆顶, 然后调整堆:首先与15比较, 12小于15, 所以不用交换; 然后与10比较, 因为10小于12, 所以交换10和12的位置; 调整后12再与16比较, 12小于16, 调整堆过程结束。因此12共与15、10、16进行了三次比较。
4． 在OSI 参考模型中, 直接为会话层提供服务的是（ ）
A. 应用层
B. 表示层
C. 传输层
D. 网络层
【答案】C
【解析】OSI 参考模型中, 下层直接为上层提供服务, 而会话层的下层为传输层。
5． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）
A.007.110.119.114.911.120.122
B.007, 110, 119, 114, 911, 122, 120
C.007, 110, 911, 114, 119, 120, 122
D.110, 120, 911, 122, 114, 007, 119
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。
6． 在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。
A.G 中有弧
C.G 中没有弧
【答案】D
【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。
7． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
A.push ，pop ，push ，pop ，push ，pop
B.push ，push ，push ，pop ，pop ，pop
C.push ，push ，，pop ，pop ，push ，pop
D.push ，pop ，push ，push ，pop ，pop
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，push 的数目始终大于等于pop 的数目。
8． 对如下所示的有向图进行拓扑排序, 得到的拓扑序列可能是（ ）
A.3, 1, 2, 4, 5, 6
B.G 中有一条从到的路径 D.G 中有一条从到的路径
B.3, 1, 2, 4, 6, 5
C.3, 1, 4, 2, 5, 6
D.3, 1, 4, 2, 6, 5
图
【答案】D
【解析】拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0) 的顶点并且输出它;
(2)从图中删去该顶点, 并且删去从该顶点发出的全部有向边;
(3)重复上述两步, 直到剩余的网中不再存在没有前趋的顶点为止。
对于此有向图进行拓扑排序所有序列为:3, 1, 4, 6, 2, 5和3, 1, 4, 2, 6, 5。所以选D
9． 假设栈初始为空, 将中缀表达式
当扫描到f 时, 栈中的元素依次是（ ） A.
B.
C.
D.
【答案】B
【解析】中缀表达式转后缀表达式遵循以下原则:
(1)遇到操作数, 直接输出;
(2)栈为空时, 遇到运算符, 入栈;
(3)遇到左括号, 将其入栈;
(4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出;
(5)遇到其他运算符
符入栈;
(6)最终将栈中的元素依次出桟, 输出。
所以扫描到‟/‟, 入栈„描到‟+‟, 由于‟+‟优先级比‟/'低, 所以将‟/‟弹出, ‟+‟入栈; 扫描到‟*,, 优先级比‟+‟高, 入栈; 扫描到‟(„, 入栈; 扫描到‟一„, 将栈中优先级更高的‟*‟弹出, „一, 入栈; 扫描到‟*‟, 优先级比‟一„高, 入栈。所以扫描至“f的时候, 栈中元素为:+(一*
转换为等价后缀表达式的过程中, 时, 弹出所有优先级大于或等于该运算符的栈顶元素, 然后将该运算