2012 年全国硕士研究生入学统一考试—计算机专业基础综合试题2012 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题（科目代码 408 ）12012 年全国硕士研究生入学统一考试—计算机专业基础综合试题一、单项选择题：第1～ 40 小题，每小题2 分，共80 分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1．求整数n(n ≥ 0)阶乘的算法如下，其时间复杂度是int fact(int n) { if (n<=1)return 1; return n*fact(n-1); } A. O(log 2n) B. O(n) C. (nlog 2n) D. O(n 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. 存在，且唯一C. 存在，可能不唯一B. 存在，且不唯一D. 无法确定是否存在7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra ）算法求源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是22012 年全国硕士研究生入学统一考试—计算机专业基础综合试题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 得到一棵...
