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

一、单项选择题

1． 算法的计算量的大小称为计算的（ ）。

A. 效率

B. 复杂性

C. 现实性

D. 难度

【答案】B

【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。

2． 在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。

A. 编辑

B. 编译

C. 链接

D. 装载

【答案】B

【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成目标程序时, 会形成逻辑地址; 链接是由链接程序将编译后形成的一组目标模块, 以及所需库函数链接, 形成完整的装入模块; 装入是由装入程序将装入模块装入内存。

3． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。 A. B. | C. D.

【答案】C

【解析】因为该序列中的结点己经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为O(N)。对于采用归并法，它是一种稳定的排序方法，它

的时间复杂度为。对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为。

4． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:

①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。

然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:

A. 左子树为空, 右子树为cd ;

b. 左子树为c , 右子树为d ;

c. 左子树为cd , 右子树为空。

按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。

5． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A.0(n)

B.0(n+e) C. D.

【答案】B

【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)

6． 下列存储器中, 在工作期间需要周期性刷新的是（ ）。

A.SRAM

B.SDRAM

C.ROM

D.FLASH

【答案】B

【解析】动态随机存储器(DRAM)是利用存储元电路中栅极电容上的电荷来存储信息的, 电容

上的电荷一般只能维持

须刷新。

, 因此即使电源不掉电, 信息也会自动消失。为此, 每隔一定时间必

7． 为提高散列(Hash)表的查找效率, 可以采用的正确措施是（ ）。

Ⅰ. 增大装填(载) 因子

Ⅱ. 设计冲突(碰撞) 少的散列函数

Ⅲ. 处理冲突(碰撞) 时避免产生聚集(堆积) 现象

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ

D. 仅Ⅱ、Ⅲ

【答案】D

【解析】散列表的查找效率(比较次数) 取决于:散列函数、处理冲突的方法和散列表的装填因子α。α标志着散列表的装满程度, 通常情况下, α越小, 发生冲突的可能性越小; 反之, α越大, 表示已填入的记录越多, 再填入记录时, 发生冲突的可能性越大。因此选项Ⅰ错误, 越是增大装填因子, 发生冲突的可能性就越大, 查找效率也越低。选项Ⅱ正确。选项Ⅲ正确。采用合适的处理冲突的方法避免产生聚集现象, 也将提高查找效率。例如, 用拉链法解决冲突时不存在聚集现象, 用线性探测法解决冲突时易引起聚集现象。

8． 已知程序如下:

{

}

voidmain （ ）

{

>

}

程序运行时使用栈来保存调用过程的信息, 自栈底到桟顶保存的信息依次对应的是（ ）。

A. B. C. D.

【答案】A

【解析】函数S(int n)是一个递归函数:

①当实际参数小于等于零时则返回0, 并终止递归;

②当实际参数大于零时则递归调用S(n-1), 并将S(n-1)的结果加上n 作为返回值。程序从main （ ）函数开始, 首先调用main （ ）函数; 在main （ ）函数中调用S(1)函数时, 将main （ ）函数的上下文保存到栈中, 并进入函数S(1); 由于函数S(1)的实际参数大于零, 需要调用S(0), 故将S(1)函数的上下文保存到栈中, 进入S(0); 在S(0)中, 实际参数小于等于零, 递归终止。