2012考研408真题答案(1).pdf

2012年计算机学科专业基础综合试题参考答案一、单项选择题1.B2.A3.A4.B5.C6.C7.C8.A9.D10.A11.D12.D13.B14.D15.D16.A17.C18.C19.C20.D.21.D22.B23.C24.B25.B26.A27.D28.A29.B30.C31.A32.B33.B34.C35.A36.B37.C38.A39.D40.D1.解析：本算法是一个递归运算，即算法中出现了调用自身的情形。递归的边界条件是1，每调用次fact(),传入该层fact0的参数值减1。采用递归式来表示时间复杂度有0)n1T(n)=T(n-1)+1n1则T()-T(n-1)+1=Tn-2)+2=.=T(1)+n-1=0(n),故时间复杂度为0(n)。2.解析：表达式求值是栈的典型应用。中缀表达式不仅依赖于运算符的优先级，还要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符进行处理，使其包含运算符优先级的信息，从而转换为后缀表达式的形式。转换过程如下表：运算符栈中缀未处理部分后缀生成部分说明a+b-a*(c+d)/c-f)+g+b-a(c+d)/e-f)+gab-a*(c+d)/e-f)+ga“+”入栈-a(c+d)/e-f)+gab-a(c+d)/e-f)+gab+“+”出栈，“”入栈*(c+d)/e-f)+gab+a(c+d)/e-f)+gabta“*”入栈*(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+“”入栈*利-0+gab+acd+e105续表运算符栈中缀未处理部分后缀生成部分说明*(f)+gab+acd+c/“”出栈，“.”入栈*(H+gab+acd+e/fgab+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的祖先。考虑前序序列a,，b,d,c、后序序列b,c,d,e,a,可知a为根结点，e为a的孩子结点；此外，a的孩子结点的前序序列e,b,d,c、后序序列b,c,d,e,可知e是bcd的祖先，故根结点的孩子结点只有e。故选A。【排除法】显然a为根结点，且确定e为a的孩子结点，排除D。各种遍历算法中左右子树的遍历次序是固定的，若b也为a的孩子结点，则在前序序列和后序序列中e、b的相对次序应是不变的，故排除B,同理排除C。【特殊法】前序序列和后序序列对应着多棵不同的二叉树树形，我们只需画出满足该条件的任一棵二叉树即可，任意一棵二叉树必定满足正确选项的要求。e,b,d,cb,d,cd,c(a)(b)(c)(d)显然选A,最终得到的二叉树满足题设中前序序列和后序序列的要求。4.解析：所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为N、左右子树的高度分别为N-1和N-2、所有非叶结点的平衡因子均为1的平衡二叉树，总结点数的公式为：CNCw-1+CN.2+1,C1=1,C2=2,C3=2+1+1=4,可推出C620【画图法】先画出T1和T2:然后新建一个根结点，连接T2、T1构成T3:新建一个根结点，连接T3、T2构成T4:依此类推，直到画出T6,可知T6的结点数为20。106【排除法】对于选项A,高度为6、结点数为10的树怎么也无法达到平衡。对于选项C,结点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理D错误。只可能选B,5.解析：广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表：边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O),在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为O(e),算法总的时间复杂度为O(n+e)。6.解析：对角线以下元素均为零，表明只有顶点i到顶点j()可能有边，而顶点j到顶点i一定没有边，即有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，试举一例：设011有向图的邻接矩阵000则存在两个拓扑序列，因此该图存在可能不唯一的拓扑序列。000结论：对于任一有向图，如果它的邻接矩阵中对角线以下（或以上）的元素均为零，则存在拓扑序列（可能不唯一）。反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。7.解析：从a到各顶点的最短路径的求解过程：顶点第1趟第2趟第3趟第4趟对5趟b(a,b)2c(a,c)5(a,b,c)3d(a,b,d)5(a,b,d)5(a,b,d)50o00(a,b,c,04f(a.b.c,e)7(a,b,c,e)7(a,b,d,e)6集合Sa,bfab.cfa.b.c.ffa.b.c.fdfa.b.c.fd.e后续目标顶点依次为，d,e,【排除法】对于A,若下一个顶点为d,路径a,b,d的长度5，而a,b,c,f的长度仅为4，显然错误。同理可以排除B。将f加入集合S后，采用上述的方法也可以排除D。8.解析：对于I,最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，I正确。对于，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，错误。对于，设N个结点构成环，N-1条边权值相等，则从不同的顶点开始普里姆算法会得到N-1中不同的最小生成树，错误。对于V,当最小生成树唯一时(各边的权值不同)，普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，V错误。9.解析：对于上图所示的3阶B-树，被删关键字78所在结点在删除前的关键字个数=13/2-1，且其左兄弟结点的关键字个数=23/21，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键107