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

一、单项选择题

1． 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A. 二叉排序树

B. 哈夫曼树

C.A VL 树

D. 堆

【答案】D

【解析】堆的定义:

n 个关键字序列K 1，K 2，... ，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :

(1)

(2)

且且或

满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。

由堆的定义可知堆可以满足上述性质。

2． 已知一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，则该完全二叉树的结点个数最多是（ ）.

A.39

B.52

C.111

D.119

【答案】C

【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层. 题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度. 根据题意，一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，可知此二叉树的高度是6或7. 题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7. 由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是

目中二叉树的第6层结点数是

可达

. 又根据二叉树的性质1可知，题个结点，已知有8个叶子结点，那么其余32﹣8＝24个结点均为分支结点，这些结点在第7层上最多有48个子结点(即叶子结点). 所以此二叉树的结点数最多

3． —个进程的读磁区操作完成后, 操作系统针对该进程必做的是（ ）

A. 修改进程状态为就绪态

B. 降低进程优先级

C. 进程分配用户内存空间

D. 增加进程的时间片大小

【答案】A

【解析】进程等待的操作完成便会从等待状态转移到就绪状态。

4． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A.N

B.2N －1

C.2N

D.N －1

【答案】A

【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。

5． 下列指令中, 不能在用户态执行的是（ ）

A.trap 指令

B. 跳转指令

C. 后找指令

D. 关中断指令

【答案】D

【解析】关中断指令必须在和心态才能执行, trap 指令可以在用户态下执行, 执行了就转到和心态, 跳转与退栈指令都是可以在用户态下执行的指令。

6． 设n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是（ ）。

A. B. C. D.

【答案】A

【解析】其中, 以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语

句

, 设其执行时间为, 则有即。

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

A.3

B.4

C.5

D.6

【答案】B

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

此时可有以下4种操作:

(1)e进栈后出栈, 出栈序列为decba 。

(2)c出栈, e 进栈后出栈, 出栈序列为dceba 。

(3)cb出栈, e 进栈后出栈, 出栈序列为dcbea 。

(4)cba出栈, e 进栈后出栈, 出栈序列为dcbae 。

8． 设图的邻接矩阵A 如下所示, 各顶点的度依次是（ ）

A.1, 2, 1, 2

B.2, 2, 1, 1

C.3, 4, 2, 3

D.4, 4, 2, 2

【答案】C

【解析】当图用邻接矩阵存储时, 各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

9． 用户程序发出磁盘

（ ）

A. 用户程序

B. 系统调用处理程序

C. 设备驱动程序

D. 中断处理程序

请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是