2017年常州大学艺术学院858数据结构考研仿真模拟题
● 摘要
一、选择题
1． 当系统发生抖动（thrashing ）时，可以采取的有效措施是（ ）。
I. 撤销部分进程
II. 增加磁盘交换区的容量
III. 提高用户进程的优先级
A. 仅I
B. 仅 II
C. 仅III
D. 仅 I 、II
【答案】A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页
必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，
引起系统性能下降甚至崩溃。 引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交 换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统 来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情 况下增加物理内存
，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的 问条）
题，提高用户进程的优先级会使系统的状态更加恶化。
2． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。 A.
B.
C.
D. 字节 字节 字节 字节
【答案】C
【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为B 。
3． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
4． n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
5． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
【答案】A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是 ，则有语句设其执行时间为T （n ）
6． 在子网192.168.4.0/30中， 能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。
A.0
B.1
C.2
D.4
【答案】C
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C 。
7． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N-1
C.2N
D.N-1
【答案】A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为
8． 下列关于最小生成树的叙述中，正确的是（ ）。
I . 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中III. 使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同IV. 使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同
A. 仅I
B. 仅II
C. 仅 I 、III
D. 仅 II 、IV
【答案】A 。
【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价
所以说法I 正确。一定是相同的，从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路，
所以说法II 错误。当某个顶点有权值相同的边，使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法III 错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Krnskal ）算法得到的最小生成树可能相同，也可能不同，所以说法IV 错误。由此可得出正确答案。
9． 下列关于UDP 协议的叙述中，正确的是（ ）
I 提供无连接服务
II 提供复用/分用服务
III 通过差错校验，保障可靠数据传输
A. 仅I
B. 仅 I 、II
C. 仅 II 、III
D.I 、II 、III
【答案】B
【解析】UDP 无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以III 错误。
10．某计算机有五级中断的顺序为
A.11110
B.01101
C.00011
D.01010
【答案】D
【解析】由于则中断屏蔽字为表示对级中断进行屏蔽。若中断响应优先级从高到低的顺序是且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。 B 排除掉。的中断处理优先级下降，屏蔽字中需要3个0, 所以可以将选项A 、
相关内容
相关标签