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

一、单项选择题

1．

操作系统的

A. 用户级

B. 用户级

C. 用户级

D. 用户级

【答案】A 。

【解析】对于一次设备的调用, 操作系统为用户准备了系统调用的接口, 当用户使用设备时, 首先在用户程序中发起一次系统调用, 操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理, 根据调用格式和形参, 再转到相应的设备驱动程序去处理; 大部分设备在运行时是需要时间的, 所以设备驱动程序会以中断方式驱动设备, 即设置好控制寄存器参数和中断向量等参数后阻塞自己; 当设备准备好或所需数据到达后设备硬件发出中断, 设备驱动程序唤醒, 将数据按上述调用顺序逆向回传到用户程序中, 或继续驱动设备执行下一条指令。因此, 软件从上到下分为四个层次:用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

2． 用直接插入排序方法对下面4个序列进行排序(由小到大) ，元素比较次数最少的是（ ）。

A.94，32，40，90，80，46，21，69

B.32，40，21，46，69，94，90，80

C.21，32，46，40，80，69，90，94

D.90，69，80，46，21，32，94，40

【答案】C

3． 已知有向图G=(V，E) , 其中

,

G 的拓扑序列是（ ）。 A.

B.

C. D.

【答案】A

能被称为

子系统通常由四个层次组成, 每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序 的层次组织排列顺序是（ ）。 【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列

拓扑序列的条件:若

在顶

点是图中的边(即从顶点。 到有一条路径) ，则在序列中顶点必须排之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列

是

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

Ⅰ. 回路是简单路径

Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间

Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路

A. 仅Ⅱ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅲ

【答案】C

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

5． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A.0(n)

B.0(n+e) C. D.

【答案】B

【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)

6． 已知一棵有2011个结点的树, 其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。

A.115

B.116

C.1895

D.1896

【答案】D

【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点(因为一个非终端结点至少有一个孩子结点, 其最右边的孩子结点转换成二叉树后一定没有右孩子) , 另外, 树根结点转换成二叉树后也没有右孩子。题目中树的总结点数是2011, 叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中无右孩子的结点个数是1895+1=1896。

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

A. 表元素

B. 字符

C. 数据元素

D. 数据项

E. 信息项

【答案】C

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

8． 下列选项中, 用于设备和控制器(

A.PCI

B.USB

C.AGP D.

【答案】B 接口) 之间互连的接口标准是（ ）

【解析】设备和设备控制器之间的接口是USB 接口, 其余选项不符合, 故答案为B 。

9． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.

B.n/2 C.

D.n

【答案】C

【解析】最快查找一次成功，最慢查找n

次成功。平均查找次数为

。

10．执行（ ）操作时，需要使用队列做辅助存储空间。

A. 查找哈希(Hash)表

B. 广度优先搜索网

C. 前序(根) 遍历二叉树

D. 深度优先搜索网

【答案】B

【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。

那么