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

一、选择题

1． —个栈的入栈序列为的个数是（ ）

A.n-3 B.n-2 C.n-1

D. 无法确定

【答案】C

【解析】除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。

2． 下列选项中，用于设备和控制器（’接口）之间互连的接口标准是（ ）

A.PCI B.USB C.AGP

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

3． 将森林F 转换为对应的二叉树T , F中叶结点的个数等于（ ）

A.T 中叶结点的个数 B.T 中度为1的结点个数 C.T 中左孩子指针为空的结点个数 D.T 中右孩子指针为空的结点个数 【答案】C

【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩 子指针指向当前节点的兄弟节点，所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以 选C

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

中，那么第i 行的对角元素

存放于B 中（ ）处。

【答案】A

【解析】

其出栈序列是若，则则可能取值

存

中列标不大于行标，

又

存放在中，

所以

存放的位置为

5． 对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ）

A. B. C. D.

【答案】C

【解析】基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小进行排序的，故答案是C 选项。

6． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。

A. 直接插入排序 B. 起泡排序 C. 简单选择排序 D. 快速排序 【答案】A

【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需

趟排序，也即时间复杂度仍为

而对

简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）

n-1趟，

比较的时间复杂度由 降至

7． 下列选项中，导致创建新进程的操作是（ ）。

用户登录成功

设备分配

启动程序执行 A. 仅和B. 仅和C. 仅和D.

和

【答案】C

【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间（主要涉及资源分配需要协调），也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”

统填写进程ID 号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。

8． 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）

A.5 B.6 C.8 D.9

【答案】C 【解析】

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

所以至少需要8位才能表示完130个地址。

G 的拓扑序列是

（ ）。

【答案】A

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

能被称

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

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

是

10．将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。

A. 串 B. 树 C. 广义表 D. 栈 【答案】C

【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。

二、填空题