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

一、选择题

1． 线性表是具有n 个（ ）的有限序列（n ＞0）。

A. 表元素 B. 字符 C. 数据元素 D. 数据项E. 信息项 【答案】C

【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。

2． 在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（ ）。

A. 编辑 B. 编译 C. 链接 D. 装载 【答案】B

【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本，不涉及到任何与计算机运 行相关的事；编译是由编译程序将用户源代码编译成若干个目标模块，源地址编译成目标程序时，会形成逻辑地址；链接是由链接程序将编译后形成的一组目标模块，以及所需库函数链接，形成完整的装入模块；装入是由装入程序将装入模块装入内存。

3． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）

A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图

D.G 所有顶点的度的总和为n （n-1） 【答案】A

【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。

4． 栈和队的共同点是（ ）。

A. 都是先进后出 B. 都是后进先出

C. 只允许在端点处插入和删除元素 D. 没有共同点 【答案】C

【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。

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

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

对

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

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

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

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

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

6． 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。

A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35 C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 34 【答案】A

【解析】各选项对应的查找过程如下图所示，从中看到选项B 、C 、D 对应的查找树都是二叉排序树，只有选项A 对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。

7． 设有向图G= （V ，E ），顶点集V={V0, VI ，V2, V3}，边

集

若从顶点V0开始对图进行深度优先遍历，则可

能得到的不同遍历序列个数是（ ）。

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

【答案】D

【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可 能得到的不同遍历序列分别是：

8． 就平均性能而言，目前最好的内排序方法是（ ）排序法。

A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D

【解析】快速排序的平均时间复杂度是复杂度也是

所需要的辅助存储为

仅仅表示的是一个量级，

比如

所需要的辅助存储为和

的量级都为

虽然堆排序的时间

之所以说快排

看似堆排序比快速排序的性能好，

但是需要注意

最好，是在综合考虑的情况下。

9． 用户程序发出磁盘I/O请求后，系统的正确处理流程是（ ）。

A. 用户程序—系统调用处理程序—中断处理程序—设备驱动程序 B. 用户程序—系统调用处理程序—设备驱动程序—中断处理程序 C. 用户程序—设备驱动程序—系统调用处理程序—中断处理程序 D. 用户程序—设备驱动程序—中断处理程序—系统调用处理程序 【答案】B

【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程 序中发起一次系统调用，操作系统的内核接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备， 即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述