2012年计算机学科专业基础综合试题参考答案一、单项选择题1.B2.A3.A4.B5.C6.C7.C8.A9.D10.A11.D12.D13.B14.D15.D16.A17.C18.C19.C20.D21.D22.B23.C24.B25.B26.A27.D28.A29.B30.C31.A32.B33.B34.C35.A36.B37.C38.A39.D40.D1.解析：本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是n~l,每调用一次factO,传入该层facto的参数值减l。采用递归式来表示时间复杂度有0(1)n~1T(n)={T(n-1)+1n>1则T(n)=T(n-1)+1=T(n-2)+2=…=T(l)+n-1=O(n),故时间复杂度为O(n)。2.解析：表达式求值是栈的典型应用。中缀表达式不仅依赖千运算符的优先级，而且要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符进行处理，使其包含运算符优先级的信息，从而转换为后缀表达式的形式。转换过程如下表：运算符栈中缀未处理部分后缀生成部分说明#a+b-a*((c+d)/e-t)+g#+b-a*((c+d)/e-f)+ga+b-a*((c+d)le-f)+ga"+"入栈+-a*((c+d)/e-f)+gaba*((c+d)/e-f)+gab+"+"出栈，＂－”入栈*((c+d)/e-f)+gab+a一＊((c+d)/e-f)+gab+a"*"入栈一＊（（c+d)/e-f)+gab+a两个"("依次入栈-•((+d)/e-f)+gab+ac一＊（（＋d)/e-f)+gab+ac"+"入栈一＊（（＋)/e-f)+gab+acd一＊（/e-f)+gab+acd+"+"和"("依次出栈一＊（／e-f)+gab+acd+"I"入栈运算符栈中缀未处理部分后缀生成部分说明-*(I-t)+gab+acd+e－＊（一f)+gab+acd+e/"I"出栈，“－”入栈-*(一)+gab+acd+e/f-*+gab+acd+e/f-"-"和"("依次出栈+gab+acd+e/f-*"*"出栈＃+gab+acd+e/f-*-"-"出栈＋gab+acd+e/f-*-"+"入栈＃ab+acd+e/f-*-g"+"出栈（续表）可知，栈中的操作符的最大个数为5。3.解析：前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为XY与后序序列为YX时，则X为Y的祖先。考虑前序序列�'e,b,d,C、后序序列b,c,d,e,且，可知a为根结点，e为a的孩子结点。此外，a的孩子结点的前序序列�.b,d,c、后序序列b,c,d,�.可知e是bed的祖先，故根结点的孩子结点只有e。故选A。【排除法】显然a为根结点，且确定e为a的孩子结点，排除D。各种遍历算法中左右子树的遍历次序是固定的，若b也为a的孩子结点，则在前序序列和后序序列中e、b的相对次序应是不变的，故排除B,同理排除C。【特殊法】前序序列和后序序列对应着多棵不同的二叉树树形，我们只需画出满足该条件的任一棵二叉树即可，任意一棵二叉树必定满足正确选项的要求。a(a)(b)(c)(d)显然选A,最终得到的二叉树满足题设中前序序列和后序序列的要求。4.解析：所有非叶结点的平衡因子均为1,即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为N、左右子树的高度分别为N-1和N-2、所有非叶结点的平衡因子均为1的平衡二叉树，总结点数的公式为：CN=C凡I+C'.凡2+1,C1=1,C2=2,C3=2+1+1=4,可推出C6=20。勹／三三【画图法】先画出m和Tz;然后新建一个根结点，连接T公飞构成T3;新建一个根结点，连接T3、飞构成T4;以此类推，直到画出T6,可知飞的结点数为20。【排除法】对千选项A,高度为6、结点数为10的树怎么也无法达到平衡。对于选项c,结点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理D错误。只可能选B。5.解析：广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n),在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为O(e),算法总的时间复杂度为O(n+e)。6.解析：对角线以下元素均为零，表明只有顶点l到顶点j(i
