2018年福建师范大学光电与信息工程学院841计算机专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 下列选项中, 在
Ⅰ.
Ⅱ. 总线的数据线上传输的信息包括（ ）。 接口中的命令字 接口中的状态字
Ⅲ. 中断类型号
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ、Ⅲ
【答案】D 。
【解析】在总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据, 而中断类型号也是通过数据线传输的。
2． 对矩阵压缩存储是为了（ ）。
A. 方便运算
B. 方便存储
C. 提高运算速度
D. 减少存储空间
【答案】D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
3． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.
B.n/2 C.
D.n
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
。
第 2 页，共 35 页 那么
4． 广义表A ＝(a，b ，(c，d) ，(e，(f，g))) ， 则式子Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
A.(g)
B.(d)
C.c
D.d
【答案】D
【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。也就是tail 得到的元素需要在外层再加一个（ ）。
5． 在采用中断方式控制打印输出的情况下, CPU 和打印控制接口中的
息不可能是（ ）。
A. 打印字符
B. 主存地址
C. 设备状态
D. 控制命令
【答案】B 【解析】接口的功能包括:①选址功能; ②传送命令功能; ③传送数据功能; ④反映
要的, 因此, 它不可能是CPU 和打印控制接口中的端口之间交换的信息。
6． 从堆中删除一个元素的时间复杂度为（ ）。
A.O(1) B.
C.O(n) D.
【答案】B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
7． 为实现快速排序算法, 待排序序列宜采用的存储方式是（ ）。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
【答案】A
【解析】对绝大部分内部排序而言, 只适用于顺序存储结构, 快速排序在排序过程中, 既要从后向前查找, 也要从前向后查找, 因此宜采用顺序存储。
。 设备工作状态功能。A 项为数据, C 项为设备状态, D 项为命令。B 项, 主存地址在中断方式控制下是不需端口之间交换的信
第 3 页，共 35 页
8． 假设某计算机的存储系统由Cache 和主存组成. 某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.
A.5% B.
C.50%
D.95%
【答案】D
【解析】Cache 的命中率H ＝N 1(N1＋N 2) ，其中N 1为访问Cache 的次数，N 2为访存主存的次数，程序总访存次数为N 1＋N 2，程序访存次数减去失效次数就是访问Cache 的次数队. 所以根据公式可得：H ＝(1000﹣50) /100＝95%.
9． 对如下所示的有向图进行拓扑排序, 得到的拓扑序列可能是（ ）
A.3, 1, 2, 4, 5, 6
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
10．某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为字节，页表项大小为2字节，逻辑地址结构为:
逻辑地址空间大小为
（ ）.
A.64
B.128
C.256
D.512
第 4 页，共 35 页 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是