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

一、单项选择题

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

,

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

B.

C. D.

【答案】A

拓扑序列的条件:若

在顶

点 能被称为必须排

【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列是图中的边(即从顶点。

2． 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）.

A. 时间片轮转调度算法

B. 短进程优先调度算法

C. 先来先服务调度算法

D. 高响应比优先调度算法

【答案】D 到有一条路径) ，则在序列中顶点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列

是

【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间. 最高响应比优先调度算法是最先执行响应比最高的进程(响应比＝1＋等待时间/估计运行时间). 该算法综合了先来先服务(FCFS)和短作业优先(SJF)算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短.SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间.

3． 用哈希(散列) 方法处理冲突(碰撞) 时可能出现堆积(聚集) 现象, 下列选项中, 会受堆积现象直接影响的是（ ）

A. 存储效率

B. 数列函数

C. 装填(装载) 因子

D. 平均查找长度

【答案】D

【解析】哈希方法冲突会使在查找冲突的关键字时, 还要根据冲突处理办法多次比较关键字, 则直接影响了平均查找长度。

4． 下列寄存器中, 汇编语言程序员可见的是（ ）。

A. 存储器地址寄存器(MAR)

B. 程序计数器(PC)

C. 存储器数据寄存器(MDR)

D. 指令寄存器(IR)

【答案】B

【解析】CPU 有5个专用寄存器, 它们是程序计数器(PC)、指令寄存器(IR)、存储器地址寄存器(MAR)、存储器数据寄存器(MBR)和状态标志寄存器(PSWR), 这些寄存器中有些是CPU 的内部工作寄存器, 对汇编语言程序员来说是透明的, 在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值, 所以程序计数器(PC)对于汇编语言程序员可见的。

5． 用希尔排序方法对一个数据序列进行排序时, 若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15, 则该趟排序采用的增量(间隔) 可能是（ ）

A.2

B.3 C.4

D.5

【答案】B

【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组, 而它们是无序的, 所以A 错误

对于C , 增量为4, 那么9, 7, 15是一组, 而它们是无序的, 所以C 错误

对于D , 增量为5, 那么9, 8是一组, 降序, 1, 20是一组, 而它们是升序, 所以D 也错误。对于B , 分为3组:9, 13, 20; 1, 7, 23; 4, 8, 15都是升序有序, 所以B 正确

6． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1, 则该二叉树的中序遍历序列不会是（ ）。

A.1, 2, 3, 4

B.2, 3, 4, 1

C.3, 2, 4, 1

D.4, 3, 2, 1

【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反, 这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右, 这8棵二叉树的中序序列分别为:

(1)4, 3, 2, 1,

(2)3, 4, 2, 1

(3)2, 4, 3, 1

(4)2, 3, 4, 1

(5)1, 4, 3, 2

(6)1, 3, 4, 2

(7)1, 2, 4, 3

(8)1, 2, 3, 4

显然选项C 的中序序列不会出现。

7． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。

A. 顺序存储方式

B. 链式存储方式

C. 散列存储方式

D. 以上均可以

【答案】B

8． 单链表中，增加一个头结点的目的是为了（ ）。

A. 使单链表至少有一个结点

B. 标识表结点中首结点的位置

C. 方便运算的实现

D. 说明单链表是线性表的链式存储

【答案】C

【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。

9． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A.4

B.5

C.6