2012年计算机考研408真题及答案解析

题目一：求整数 n（n ≥ 0）阶乘的算法，其时间复杂度是（ ）。

A. O(log n)
B. O(n)
C. O(n log n)
D. O(n)

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

题目二：已知操作符包括 '+'、''、'*'、'/'、'(' 和 ')'。将中缀表达式 a + b ((c + d) / e * f) + g 转换为等价的后缀表达式 ab+cd+e/f*g+ 的过程中，使用栈来存放尚未确定运算次序的操作符。若栈初始为空，则在整个转换过程中，栈中同时保存的操作符的最大个数是（ ）。

A. 5
B. 7
C. 8
D. 11

题目三：若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根节点的孩子节点是（ ）。

A. 只有 e
B. 有 e、b
C. 有 e、c
D. 无法确定

题目四：若某平衡二叉树高度为6，且所有非叶结点的平衡因子均为1，则该树的结点总数为（ ）。

A. 10
B. 20
C. 32
D. 33

题目五：对于一个具有 n 个结点、e 条边并采用邻接表存储的有向图，执行广度优先遍历的时间复杂度为（ ）。

A. O(n)
B. O(e)
C. O(n + e)
D. O(n × e)

题目六：若用邻接矩阵表示一个有向图，且矩阵中主对角线以下的所有元素均为零，则关于该图的拓扑序列，可以得出的结论是（ ）。

A. 存在，且唯一
B. 存在，且不唯一
C. 存在，可能不唯一
D. 无法确定是否存在

题目七：下列关于最小生成树的说法中，正确的是（ ）。
Ⅰ．最小生成树的总代价是唯一的
Ⅱ．所有权值最小的边一定会出现在所有最小生成树中
Ⅲ．使用普里姆（Prim）算法从不同顶点开始，所得到的最小生成树一定相同
Ⅳ．使用普里姆算法与克鲁斯卡尔（Kruskal）算法所得的最小生成树总是不同的

A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ

题目八：在内部排序过程中，对尚未确定最终位置的所有元素进行一次处理称为一趟排序。以下排序方法中，每一趟排序结束后至少能确定一个元素最终位置的是（ ）。
Ⅰ．简单选择排序
Ⅱ．希尔排序
Ⅲ．快速排序
Ⅳ．堆排序
Ⅴ．二路归并排序

A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅲ、Ⅴ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ

题目九：对同一待排序序列分别应用折半插入排序和直接插入排序，二者之间可能存在差异的是（ ）。

A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数

题目十：假设基准程序 A 在某计算机上运行时间为 100 秒，其中 CPU 时间为 90 秒，其余为 I/O 时间。如果 CPU 速度提升 50%，而 I/O 速度保持不变，则程序 A 新的运行时间为（ ）。

A. 55s
B. 60s
C. 65s
D. 70s

题目十一：设编译器规定 int 类型为 32 位，short 类型为 16 位，执行以下 C 语言语句：
unsigned short x = 65530;
unsigned int y = x;
则 y 的机器数表示为（ ）。

A. 0000 7FFAH
B. 0000 FFFAH
C. FFFF 7FFAH
D. FFFF FFFAH

题目十二：float 类型（即 IEEE754 单精度浮点数格式）所能表示的最大正整数是（ ）。

A. 2 2
B. 2 2
C. 2 2
D. 2 2