2016年聊城大学计算机学院数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ） A. B. C. D.
答:D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
2． 主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）
A .10 Mbps
B. 20 Mbps
C.80 Mbps
D.100 Mbps
答:C 【解析】
3． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。
A. 仅1
B. 仅2
C. 仅 1，2
D. 仅 2, 3
答:C
【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响
4． 对于栈操作数据的原则是（ ）。
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
答:B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
5． 在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
答:D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于
上。
6． 栈和队的共同点是（ ）。
A. 都是先进后出
B. 都是后进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
答:C
【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。
7． 在页式存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady 异常现象的是（ ）。
I . LRU 算法
A. 仅 II
B .仅 I II
C. 仅I III
D. 仅 II III
答:A
【解析】Belady 现象只有FIFO 算法才会出现
8． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希（Hash ）表
B. 广度优先搜索网
的结点II. FIFO 算法 III. OPT 算法
C. 前序（根）遍历二叉树
D. 深度优先搜索网
答:B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
9． 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的是（ ）
I. 处理越界错 II. 置换页 III. 分配内存
A. 仅I 、II
B .仅II 、III
C. 仅I 、III
D.I 、II 、和III
答:B
【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。
10．下列选项中，不能改善磁盘设备性能的是（ ）。
A. 重排请求次序
B. 在一个磁盘上设置多个分区
C. 预读和滞后写
D. 优化文件物理块的分布
答:B 。
【解析】磁盘
的一个瓶颈。“重排性能主要是指其读写速度。相对而言，磁盘的性能是计算机性能提高请求次序”可以优化磁臂调度的算法，减少读写时间，故正确；“预读和滞
性能，后写”是利用内存作为磁盘的缓存，使得对磁盘的访问变为对内存的访问，也可以在总体上提高其性能；“优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间，也可以提高磁盘
而磁盘分区仅在磁盘空间的组织上进行划分， 对磁盘
性能的提升没有什么帮助，是不能改善磁盘设备性能的，故答案为B 。
二、填空题
11．顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
答:物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
相关内容
相关标签