2017年内蒙古科技大学信息工程学院843数据结构考研冲刺密押题
● 摘要
一、选择题
1． 在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于上。
2． 在缺页处理过程中，操作系统执行的操作可能是（ ）。
I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I 、II B. 仅II C. 仅III D.I 、II 和III 【答案】D
【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页）
驱动程序做磁盘1/0, 将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改 页表，将，将物理页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返 回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。
第 2 页，共 71 页
的结点
3． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）。
A. 命令解释程序 B. 中断处理程序 C. 系统调用服务程序 D. 用户登录程序 【答案】B
【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理是：利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受，中断则会停止当前进程的运行，转而服务发出中断的物理设备（注意与陷阱，即软中断有区别）那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型（不同外设不同）计算所得，或计算机系统在开机配置时所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候（一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器（例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面。
4． 归并排序中，归并的趟数是（ ）。
【答案】B
【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n
。因此每次归并元素的个数增加一倍。所以
所以归并的趟数为
5． 两台主机之间的数据链路层采用后退N 帧协议（GBN ）传输数据，数据传输速率为16kbps ，单向传播时延为270ms ，数据帧长度范围是128〜512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（ ）。
A.5 B.4 C.3 D.237
【答案】B 。
【解析】GBN 的工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因
此首先计算出发送一帧的时间
这段时间总共可以发送
故发送一帧到收到确认为止的总时间为
，为了保证发送帧序号和确认帧（帧）
序号在此期间不重复，因此帧序号的比特数至少为4, 答案为B
第 3 页，共 71 页
6． 下列调整中，不可能导致饥饿现象的是（ ）
A. 时间片转移 B. 静态优先及调度 C. 非抢占式作业优先 D. 抢占式短作业优先 【答案】A
【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。
7． 下列选项中，会导致用户进程从态切换到内核的操作是（ ）
I. 整数除以零 II. Sin（ ）函数调用 III. read系统调用 A. 仅 I 、II B .仅 I 、III C. 仅II 、III D. I、II 和III 【答案】B
【解析】对于I ，系统发生异常，需要进入内核态由操作系统进行处理，而read 系统调用函数也是在内核态执行，sin （ ）就是普通的用户函数，在用户态执行，故答案为C 。
8． 假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地 址2000H 中的内容为3000H ，地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H B.2000H C.3000H D.4000H 【答案】D
【解析】根据变址寻址的作数的实际地址，
由题可知4000H 。
第 4 页，共 71 页
变址寄存器的内容与形式地址的内容相加之后得到操
根据实际地址访问内存，获取操作数
相关内容
相关标签