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

一、单项选择题

1． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。

两个操作完成后, 2的值（ ）。

A. 可能为-1或3

B. 只能为1

C. 可能为0、1或2

D. 可能为-1、0、1或2

【答案】C

【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。

本例中, 由于没有采取保证数据同步的相应措施, 则最后结果就会出现差错。例如, 当正常情况下, 进程P1和P2先后对x 操作, 可以看到x 值的变化为初始

则x 值的变化为初始的过程, 若P2, P1先后操作, , 这是正确的。若考虑一种并发的情况, 进程P1和P2先后执行了取数load 的操作, 它们得到的x 值均为1, 运算后, P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的操作了, 哪个进程后操作, 结果就是那个进程的x 值, 所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。

2． 下列选项中, 不可能是快速排序第2趟排序结果的是（ ）

A.2, 3, 5, 4, 6, 7, 9

B.2, 7, 5, 6, 4, 3, 9

C.3, 2, 5, 4, 7, 6, 9

D.4, 23, 5, 7, 6, 9

【答案】C

【解析】对于快速排序, 每一趟都会使一个元素位于有序时的位置, 而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比, 只有9位于它有序的时候的位置, 显然不是第二趟快速排序的结果

3． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。

图 有向带权图

A.d , e , f

B.e , d , f

C.f , d , e

D.f , e , d

【答案】C 。

【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。

4． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。

A.push ，pop ，push ，pop ，push ，pop

B.push ，push ，push ，pop ，pop ，pop

C.push ，push ，，pop ，pop ，push ，pop

D.push ，pop ，push ，push ，pop ，pop

【答案】B

【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，push 的数目始终大于等于pop 的数目。

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

A. 二叉排序树

B. 哈夫曼树

C.A VL 树

D. 堆

【答案】D

【解析】堆的定义:

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

(1)

(2)

且且或

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

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

6． 站点A 、B 、C 通过CDMA 共享链路, A 、B 、C 的码片序列(chippingsequence)分别是(1, 1, 1, 1) 、(1, -1, 1, -1) 和(1, 1, -1, -1) , 若C 从链路上收到的序列是(2, 0, 2, 0, 0, -2, 0, -2, 0, 2, 0, 2) , 则C 收到A 发送的数据是（ ）

A.000

B.101

C.110

D.111

【答案】B

【解析】用A 的码片与信息做内积运算

7． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。

A. 必定快

B. 不一定

C. 在大部分情况下要快

D. 取决于表递增还是递减

【答案】C

【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。

8． 下列叙述中，不符合m 阶B 树定义要求的是（ ）.

A. 根结点最多有m 棵子树

B. 所有叶结点都在同一层上

C. 各结点内关键字均升序或降序排列

D. 叶结点之间通过指针链接

【答案】D

【解析】B 树就是指树.

根据树的定义，m

阶

树中每个结点最多有m 个分支，因此，