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

一、单项选择题

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

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

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

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

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

A.(1)

B.(1), (2)

C.(1), (4)

D.(3)

【答案】A

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

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

A. 顺序文件

B. 索引文件

C. 哈希文件

D. 多关键字文件

【答案】A

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

3． 在OSI 参考模型中, 直接为会话层提供服务的是（ ）

A. 应用层

B. 表示层

C. 传输层

D. 网络层

【答案】C

【解析】OSI 参考模型中, 下层直接为上层提供服务, 而会话层的下层为传输层。

4． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps ，电缆中的信号传播速度是200000km/s.若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）.

A. 增加160m

B. 增加80m

C. 减少160m

D. 减少80m

【答案】D

【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度＝碰撞窗口大小×报文发送速率，本题最小数据帧长度

89减少800b , 那么碰撞的窗口也要减少，因此距离也要减少，从而(800×2×l0)/(l×l0) ＝160m ，由于

时间延时存在两倍的关系，因此减少的距离为80m 。

5． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A.107

B.108

C.214

D.215

【答案】B

【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有n0＝n2＋+l，所以215＝n0＋n2＝2*n2＋l ，n2＝107，n0＝108。也就是说若对其进行哈夫曼编码，共能得到108个码字。

6． 已知小根堆为8, 15, 10, 21, 34, 16, 12, 删除关键字8之后需重建堆, 在此过程中, 关键字之间的比较数是（ ）。

A.1

B.2

C.3

D.4

【答案】C

【解析】堆排序中, 依次输出堆顶的最小值, 然后重新调整堆, 如此反复执行, 便得到一个有序序列。本题中, 删除堆顶元素8后将最后一个元素12置于堆顶, 然后调整堆:首先与15比较, 12小于15, 所以不用交换; 然后与10比较, 因为10小于12, 所以交换10和12的位置; 调整后12再与16比较, 12小于16, 调整堆过程结束。因此12共与15、10、16进行了三次比较。

7． 已知有向图G=(V，E) , 其中

,

G 的拓扑序列是（ ）。 A.

B.

C. D.

【答案】A

拓扑序列的条件:若

在顶

点 能被称为必须排【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列是图中的边(即从顶点。 到有一条路径) ，则在序列中顶点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列

是

8． 某计算机的控制器采用微程序控制方式, 微指令中的操作控制字段采用字段直接编码法, 共有33个微命令, 构成5个互斥类, 分别包含7、3、12、5和6个微命令, 则操作控制字段至少有 （ ）。

A.5位

B.6位

C.15位

D.33位

【答案】C 。

33个微命令分成5个互斥类(即5个字段) , 根据每个类中微命令的多少可以分别确定【解析】

字段的长度为3、2、4、3、3位, 又因为采用直接编码方式, 所以它们之和

作控制字段的位数。

9． 下列选项中, 不能构成折半查找中关键字比较序列的是（ ）。

A.500, 200, 450, 180

B.500, 450, 200, 180

C.180, 500, 200, 450

D.180, 200, 500, 450

【答案】A

【解析】折半查找的过程是:先确定待查找记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足:对每一个关键字, 其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误, 第三次比较的关键字为450, 说明待查关键字位于200〜450间, 所以第四次比较时不会遇到关键字180。

10．下列关于无向连通图特性的叙述中，正确的是（ ）.

(1)所有的顶点的度之和为偶数

(2)边数大于顶点个数减1

(3)至少有一个顶点的度为1

A. 只有(1)

也就是操