2017年西北民族大学中国民族信息技术研究院849计算机学科专业基础之数据结构考研题库
● 摘要
一、选择题
1． 折半查找的时间复杂性为（ ）。
【答案】D
【解析】顺序查找的事件复杂度为度为
子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序
2． 操作系统的
A. 用户级B. 用户级C. 用户级D. 用户级【答案】A 。
【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。 因此，
软件从
上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。
3． 在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（ ）。
A. 可变分配，全局置换 B. 可变分配，局部置换 C. 固定分配，全局置换 D. 固定分配，局部置换 【答案】
【解析】分配和置换策略有下面三个组合：①固定分配、局部置换；②可变分配、全局置换；，或根据程序员、③可变分配、局部置换。固定分配是指基于进程的类型（交互型或批处理型等）
程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变，采用该策
第 2 页，共 54 页
因为折半查找是查找效率最高的算法，它的事件复杂
的层次组织排列顺序是（ ）。
略时，如果进程在运行中发现缺页，则只能从该进程在内存的n 个页面中选出一个页换出，然后再调入一页，才能保证分配给该进程的内存空间不变，因此不能有固定分配，全局置换组合。
4． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是 【答案】A
【解析】顶点Vp 到顶点Vq 之间的一条路径是指顶点序列
，路径上边
的数目称为路径的长度。
5． 两台主机之间的数据链路层采用后退N 帧协议（GBN ）传输数据，数据传输速率为16kbps ，单向传播时延为270ms ，数据帧长度范围是128〜512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（ ）。
A.5 B.4 C.3 D.237
【答案】B 。
【解析】GBN 的工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因
此首先计算出发送一帧的时间
这段时间总共可以发送
故发送一帧到收到确认为止的总时间为
，为了保证发送帧序号和确认帧（帧）
序号在此期间不重复，因此帧序号的比特数至少为4, 答案为
B
6． 某字长为8位的计算机中，y 的机器数分别为已知整型变量x 、若整型变量
A.11000000 B.00100100 C.10101010 D. 溢出
则z 的机器数为（ ）
第 3 页，共 54 页
【答案】A
y 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。
7． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100 B.200 C.400 D.600
【答案】C
【解析】基准程序的
计算机的主频为
为1200MHz ，
该机器的
8． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 【答案】B
9． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
10．float 型整数据常用IEEE754单精度浮点格式表示，假设两个float 型变量x 和y 分别在32为寄存器
和中，若
A. B. C. D.
且符号相同
且符号不同
且符号相同
且符号不同
第 4 页，共 54 页
则x 和y 之间的关系为：（ ）