2012计算机考研真题及答案.doc

2012 年全国硕士研究生入学统一考试—计算机专业基础综合试题 2012 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 （科目代码 408） 1 2012 年全国硕士研究生入学统一考试—计算机专业基础综合试题 一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项最符合试题 要求。 1．求整数 n(n≥0)阶乘的算法如下，其时间复杂度是 int fact(int n) { if (n=1)return 1; return n*fact(n-1); }  A. O(log2n)  B. O(n)  C. (nlog2n)  D. O(n2)  2．已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。将中缀表达式 a+b-a*((c d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最 大个数是  A. 5  B. 7  C. 8  D. 11  3.若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点  A. 只有 e  B. 有 e、b  C. 有 e、c  D. 无法确定  4．若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为  A. 10  B. 20  C. 32  D. 33  5．对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是  A. O(n)  B. O(e)  C. O(n+e)  D. O(n*e)  6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是  A. 存在，且唯一 C. 存在，可能不唯一  B. 存在，且不唯一 D. 无法确定是否存在  7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点 a 到其他各顶点的最短路径，则得到的第一条最 短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是 2 2012 年全国硕士研究生入学统一考试—计算机专业基础综合试题 A.d,e,f B.e,d,f C. f,d,e D.f,e,d  8．下列关于最小生成树的说法中，正确的是 I. 最小生成树树的代价唯一 II. 权值最小的边一定会出现在所有的最小生成树中 III. 用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同 IV. 普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同  A. 仅 I  B. 仅 II  C. 仅 I、III  D. 仅 II、IV  9．设有一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是  A. 60  B. 60, 62  C. 62, 65  D. 65  10．在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排 序结束都至少能够确定一个元素最终位置的方法是 I. 简单选择排序 II. 希尔排序 III. 快速排序 IV 堆排序 V. 二路归并排序  A. 仅 I、III、IV C. 仅 II、III、IV  B. 仅 I、III、V D. 仅 III、IV、V  11．对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是  A. 排序的总趟数 C. 使用辅助空间的数量  B. 元素的移动次数 D. 元素之间的比较次数  12．假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU 速度 提高 50%，I/O 速度不变，则运行基准程序 A 所耗费的时间是  A. 55 秒  B. 60 秒  C. 65 秒  D. 70 秒  13．假定编译器规定 int 和 short 类型长度占 32 位和 16 位，执行下列 C 语言语句 unsigned short x = 65530; unsigned int y = x; 得到 y 的机器数为 3 2012 年全国硕士研究生入学统一考试—计算机专业基础综合试题 A. 0000 7FFA B. 0000 FFFA C. FFFF 7FFA D. FFFF FFFA  14．float 类型（即 IEEE754 单精度浮点数格式）能表示的最大