2012年计算机统考真题及答案解析(套题版).pdf

2012 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个 选项最符合试题要求。 1．求整数n(n≥0) 阶乘的算法如下，其时间复杂度是 。 int fact(int n){ if (n=1) return 1; return n*fact(n-1); } 2 A. O(log n) B. O(n) C. O(nlog n) D. O(n ) 2 2 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 ．存在，且唯一 B ．存在，且不唯一 C ．存在，可能不唯一 D ．无法确定是否存在 7 ．对如下有向带权图，若采用迪杰斯特拉（Dijkstra ）算法求从源点 a 到其他各顶点的最短路径， 则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径 的目标顶点依次是 。 A ．d,e,f B ．e,d,f C ．f,d,e D ．f,e,d 8 ．下列关于最小生成树的叙述中，正确的是 。 Ⅰ．最小生成树的代价唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 王道论坛（ ）原创并友情分享！~ Ⅲ．使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同 Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同 A ．仅 Ⅰ B ．仅Ⅱ C ．仅 Ⅰ、Ⅲ D ．仅Ⅱ、Ⅳ 9 ．已知一棵3 阶 B-树，如下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字 是 。 A ．60 B ．60, 62 C ．62, 65 D ．65 10．在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方 法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是