2017年电子科技大学基础与前沿研究院820计算机专业基础之数据结构考研题库
● 摘要
一、选择题
1． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
2． 用户程序发出磁盘I/O请求后，系统的正确处理流程是（ ）。
A. 用户程序—系统调用处理程序—中断处理程序—设备驱动程序
B. 用户程序—系统调用处理程序—设备驱动程序—中断处理程序
C. 用户程序—设备驱动程序—系统调用处理程序—中断处理程序
D. 用户程序—设备驱动程序—中断处理程序—系统调用处理程序
【答案】B
【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程 序中发起一次系统调用，操作系统的内核接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备， 即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，正确的顺序应该是用户到系统调用到驱动到中断处理。中断处理处于最底层。
3． 某计算机存储器按字节编址，主存地址空间大小为64MB ，现用4Mx8位的RAM 芯片组成32MB 的主 存储器，则存储器地址寄存器MAR 的位数至少是（ ）。
A.22 位
B.23 位
C.25 位
D.26 位
【答案】D
【解析】虽然实际的主存储器（RAM 区）只有32MB , 但不排除还有ROM 区，考虑到存储器
扩展的需要， MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
4．
某系统正在执行三个进程
例如下表所示。
和各进程的计算（CPUCPUCPU
）时间和时间比
为提高系统资源利用率，合理的进程优先级设置应（ ）
A.
B.
C.
D.
【答案】B
【解析】为了合理地设置进程优先级，应该将进程的CPU 利用时间和时间做综合考虑，故答案选B 。
5． 在页式存储管理系统中，采用某些页面置换算法，会出现Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady 异常现象的是（ ）。
I . LRU 算法
A. 仅 II
B .仅 I II
C. 仅I III
D. 仅 II III
【答案】A
【解析】Belady 现象只有FIFO 算法才会出现
6． 下列程常段的时间复杂度是（ ）
A.
B.
C.
D.
【答案】C
【解析】外部循环的退出条件是而对于k ，每次循环都执行II. FIFO 算法 III. OPT 算法 所以循环次数为
内部循环的退出条件是对于j ，每次循环都执行所以每次循环次数为n 次。所以此程序段的时间复杂度为O 即选C 。
7． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有
由此可得对应的平衡二叉树如下图所示。
8． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A.1, 2.3.4
B.2，3, 4.1
C.3, 2, 4, 1
D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
从左至右，这8棵二叉树的中序序列分别为：
（1）4. 3. 2. 1，
（2）3, 4, 2, 1
（3）2, 4, 3, 1
相关内容
相关标签