2011年计算机学科专业基础综合试题参考答案一、单项选择题1.9.17.25.33.CAACBADBBCDBCCCCADADCDCDDBBCDBBADBBADCDA2.10.18.26.34.3.11.19.27.35.4.12.20.28.36.5.13.21.29.37.6.14.22.30.38.7.15.23.31.39.8.16.24.32.40.l.解析：在程序中，执行频率最高的语句为"x=2*x"。设该语句共执行了T(n)次，则2兀n)+l~n/2,故T(n)=log2(n/2)-1=log2n-2,得T(n)=O(log2n)。2.解析：d为第1个出栈元素，则d之前的元素必定是进栈后在栈中停留。因而出栈顺序必为d_c_b_a_,e的顺序不定，在任一"_"上都有可能，一共有4种可能。【另解】d首先出栈，则abc停留在栈中，此时栈的状态如右图所示。此时可以有如下4种操作：(De进栈后出栈，则出栈序列为decba;®c出栈，e进栈后出栈，出栈序列为dceba;@cb出栈，e进栈后出栈，出栈序列为dcbea;©cba出栈，e进栈后出栈，出栈序列为dcbae。3.解析：根据题意，第一个元素进入队列后存储在A[O]处，此时front和rear值都为0。入队时由于要执行(rear+1)%n操作，所以如果入队后指针指向o,则rear初值为n-1,而由千第一个元素在A[O]中，插入操作只改变rear指针，所以front为0不变。注意：©循环队列是指顺序存储的队列，而不是指逻辑上的循环，如循环单链表表示的队列不能称为循环队列。@front和rear的初值并不是固定的。【排除法】如果front和rear的初值相等，则无法判断队列空和队列满，排除A、D。第1个进入队列的元素存储在A[O]处，进队操作不会改变front的值，由题意可知队列非空时front指向队头元素，故front初值为o,只能选B。4.解析：根据完全二叉树的性质，最后一个分支结点的序号为Ln12」=L16s12」=384,故叶子结点的个数为768-384=384。【另解1】由二叉树的性质n=n社n1+n2和n。=n2+1可知，n=2n。-I+ni,2n。-I+n1=768,显然n1=1,2n。=768,则n。=384。【另解2】完全二叉树的叶子结点只可能出现在最下两层，由题可计算完全二叉树的高度为10。第10层的叶子结点数为768-(29-1)=257;第10层的叶子结点在第9层共有「257127=129个父结点，第9层的叶子结点数为(29-1)-129=127,则叶子结点的总数为257+127=384。5.解析：前序序列为NLR,后序序列为LRN,由千前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为4。1为根结点，由千根结点只能有左孩子（或右e-d飞「孩子），因此，在中序序列中，l或在序列首或在序列尾，ABCD皆满足要求。仅考虑以1的孩子结点2为根结点的子树，它也只能有左孩子（或右孩子），因此，在中序序列中，2或在序列首或序列尾，ABD皆满足要求。【另解】画出各选项与题干信息所对应的二叉树如下，故ABD均满足。6.解析：树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数＝分支结点数+1=2011-116+1=1896。通常本题应采用特殊法解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子，故无右孩子的结点个数=2011-115=1896。7.解析：在二叉排序树中，左子树结点值小于根结点，右子树结点值大于根结点。在选项A中，当查找到91后再向24查找，说明这一条路径（左子树）之后查找的数都要比91小，而后面却查找到了94C解题过程中，建议配合画图），因此错误。【画图法】各选项对应的查找过如下图，BCD对应的查找树都是二叉排序树，A对应的查找树不是二叉排序树，因为在91为根的左子树中出现了比91大点的结点94。点点结结叶间个6l中l共个5二二(a)选项A的查找过程(b)选项B的查找过程(c)选项C的查找过程(d)选项D的查找过程8.解析：第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，故I错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为O(n2),必将浪费大量的空间，而邻接表的空间复杂度为O(n+e),应该选用邻接表，故II错误。存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故III正确。9.解析：Hash表的查找效率取决于散列函数、处理冲突的方法和装填因子...
