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

一、单项选择题

1． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。

A. 必定快 B. 不一定

C. 在大部分情况下要快 D. 取决于表递增还是递减 【答案】C

【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。

2． 对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。

A. 每次分区后，先处理较短的部分 B. 每次分区后，先处理较长的部分 C. 与算法每次分区后的处理顺序无关 D. 以上三者都不对 【答案】A

【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为n+1。整个f 的最大深度为递归深度。

3． 求整数阶乘的算法如下, 其时间复杂度是（ ）。

A. B.0(n) C.

2

D.O(n)

【答案】B 。

【解析】设fact(n)的运行时间函数是T(n)。

该函数中语句①的运行时间是0(1), 语句②的运行时间是算的时间。

因此, 当则,

时

,

;

。

即fact(n)的时间复杂度为O(n)。

当11>1时,

, 其中O(1)为乘法运

通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。

4． 在体系结构中, 直接为ICMP 提供服务的协议是（ ）。

A.PPP B.IP C.UDP D.TCP

【答案】B 。

【解析】首先明确ICMP 是网络层的协议, 由于服务必须是下一层向上一层提供服务的, 因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层, 在网络层上面, 所以显然错误, 而PPP 协议是广域网数据链路层协议, 直接为网络层, 也就是IP 层提供服务, ICMP 协议是封装在网络层, 因此PPP 不能直接为ICMP 提供服务, ICMP 报文直接封装在IP 分组中, 故答案是B 。

5． 无向图G=(V，E) ，其中:

，

对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 A.a , b , e , c , d , f B.a , c , f , e , b , d C.a , e , b , c , f , d D.a , e , d , f , c , b 【答案】D

【解析】图的深度优先遍历过程是:从图中某个初始顸点v 出发，首先访问初始顶点v ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。

根据关系。依据

上面的原则遍历，得出遍历顺序a ，e ，d ，f ，c ，b 。

6． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2字节，逻辑地址结构为:

逻辑地址空间大小为（ ）.

A.64 B.128 C.256 D.512

【答案】B

【解析】地址空间分为逻辑地址空间和物理地址空间. 页的大小为采用二级页表，

一页可存放

可知各顶点之间的邻接

字节，页表项大小为

页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是

字节，页表项大小为2B ，

字节，

故最少需要

个页表项，本题中逻辑地址空间大小为

个页面来保存页表项，故本题答案为B.