2010年计算机学科专业基础综合试题参考答案一、单项选择题1.9.17.25.33.DBDBC2.10.18.26.34.CDBAC3.11.19.27.35.DAADD4.12.20.28.36.CDDBC5.13.21.29.37.CDACAABDCDBBABB6.14.22.30.38.7.15.23.31.39.8.16.24.32.40.BACBA1.解析：选项A可由in,in,in,in,out,out,in,out,out,in,out,out得到；选项B可由in,in,in,out,out,in,out,out,in,out,in,out得到；选项C可由in,in,out,in,out,out,in,in,out,in,out,out得到；选项D可由in,out,in,in,in,in,in,out,out,out,out,out得到，但题意要求不允许连续三次退栈操作，故D不可能得到。【另解】先进栈的元素后出栈，进栈顺序为a,b,c,d,e,f,故连续出栈时的序列必然是按字母表逆序的，若出栈序列中出现了长度大千等于3的连续逆序子序列，则为不符合要求的出栈序列。2.解析：本题的队列实际上是一个输出受限的双端队列。A操作：a左入（或右入）、b左入、c右入、d右入、e右入。B操作：a左入（或右入）、b左入、c右入、d左入、e右入。D操作：a左入（或右入）、b左入、c左入、d右入、e左入。C操作：a左入（或右入）、b右入、因d未出，此时只能进队，c怎么进都不可能在b和a之间。【另解】初始时队列为空，第1个元素a左入（或右入），而第2个元素b无论是左入还是右入都必与a相邻，而选项D中a与b不相邻，不合题意。3.解析：题中所给二叉树的后序序列为d,b,c,a。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b;结点b无左子树，左链域指向其前驱结点d;结点c无左子树，左链域指向其前驱结点b,无右子树，右链域指向其后继结点a。故选D。4.解析：插入48以后，该二叉树根结点的平衡因子由-1变为-2,在最小不平衡子树根结点的右子树CR)的左子树(L)中插入新结点引起的不平衡属千RL型平衡旋转，需要做两次旋转操作（先右旋后左旋）。今132490调整后，关键字37所在结点的左、右子结点中保存的关键字分别是24、53。5.解析：设树中度为iCi=O,1,2,3,4)的结点数分别为N;,树中结点总数为N,则树中各结点的度之和等于N-1,即N=1+N1+2N2+3N3+4N4=Ni。+N尸岛+N3+N4,根据题设中的数据，即可得到N。=82,即树T的叶结点的个数是82。6.解析：哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为1的结点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左、右子树根结点权值之和，其权值不小千其左、右子树根结点的权值，在与结点P的左、右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q,则结点Q的兄弟结点中权值较小的一个应该与结点P作为左、右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小千下一层任一结点的权值。7.解析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保待连通，首先需要G的任意6个结点构成完全连通子图GI,需n(n-1)/2=6x(6-1)/2=15条边，然后再添一条边将第7个结点与Gl连接起来，共需16条边。8.解析：拓扑排序的过程如下图所示。三二勹输出e妙，输出b©�0---,三：出b输出衫。输出c三出'�输出c输：0©©输出d,得到aebcd输出d,得到abecd输出d,得到abced可以得到3个不同的拓扑序列，分别为abced、abecd、aebcd。9.解析：折半查找法在查找成功时进行的关键字比较次数最多为Llog2刓+1,即判定树的高度；折半查找法在查找不成功时进行的关键字比较次数最多为l1og2n」+1。题中n=16,因此最多比较L1og2t6」+1=5次。也可以画出草图求解。思考：若本题题干改为求最少的比较次数呢？10.解析：快递排序的递归次数与元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若划分后分区不平衡，则递归次数多。但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并不会影响树中的分支数。11.解析：题中所给的三趟排序过程中，每一趟排序是从前往后依次比较，使最大值“沉底”，符合冒泡排序的...
