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

一、单选题

1． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组B[l...(n(n＋1))/2]中，则在B 中确定a ij (i＜j) 的位置k 的关系为（ ）。

A.i*(i﹣1)/2＋j

B.j*(j﹣1)/2＋i

C.i*(i＋1)/2＋j

D.j*(j＋1)/2＋i

【答案】B

【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为n(n＋1)/2。对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)

依次存放于一维数组

中，当i ＜j 时，i 与k 的关系为j*(j﹣1)/2＋i 。

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

A. B. C. D.

【答案】A

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

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

3． 下面关于串的叙述中，不正确的是（ ）。

A. 串是字符的有限序列

B. 空串是由空格构成的串

C. 模式匹配是串的一种重要运算

D. 串既可以采用顺序存储，也可以采用链式存储

【答案】B

【解析】空格构成的串称空格串。空串用

符，因此B 项不正确。

第 2 页，共 41 页 表示。零个字符的串称为空串，空格也是一个字

4． 假定编译器将赋值语句“x=x+3; ”转换为指令”add xaddt, 3”, 其中xaddt 是x 对应的存储单元地址, 若执行该指令的计算机采用页式虚拟存储管理方式, 并配有相应的TLB , 且Cache 使用直写(Write Through)方式, 则完成该指令功能需要访问主存的次数至少是（ ）。

A.0

B.1

C.2

D.3

【答案】C

【解析】采用页式虚拟存储管理方式时, 若页表全部放在内存中, 则存取一个数据最少要访问两次内存:第一次是访问页表, 得到所存取的数据或指令的物理地址; 第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中, 如果给出的地址在TLB 中, 则直接根据该地址取数据或指令, 仅需要一次访问内存。Cache 使用直写方式时, 计算完需要将数据写回到内存中, 因此完成整个指令功能至少需要访问主存2次。

5． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）

A.O(2n)

B.O(n)

C.O(n2)

D.O(log2n )

【答案】C

【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。

6． 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3, 这些资源总数分别为18、6、222。时刻的资源分配情况如下表所示, 此时存在的一个安全序列是（ ）。

表 资源分配情况表

A.P0, P2, P4, P1, P3

B.P1, P0, P3, P4, P2

C.P2, P1, P0, P3, P4

D.P3, P4, P2, P1, P0P0

【答案】D 。

【解析】典型的死锁避免算法、银行家算法的应用。分析一下下表, 可以看到, P3, P4, P2, P1, P0

第 3 页，共 41 页

运行是可以的。

表

本题也可以排除法, 时刻可用资源是R1, R2, R3分别为2, 3, 3, 此时刻, P0需要R1, R2, R3分别为2, 3, 7, 故排除A , P1需要R1, R2, R3分别为1, 3, 3, P2还需要资源R1, R2, R3分别为0, 0, 6, 故C 排除, P3需要R1, R2, R3分别为2, 2, 1。所以正确答案在B , D 之间。

看B 选项, P1之后的可用资源R1, R2, R3分别变为6, 3, 6, 而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。

7． 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 元素a , b , c , d , e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是（ ）。

A.b , a , c , d , e

B.d , b , a , c , e

C.d , b , c , a , e

D.e , c , b , a , d

【答案】C

【解析】根据题意, 队列两端都可以输入数据元素, 但是只能在一端输出数据元素, 这种队列为

输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队, 从而得出不可能的情况。

假设L 代表从左端入队, R 代表从右端入队, 出队都是从左端L 出。四个选项所给序列的进队操作序列分别为:

选项A.aL(或aR) , bL , cR , dR , eR

选项B.aL(或aR) , bL , cR , dL , eR

选项C. 不可能出现选项

D.aL(或aR) , bL , cL , dR , eL

8． 用有向无环图描述表达式

A.5

B.6

C.8

D.9

【答案】A

【解析】一共5个结点

，6条边

第 4 页，共 41 页 ，至少需要顶点的数目为（ ）。 。