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

一、选择题

1． 排序算法的稳定性是指（ ）。

A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C. 算法的排序性能与被排序元素的数量关系不大 D. 算法的排序性能与被排序元素的数量关系密切 【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，

且在之前，而在排序后的序列中，仍在

之前，则称这种排序算法是稳定的；否则称为不稳定的。

2． 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程 中元素之间进行的比较次数是（ ）。

A.1 B.2 C.4 D.5

【答案】B

【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆， （2）为插入18后，

（3）比较10与18，交换后，

（4）比较25与18, 不交换，即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。

3． 下列关于图的叙述中，正确的是（ ）。

I. 回路是简单路径

II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A. 仅 II B. 仅 I 、II C. 仅III D. 仅 I 、III 【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，所以选项I 错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项II 错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，图中存在回路。所以选项III 正确。

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

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

【解析】 5． 若串

A.8 B.37 C.36 D.9

【答案】B

【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为长为为：

存

存放于B 中（ ）处。

中列标不大于行标，

又

其子串的数目是（ ）。

存放在中，

所以

存放的位置为

长为n 的子串有1个，长为的子串有2个，

的子串有3个，……，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案

故选B 。

6． 已知有向图G=（V ，E ），其中

G 的拓扑序列是

（ ）。

【答案】A

【解析】设G=（V ，E ）是一个具有n 个顶点的有向图，V 中顶点序列

能被称

，则在序列中顶点Vi 为拓扑序列的条件：若是图中的边（即从顶点V i 到V j 有一条路径）

必须排在顶点Vj 之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列

是

7． 在缺页处理过程中，操作系统执行的操作可能是（ ）。

I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I 、II B. 仅II C. 仅III D.I 、II 和III 【答案】D

【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页）

驱动程序做磁盘1/0, 将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改 页表，将，将物理页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返 回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。

8． 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB ，采用页式存储管理，页面大小为4KB ，TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。