2016年天津职业技术师范大学信息技术工程学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：
序列：页框：
淘汰：3。
2． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。
访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是
该机的MIPS 数是（ ）
A.100 B.200 C.400 D.600
【答案】C
【解析】基准程序的该机器的
计算机的主频为
为1200MHz ，
3． 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB ，采用页式存储管理，页面大小为4KB ，TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。
则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ） A.0153180H B.0035180H C.TLB 缺失 D. 缺页 【答案】A
【解析】虚拟地址为03FFF180H ，其中页号为03FFFH , 页内地址为180H ，根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H , 页框号与页内地址之和即为物理地址015 3180H。
4． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）
A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2 【答案】C
【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
5． 5个字符有如下4种编码方案，不是前缀编码的是（ ）
A. B. C. D. 【答案】D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符
则可以用从根结点到叶子结点的路径上的分支字符串作为该叶
子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故
不符合前缀编码的定义。
6． 设栈S 和队列Q 的初始状态均为空，元素a , b , c ，d ，e , f ，g 依次进入栈S 。若每个元素出栈 后立即进入队列Q ，且7个元素出队的顺序是b ，d ，c ，f , e , a ，g ，则栈S 的容量至少是（ ）。
A.1 B.2 C.3 D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b , 表明栈内还有元素a ，b 出栈前的深度为2; 第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3; c 出栈后，剩余元素为a ，c 出栈前的深度为2; f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3; e 出栈后，剩余元素为a ，e 出栈前的深度为2; a 出栈后，无剩余元素，a 出栈前的深度为1; g 出栈后，无剩余元素，g 出栈前的深度为1。所以栈容量至少是3。
7． 下列选项中，操作系统提供的给应用程序的接口是（ ）。
A. 系统调用 B. 中断 C. 库函数 D. 原语 【答案】A
【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口复杂调用（例如多种
，
以及包含在）
自然命令用户接口
等，而系统调用中除了常规的一些传统的系统调用（例如read （ ））以外，还有经过扩展的
库中的各种封装好的过程调用（最终都是通过系统调
用陷入到操作系统中去的）等。
8． 某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的百分比至少是（ ）
A. B. C. D. 【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的百分比为
时间占用CPU 时间
中断响应容许的延迟时间对此没有影响，属于干扰条件。
时间占整个CPU 时间