2012年考研计算机考试试题（选择题前6道）

　　　　　　　　　　　　　　　　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 . (a log2n)
　　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. 存在，且唯一
　　B. 存在，且不唯一
　　C. 存在，可能不唯一
　　D. 无法确定是否存在