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

一、单项选择题

1． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。

A.(2，5，12，16)26(60，32，72)

B.(5，16，2，12)28(60，32，72)

C.(2，16，12，5)28(60，32，72)

D.(5，16，2，12)28(32，60，72)

【答案】B

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

第一次比较:28比72小，不交换;

第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;

第三次比较:16比28小，不交换；

第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;

第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;

第六次比较:28比12大，不交换；

第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;

一次划分结束。

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

A. B. C. D.

【答案】A

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

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

3． 主机甲和乙已建立了TCP 连接, 甲始终以MSS=1KB大小的段发送数据, 并一直有数据发送; 乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗口为8KB , 则从t 时刻起, 不再发生超时的情况下, 经过10个RTT 后, 甲的发送窗口是（ ）

A.10KB

B.12KB

第 2 页，共 64 页

C.14KB

D.15KB

【答案】A

【解析】发送窗口是接受窗口和拥塞窗口的最小值, 这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的, 取最小值。

4． 下列关于闪存(FlashMemory)的叙述中, 错误的是（ ）。

A. 信息可读可写, 并且读、写速度一样快

B. 存储元由MOS 管组成, 是一种半导体存储器

C. 掉电后信息不丢失, 是一种非易失性存储器

D. 采用随机访问方式, 可替代计算机外部存储器

【答案】A 。

【解析】考查闪存的特性, 闪存是EEPROM 的进一步发展, 可读可写, 用MOS 管的浮栅上有无电荷来存储信息, 它依然是ROM 的一种, 故写速度比读速度要慢不少。闪存是一种非易失性存储器, 它采用随机访问方式, 现在常见的SSD 固态硬盘就是由flash 芯片组成的, 故答案为A 。

5． 下列关于图的叙述中, 正确的是（ ）。

Ⅰ. 回路是简单路径

Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间

Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路

A. 仅Ⅱ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅲ

【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, 所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间, 稠密图适合用邻接矩阵的存储表示, 所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路, 即在拓扑排序输出结束后所余下的顶点都有前驱, 则说明了只得到了部分顶点的拓扑有序序列, 图中存在回路。所以选项Ⅲ正确。

6． 设二维数组(即m 行n 列) 按行存储在数组

A[i，j]在一维数组B 中的下标为（ ）。

A.(i﹣1)*n＋j

B.(i﹣1)*n＋j ﹣l

C.i*(j﹣1)

D.j*m＋i ﹣l

第 3 页，共 64 页 中，则二维数组元素

【答案】A

【解析】前i ﹣1的元素个数为(i﹣1)*n，所以二维数组元素A[i，j]在一维数组B 中的下标为(i﹣1)*n＋j 。需要注意数组B 的下标是从0开始，还是从1开始。

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

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

B. 降低进程优先级

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

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

【答案】A

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

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

表 资源分配情况表

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运行是可以的。

表

本题也可以排除法, 时刻可用资源是R1, R2, R3分别为2, 3, 3, 此时刻, P0需要R1, R2, R3

第 4 页，共 64 页