2010年研究生入学统一考试计算机学科专业基础综合试卷

2010年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题(1-40小题,每小题2分,共80分,下列每小题给出的四个选项中,只有一项符合题目要求,把所选项前的字母填在题后的括号内.)(1)若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是(A)d,c,e,b,f,a(B)c,b,d,a,e,f(C)b,c,a,e,f,d(D)a,f,e,d,c,b(2)某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是(A)b,a,c,d,e(B)d,b,a,c,e(C)d,b,c,a,e(D)e,c,b,a,d(3)下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是(A)(B)(C)(D)(4)在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是(A)13,48(B)24,48(C)24,53(D)24,90(5)在一棵度数为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是(A)41(B)82(C)113(D)122(6)对n(n=2)个权值均不相同的字符构成哈弗曼树,关于该树的叙述中,错误的是(A)该树一定是一棵完全二叉树(B)树中一定没有度为1的结点(C)树中两个权值最小的结点一定是兄弟结点(D)树中任一非叶结点的权值一定不小于下一层任一结点的权值(7)若无向图G=(V,E)中含7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是(A)6(B)15(C)16(D)21(8)对下图进行拓扑排序,可以得到不同的拓扑序列的个数是(A)4(B)3(C)2(D)1(9)已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是(A)4(B)5(C)6(D)7(10)采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是(A)递归次数于初始数据的排列次数无关(B)每次划分后,先处理较长的分区可以减少递归次数(C)每次划分后,先处理较短的分区可以减少递归次数(D)递归次数与每次划分后得到的分区处理顺序无关(11)对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序结果如下:第一趟:2,12,16,5,10,88第二趟:2,12,5,10,16,88第三趟:2,5,10,12,16,88则采用的排序方法可能是(A)冒泡排序法(B)希尔排序法(C)归并排序法(D)基数排序法2010-(41)(10分)将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一个一维数组散列,函数为:H(key)=(key×3)MOD7,处理冲突采用线性探测再散列法,要求装载因子为0.7.问题:(1)请画出所构造的散列表.(2)分别计算等概率情况下,查找成功和查找不成功的平均查找长度.2010-(42)(13分)设将n(n1)个整数存放到一维数组R中.设计一个在时间和空间两方面尽可能高效的算法.将R中的序列循环左移P(0Pn)个位置,即将R中的数据由(X0,X1,…,Xn-1)变换为(Xp,Xp-1,…,Xn-1,X0,X1,…,Xp-1).要求:(1)给出算法的基本设计思想.(2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释.(3)说明你所设计算法的时间复杂度和空间复杂度.2010年计算机考研试题详细解析1.D分析：快速解题，选项所给序列中出现长度大于等于3的连续逆序子序列，即为不符合要求的出栈序列。四个选项所给序列的进出栈操作序列分别为：按照题设要求，选项D所给序列即为不可能得到的出栈顺序。2.C分析：快速解题，无论哪种入队方式（即先从左边入队还是先从右边入队），a和b都应该相邻，这是出队序列合理的必要条件。只有选项C所给序列中a与b不相邻，可以确定正确选项为C。四个选项所给序列的进队操作序列分别为（L代表左入，R代表右入）：A.aL(或aR),bL,cR,dR,eRB.aL(或aR),bL,cR,dL,eRC.不可能出现D.aL(或aR),bL,cR,dR,eL3.D分析：线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息。题中所给二叉树的后序序列为d,b,c,a。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。正确选项为D。4.C分析：插入48以后，该二叉树根结点的平衡因子由-1变为-2，失去平衡，进行平衡调整，过程如下图：5.B分析：设树中度为i（i=0，1，2，3，4）的结点数分别为Ni，树中结点总数为N，则树中各结点的度之和等于N-1，即N=1+N1+2N2+3N3+4N4=N0+N1+N2+N3+N4，根据题设中的数据，即可得到N0=82，即树T的叶结点的个数是82。6.A分析：哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为１的结点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q与其兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。7.C分析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意六个结点构成完全连通子图G1，需15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。8.B分析：拓扑排序的步骤为：（1）在有向图中选一个没有前驱的顶点并且输出之；（2）从图中删除该顶点和所以以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列，分别为a,b,c,e,da,b,e,c,da,e,b,c,d。9.B分析：折半查找法在查找不成功时和给定值进行比较的关键字个数最多为+1，即折半查找判定树的高度，在本题中，n=16，故比较次数最多为5。10.D分析：本题实际考察了快速排序的时间复杂度分析，快速排序的效率与初始序列有关这是显然的，因此A错。对于B,C,D：折半查找法的算法可以简写为：voidqicksort(intR[],intl,intr){............qicksort(R,l,i-1);//①qicksort(R,i+1,r);//②}快速排序的递归次数由l和r决定（l和r决定了要处理问题的规模）。将快速排序的递归次数设为F(l,r)则按照上述代码中①②句的执行次序有：递归次数F(l,r)=F(l,i-1)+F(i+1,r)..........③如果将①②句颠倒，则有：递归次数F(l,r)=F(i+1,r)+F(l,i-1)..........④显然③和④式是相等的，因此递归次数与每次划分后得到的分区处理顺序无关。11.A本题考查起泡排序算法的执行过程。__41【参考答案】（1）因为装填因子为0.7，数据总数为7，所以存储空间长度为L=7/0.7=10因此可选T=10，构造的散列函数为H(key)=(key×3)MOD10线性探测再散列函数为：Hi(key)=(H(key)+di)MOD10,(di=1,2,3...9)因此，各数据的下标为H(7)=(7×3)MOD10=1H(8)=(8×3)MOD10=4H(30)=(30×3)MOD10=0H(11)=(11×3)MOD10=3H(18)=(18×3)MOD10=4H1(18)=(H(18)+1)MOD10=5H(9)=(9×3)MOD10=7H(14)=(14×3)MOD10=2由上述计算所得Hash表如下：下标0123456789关键字3071711818空9空空（2）由上表可以得：查找成功的平均查找长度为：ASL1=(1+1+1+1+2+1+1)/7=8/7查找不成功的平均查找长度为：ASL2=(7+6+5+4+3+2+1+2+1+1)=3.242【参考答案】（1）建立一个可以放下p个整数的辅助队列，将数组R中的前p个整数依次进入辅助队列，将R中后面的n-p个整数依次前移p个位置，将辅助队列中的数据依次出队，依次放入R中第n-p个整数开始的位置。（2）使用c语言描述算法如下：voidShift(intR[],intn,intp)//n为存放的整数个数，p为循环左移的个数{inttemp[p];//辅助数组，存放要移出的整数。inti=0;while(ip){//将R中前p个数据存入辅助数组中。temp[i]=R[i];i++;}i=0;while(in-p)//将R中从第p个整数开始的整数前移p个位置。{R[i]=R[p+i];i++;}i=0;while(ip)//将辅助数组中的p个数据放到R中第n-p个数据的后面。{R[n-p+i]=temp[i];i++;}}（3）所设计的算法的时间复杂度为O(n)，空间复杂度为O(p)。