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

一、选择题

1． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。

A. 对称矩阵 B. 稀疏矩阵 C. 三角矩阵 D. —般矩阵 答:C

【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序：①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在 图中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。

2． 下列关于进程和线程的叙述中，正确的是（ ）。

A. 不管系统是否支持线程，进程都是资源分配的基本单位 B. 线程是资源分配的基本单位，进程是调度的基本单位 C. 系统级线程和用户级线程的切换都需要内核的支持 D. 同一进程中的各个线程拥有各自不同的地址空间 答:A 。

“线程是资源分配的基本单位，【解析】利用排除法来确定正确答案：进程是调度的基本单位”这句话说反了，明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确，因为用户级线程的切换由用户编写的RuntimeSystem 执行的，内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误，引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间，故“不管系统是否支持线程，进程都是资源分配的基本单位”是正确的。

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

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

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

4． 某同步总线的时钟频率为所需要的时间至少是（ ）。

A.20ns B.40ns C.50ns D.80ns 答:C 。

宽度为32位，地址/数据线复用，每传输一个地址或数据占用

一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据

【解析】总线的时钟频率为100MHz ，贝时钟周期为10ns 。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5=50ns。

5． —

组记录的关键码为

准得到的一次划分结果为（ ）。

答:C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为

则利用快速排序的方法，以第一个记录为基

一次划分结束。

6． 对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：

第一趟：2，12，16, 5，10，88

第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88 则采用的排序方法可能是（ ）。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 基数排序 答:A

【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若

干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”

序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底”

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

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

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

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

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

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

9． 元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。

A.3 B.4 C.5 D.6 答:B

【解析】d 首先出栈后的状态如下图所示。

此时可有以下4种操作：

（1）e 进找后出栈，出梭序列为decba 。 （2）c 出找，e 进找后出栈，出找序列为dceba 。