当前位置：问答库＞考研试题

一、选择题

1． 冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。

A. 指令操作码的译码结果 B. 指令和数据的寻址方式 C. 指令周期的不同阶段 D. 指令和数据所在的存储单元 【答案】C

【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。

2． 分区分配内存管理方式的主要保护措施是（ ）。

A. 界地址保护 B. 程序代码保护 C. 数据保护 D. 栈保护 【答案】A

【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。

3． 希尔排序的组内排序采用的是（ ）。

A. 直接插入排序 B. 折半插入排序 C. 快速排序 D. 归并排序 【答案】A

【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增

量足够小）时，再对全体元素进行一次直接插入排序。

4． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。

A.4 B.5 C.6 D.7

【答案】C

【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个全二叉树的高度为

或

结点的完

由完全二叉树类推到完全三叉树可知，n 个结点的完全三

叉树的高度为

或

5． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于

中，那么第i 行的对角元素【答案】A

【解析】

中列标不大于行标，

又

存放在

中，

所以

存放于B 中（ ）处。

存

存放的位置为

6． 在下列表述中，正确的是（ ）

A. 含有一个或多个空格字符的串称为空格串 B.

对

个顶点的网，求出权最小的

条边便可构成其最小生成树

C. 选择排序算法是不稳定的

D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1 【答案】C

【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。

7． 下列选项中，不可能是快速排序第2趟排序结果的是（ ）

A.2, 3, 5, 4, 6, 7, 9 B.2, 7, 5, 6, 4, 3, 9 C.3, 2, 5, 4, 7, 6, 9 D.4, 2, 3, 5, 7, 6, 9

【答案】C

【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果

8． —个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）

A. 修改进程状态为就绪态 B. 降低进程优先级 C. 进程分配用户内存空间 D. 增加进程的时间片大小 【答案】A

【解析】进程等待的操作完成便会从等待状态转移到就绪状态。

9． 下列选项中，操作系统提供的给应用程序的接口是（ ）。

A. 系统调用 B. 中断 C. 库函数 D. 原语 【答案】A

【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口复杂调用（例如多种

，以及包含在）

自然命令用户接口

等，而系统调用中除了常规的一些传统的系统调用（例如read （ ））以外，还有经过扩展的

库中的各种封装好的过程调用（最终都是通过系统调

用陷入到操作系统中去的）等。

10．某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）

A.9 B.10 C.11 D.12

【答案】B

【解析】2+3+4+1 = 10

二、填空题

11．对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

12．应用prim 算法求解连通网络的最小生成树问题。

（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。