2012考研计算机真题及答案解析(详细).pdfVIP

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 ．12 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．下列关于最小生成树的说法中，正确的是（ ）。 第 1 页 共 15 页 Ⅰ．最小生成树的代价唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ．使用普里姆（Prim ）算法从不同顶点开始得到的最小生成树一定相同 Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同 A ．仅Ⅰ B ．仅Ⅱ C ．仅Ⅰ、Ⅲ D ．仅Ⅱ、Ⅳ 9 ．设有一棵3 阶B 树，如下图所示。删除关键字78 得到一棵新B 树，其最右叶结点所含 的关键字是（ ）。 A ．60 B ．60，62 C ．62，65 D ．65 10．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方 法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。 Ⅰ．简单选择排序 Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排序 Ⅴ．二路归并排序 A ．仅Ⅰ、Ⅲ、Ⅳ B