2010计算机统考复习指导

计算机统考复习中的数据结构复习指导殷人昆北京清航教育校长清华大学计算机系教授一、总体分析计算机科学与技术学科全国硕士研究生统一入学考试已经进行了两次。数据结构部分的考试范围要求掌握：1，基本数据结构的知识2，算法设计和编程的能力3，综合应用算法和数据结构的技能从考试的命题来看，2010年比2009年的题目难度要大一些。在这里，我对2009年考题与2010年考题的考试范围进行了简单的比较：A,选择题部分，请参考表12009年2010年1.队列与缓冲区1.进栈与出栈序列2.栈与队列的操作2.双端队列的出队序列3.几种二叉树遍历的方式3.后序线索二叉树的表示4.完全二叉树的性质4.平衡二叉树的插入5.平衡二叉树的定义5.K叉树叶结点的计算6.森林的二叉树表示6.Huffman树的定义和特点7.无向连通图的定义7.无向连通图的最少边数8.m阶B树的定义8.拓扑排序序列9.堆的定义和插入方法9.折半查找的性能分析10.几种排序方法10.快速排序递归次数表12010年选择题还有一道题（11题）是对几种排序方法的考察。由表1我们可以总结出，在选择题部分，各主要知识点分布如下，请参考表2：考察内容2009年2010年栈、队列与双端队列22树与二叉树、森林44图12查找11排序22表2B，综合应用题部分的试题范围如下：2009年2010年41.求解图的最短路径41.散列表构造、数据存储及性能分析42.算法设计：在单链表中求倒数第k个结点位置42.算法设计：将一维数组中所有元素循环左移p位总体上讲，2009年的试题较简单，2010年的试题比较复杂，且难度稍大，但平时教学中应当都教过，或练习都做过。二、2010年考试改卷的基本情况2010年考试改卷的大概情况如下：客观题是机改，数据结构部分总分22分，平均得分约为17分，失分较多的是第2题（双端队列）第5题（K叉树叶结点的计算）第8题（拓扑排序的序列个数）第10题（快速排序递归次数）；主观题是人改，数据结构部分总分23分第41题10分，平均得分5分，失分最多的是计算散列表长度（2分），多数考生未得分。将给定元素存储到散列表中（6分），平均得3分。如果第1问错了，不影响第2问得分；但可惜散列函数有不少同学选择不完全对。计算平均查找长度（2分），平均得1分。第42题是算法设计题13分，平均得6～8分，失分最多的是算法效率达不到要求。许多考生成绩差的主要原因：1，本科数据结构课程学习不够扎实；2，考前复习不够充分；3，考试时审题不仔细，急于给出答案，未严格推导。三、2010年考试试卷分析由于篇幅有限，在此只例举综合题两道大题进行分析。二、综合应用题41题：（10分）将关键字序列{7,8,30,11,18,9,14}散列存储到散列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列，函数为：H(key)=(key3)MOD7处理冲突采用线性探测再散列法，要求装载因子为0.7问题：(1)请画出所构造的散列表。(2)分别计算等概率情况下，查找成功和查找不成功的平均查找长度。解答：这是一道常规的数据结构题目。实际上要做三步工作：计算表的长度，从而将7个数据存储到散列表中，最后计算等查找概率情形下，查找成功和查找不成功的平均查找长度。(1)根据题意，表的装载因子为=n/m=0.7，n=7，因此有m=n/=10，即表长度为m=10。分别计算各个数据元素的散列地址：H(7)=(7*3)mod7=0，一次比较到位H(8)=(8*3)mod7=3，一次比较到位H(30)=(30*3)mod7=6，一次比较到位H(11)=(11*3)mod7=5，一次比较到位H(18)=(18*3)mod7=5，冲突，=6，冲突，=7，三次比较到位H(9)=(9*3)mod7=6，冲突，=7，冲突，=8，三次比较到位H(14)=(14*3)mod7=0，冲突，=1，二次比较到位根据以上得到的各数据元素的散列地址，可以得到如下散列表：图1图142题：（13分）设将n(n1)个整数存放到一维数组R中。设计一个在时间和空间两方面尽可能高效的算法。将R中的序列循环左移p（0pn）个位置，即将R中的数据由(a0,a1,……an-1)变换为(ap,ap-1,…an-1,a0,a1,…,ap-1)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或JaVa语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。解答：此算法即有名的海豚算法。解法一（标准答案）算法基本思路是首先把序列{a0,a1,...,ap,…,an-1}逆转为{an-1,an-2,...,ap,…,a0}，再分别逆转{an-1,an-2,...,ap}和{ap-1,ap-2,…,a0}，最后得到{ap,ap+1,…,an-1,a0,…,ap-1}。(1)逆转算法voidreverse(intA[],intleft,intright){intn=right-left+1;if(n=1)return;if(n=1)return;for(inti=0;in/2;i++){inttemp=A[i];A[i]=A[n-i-1];A[n-i-1]=temp;}}(2)循环左移算法voidsift_Left(inta[],intn,intp){reverse(a,0,n-1);reverse(a,0,n-p-1);reverse(a,n-p,n-1);}第一个reverse函数执行了3n/2次数据移动，使用了一个辅助存储；第二个reverse函数执行了3(n-p)/2次数据移动，使用了一个辅助存储；第三个reverse函数执行了3p/2次数据移动，使用了一个辅助存储；总共执行了3n次数据移动，使用了1个辅助存储。解法二（利用最大公约数）清华阅卷组给出如果n与p不互质，一次循环左移只涉及间隔为p如果n与p不互质，一次循环左移只涉及间隔为p的部分数据元素，可先求n与p的最大公约数m,再做m次循环左移，每次比上次右错一位，从而实现所有数据元素的循环左移。例如，n=10，p=4，m=2，做2次循环左移。第1次涉及位置0-4-8-2-6，第2次涉及位置1-5-9-3-7。(1)求n与p的最大公约数的算法intGCD(intn,intp){//函数用辗转相除法计算n与p的最大公约数,若n//与p互质,则函数返回1.if(np){inttemp=n;n=p;p=temp;}intr=n%p;while(r!=0){n=p;p=r;r=n%p;}returnp;}(2)循环左移算法voidsift_k(inta[],intn,intp){if(!p)return;inti,j,m,k,temp;m=GCD(n,p);for(k=0;km;k++){temp=a[k];i=k;j=(i+p)%n;while(j!=k){a[i]=a[j];i=j;j=(j+p)%n;}a[i]=temp;}}解法三（解法二的改进型）清航考研给出调用子程序需要花费较多的时间和空间代价，本算法省去了计算最大公约数，仅利用一个控制变量控制循环左移的次数，效果更好。voidsiftLeft_p(inta[],intn,intp){if(!p)return;inti,j;inttemp;intcount=0,k=0;while(countn){i=k;temp=a[i];j=(i+p)%n;while(j!=k){a[i]=a[j];i=j;j=(i+p)%n;count++;}a[i]=temp;count++;k++;}}设m为n与p的最大公约数，则最内层while循环执行m次，每次循环执行n/m+1次数据移动，包括与temp的相互传送2次，总的数据移动次数为m*(n/m+1)=n+m。特别地，当p=n时，m=n，最内层while循环不执行，总的数据移动次数2n，做了n次与temp的传出和传入；当p=0时，总的数据移动次数为0。算法用了一个附加存储temp。解法四（被扣了分的算法）很多考生使用了一个附加数组，先暂存子序列{a0,a1,...,ap}，再把序列中后面的n-p个数据元素前移，得{ap,…,an-1}；最后把暂存到临时数组中的子序列拷贝到an-1后面，得到结果：{ap,…,an-1,a0,a1,...,ap}由于使用的附加空间较多，相应也扣了一些分。算法移动元素的次数为n+p；特别地，当n=p时，算法移动元素的次数为2n。