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

一、单项选择题

1． 下面关于哈希(Hash，杂凑) 查找的说法正确的是（ ）。

A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B. 除留余数法是所有哈希函数中最好的

C. 不存在特别好与坏的哈希函数，要视情况而定

D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可

【答案】C

【解析】若数据结构中存在关键字和K 值相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，称这个对应关系f 为哈希(Hash)函数，哈希函数的选择要视具体情况而定。

2． 下列选项中, 满足短任务优先且不会发生饥饿现象的调度算法是（ ）。

A. 先来先服务

B. 高响应比优先

C. 时间片轮转

D. 非抢占式短任务优先

【答案】B

【解析】分析该题目可以看到, 本题所提到的问题是涉及短任务调度也就是属于作业调度, 因此首先排除时间片轮转算法; 因为作业调度算法中没有时间片轮转的算法。其次, 因为问题提到短任务, 则先来先服务的算法也可以排除了, 它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个？我们可以通过分析得到, 非抢占式短任务优先算法不能解决饥饿问题, 因为当一个系统短任务源源不断到达是, 长任务必然会得不到调度, 产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法, 并以高响应比值优先调度。这样, 无论短任务或长任务, 均可以得到调度, 而且, 较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有高响应比优先算法。

3． 链表不具有的特点是（ ）。

A. 插入、删除不需要移动元素

B. 可随机访问任一元素

C. 不必事先估计存储空间

D. 所需空间与线性长度成正比

【答案】B

【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。

4． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.

B.n/2 C.

D.n

【答案】C

【解析】最快查找一次成功，最慢查找n

次成功。平均查找次数为

。

5． 就平均性能而言，目前最好的内排序方法是（ ）排序法。

A. 起泡

B. 希尔插入

C. 交换

D. 快速

【答案】D

【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为

间复杂度也是

注意仅仅表示的是一个量级，比如和的量级都为，虽然堆排序的时。之所以说，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要那么快排最好，是在综合考虑的情况下。

6． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）

A.G 的邻接多重表需要n(n－1) 个边结点和n 个顶点结点

B.G 的连通分量个数最少

C.G 为连通图

D.G 所有顶点的度的总和为n(n—1)

【答案】A

A 项中G 的邻接多重表中需要【解析】

n 个结点的度的总和为n(n－1) 。

个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n －1，则

7．

将一个的三对角矩阵，

按行优先存入一维数组中，A 中元素A 6665(即该元素下标i ＝66，j ＝65) ，在B 数组中的位置K 为（ ）。

A.198

B.195

C.197

【答案】B

【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下:k ＝2i ＋j ﹣2。

8． 下列选项中, 在总线的数据线上传输的信息包括（ ）。

Ⅰ.

Ⅱ. 接口中的命令字 接口中的状态字

Ⅲ. 中断类型号

A. 仅Ⅰ、Ⅱ

B. 仅Ⅰ、Ⅲ

C. 仅Ⅱ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】D 。

【解析】在总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据, 而中断类型号也是通过数据线传输的。

9． 下列选项中, 不会引起指令流水线阻塞的是（ ）。

A. 数据旁路(转发)

B. 数据相关

C. 条件转移

D. 资源冲突

【答案】A

【解析】由于采用流水线方式, 相邻或相近的两条指令可能会因为存在某种关联, 后一条指令不能按照原指定的时钟周期运行, 从而使流水线断流。有三种相关可能引起指令流水线阻塞:

①结构相关, 又称资源相关;

②数据相关;

③控制相关, 又称指令相关, 主要由转移指令引起。

10．若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）

A.1和5

B.2和4

C.4和2