2010年联考《408计算机学科专业基础综合》真题答案.pdf

计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解。请见：网学天地(www.e-);咨询QQ:2696670126算法可以用两个函数，即Reverse()和LeftShiftO)实现相应的功能，后者调用Reverse(函数3次。算法如下：void Reverse(int R,int left,int right)int k=left,j=right,tmp;/k等于左边界1eft,j等于右边界rightwhile(k068pn)Reverse(R0,hp-)www.e-stud/将全部数据逆置/将前n-p个元素逆置Reverse(R,n-p,n-1);/将后P个元素逆置【(1)、(2)的评分说明】考生所给算法的时间复杂度及空间复杂度分别为O()和O(1),且算法实现正确，可给11分：若时间复杂度超过O()或空间复杂度超过O(1),能得到正确结果的，最高可给7分：若时间复杂度超过O()且空间复杂度超过O(1),能得到正确结果的，则最高可给3分。若在算法的基本设计思想描述中因文字表达没有非常清晰地反映出算法思路，但在算法中能够清晰地看出算法思想且正确的，可参照的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。参考答案中只给出了使用C语言的版本，使用C+/小ava语言的答案视同使用C语言。(3)说明算法复杂性：（2分)上述算法的时间复杂度为O(),空间复杂度为O(I)。【评分说明】若考生所顾忌的时间复杂度及空间复杂度与考生所实现的算法一致，可给2分。43.【答案要点】