2009年计算机学科专业基础综合试题参考答案一、单项选择题1.B9.A17.A25.C33.B1.解析：缓冲区的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数据则要排队到最后才能打印，显然不符题意，故选B。2.解析：由千队列的特点是先进先出，即栈S的出栈顺序就是队Q的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。2.10.18.26.34.3.11.19.27.35.BDBBADCDCCCBAAB4.12.20.28.36.5.13.21.29.37.6.14.22.30.38.7.15.23.31.39.ADDBCBCAADCDDAD8.16.24.32.40.DCDAA序号说明栈内栈外序号说明栈内栈外1a入栈A8e入栈aebdc2b入栈Ab9f入栈aefbdc3b出栈Ab10f出栈aebdcf4c入栈Acb11e出栈abdcfe5d入栈Acdb12a出栈bdcfea6d出栈Acbd13g入栈gbdcfea7c出栈Abdc14g出栈bdcfeag栈内的最大深度为3,故栈S的容量至少是3。【另解】元素的出栈顺序是b,d,c,f,e,a,g,可推出进栈出栈顺序为Push(S,a),Push(S,b),Pop(S,b),Push(S,c),Push(S,d),Pop(S,d),Pop(S,c),Push(S,e),Push(S,f),Pop(S,f),Pop(S,e),Pop(S,a),Push(S,g),Pop(S,g)。假设初始所需容量为o,每做一次Push进行一次"+1"操作，每做一次Pop进行一次"-1"操作，记录容量的最大值为3,所以选C。3.解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是RNL。本题考查的遍历方法并不是二叉树的3种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。4.解析：根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。而其余3个选项均可以找到不符合该条件的结点。在做题过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。5.解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7,显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8x2=16个叶结点，故完全二叉树的结点个数最多为(27-1)-16=111个结点。6.解析：森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。情形I:若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。情形II:结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k,则转换后，结点v就变为结点K的右孩子，而结点k则是结点u的右孩子，符合要求。喜｀｀。嘉｀｀II情形III:若结点u的父结点与v的父结点是兄弟关系，则转换后，结点u和v分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。分图III【逆向法】由题意可知u是v的父结点的父结点，如下图所示有4种情况：����根据树与二叉树的转换规则，将这4种情况转换成树种结点的关系。(1)在原来的树中u是v的父结点的父结点；(2)在树中u是v的父结点；(3)在树中u是v的父结点的兄弟；(4)在树中u与v是兄弟关系。由此可知I和II正确。7.解析：每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I正确。n个顶点、n-l条边可以构成无向连通图，比如树，II错误。顶点数为N(N�l)的无向完全图中不存在度为1的顶点，III错误。8.解析：选项A、B和C都是B-树的特点，而选项D则是B+树的特点。注意区别B-树和B+树各自的特点。9.解析：根据关键字序列得到的小顶堆的二叉树形式如下图所示。19151515222222(I)插入关键字3时，先将其放在小顶堆的末端，如图(2)所示。再将该关键字向上进行调整，得到的结果如图(3)所示。所以，调整后的小顶堆序列为3,5,12,8,28,20,15,22,19。10.解析：解答本题需要对各种排序算法的特点极为清楚。对于冒泡排序和选择排序，每一趟都能确定一个元素的最终位置，而题目中，前2个元素和后2个元素均不是最小或最大的2个元素并按序排列。选项D中的2路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时...
