2012年考研统考408计算机学科专业基础综合真题及答案..pdf

2012 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 （科目代码 408） 一、单项选择题：第 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．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是