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

一、单项选择题

1． —组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

A.(38，40，46，56，79，84)

B.(40，38，46，79，56，84)

C.(40，38，46，56，79，84)

D.(40，38，46，84，56，79)

【答案】C

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

第一次比较:46比84小，不交换；

第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;

第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;

第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;

第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;

一次划分结束。

2． 下列关于银行家算法的叙述中, 正确的是（ ）

A. 银行家算法可以预防死锁

B. 当系统处于安全状态时, 系统中一定无死锁进程

C. 当系统处于不安全状态时, 系统中一定会出现死锁进程

D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

【答案】B

【解析】银行家算法是避免死锁的方法。利用银行家算法, 系统处于安全状态时没有死锁进程, 故答案选B 。

3． 在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。

A.G 中有弧

C.G 中没有弧 B.G 中有一条从到的路径

D.G 中有一条从到的路径

【答案】D

【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。

4． 以下说法错误的是（ ）。

(1)算法原地工作的含义是指不需要任何额外的辅助空间

(2)在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n ) 的算法

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

(4)同一个算法，实现语言的级别越高，执行效率就越低

A.(1)

B.(1), (2)

C.(1), (4)

D.(3)

【答案】A

【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。

5． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根, 总线时钟频率为66MHZ , 每个时钟同期传送两次数据。(上升沿和下降沿各传送一次数据) 该总线的最大数据传输率是(总线带宽) :（ ）

A.132MB/S

B.264MB/S

C.528MB/S

D.1056MB/S

【答案】C

【解析】总线带宽=总线工作频率X(总线宽度/8), 由于地址线与数据线复用, 所以在两次数据

, 所以选C 传输过程中总线上数据一共传输了8次, 那么总线带宽为

6． 主机甲和主机乙间已建立一个TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。

A.500

B.700

C.800

D.1000

【答案】D

【解析】TCP 使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 那么确认序列号为200＋300＋500＝1000。

7． 下述文件中适合于磁带存储的是（ ）。

A. 顺序文件

B. 索引文件

C. 哈希文件

D. 多关键字文件

【答案】A

【解析】磁带存储是一种顺序存储，顺序文件(sequential file)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。

8． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。

A. 执行P(wait)操作

B. 申请内存失败

C. 启动设备

D. 被高优先级进程抢占

【答案】D

【解析】D 项, 被高优先级进程抢占, 进程会由执行态变为就绪态。ABC 三项, 程序由于缺少资源而由执行态转为阻塞态。

9． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。

A.4

B.5

C.6

D.7

【答案】B

【解析】

折半查找法在查找不成功时和给定值进行比较的关键字个数最多为, 在本题中, n=16, 故比较次数最多为5。

10．若对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 阶对称矩阵