算法设计与分析-考试题

12010－2011学年第一学期《算法设计与分析》试卷（A卷）授课班号年级专业2008计算机学号姓名题号123456总分审核题分151515152020得分1.（15分）假设某种算法在输入规模为n时的计算时间为n23nT，在计算机A上完成该算法的时间为t秒，现有另一台计算机B，其运行速度是A的64倍。①那么在计算机B上用同样的t秒时间能解决规模为多大的问题？②如果上述算法的时间时间复杂度改进为3nnT，其余条件不变，则在机器B上的用t/2秒的时间，能解决规模n为多大的问题？③如果算法的时间复杂度进一步优化为n8nT，其余条件不变，在机器B上解决规模为5n的问题，需要的时间是多少？2.（15分）针对n盘子的汉诺塔问题①写出算法的伪代码（或者C语言代码）。②分析算法的最好情况、最坏情况、平均情况时间复杂度（用大O表示）。3.（15分）给定一个随机数据序列X=niix1｝｛①如果X取如下的实例，X=(32,12,44,54,21,7,13,25,30)，写出手工完成插入排序的过程。②写出插入排序算法（伪代码或者c语言代码）。③分析算法的最好情况时间复杂度，最坏情况时间复杂度。4.（15分）幂指数计算问题:写出一个时间复杂度最好的算法，计算na，并分析其时间复杂度。25.（20分）选择问题：找出序列X=niix1｝｛中的第k小元素。写出一个最好情况和平均情况时间复杂度都为O(n)的算法。6.（20分）给定一个随机数据序列X=niix1｝｛①如果X取如下的实例，X=(32,12,44,54,21,7,13,25,30)，写出手工完成快速排序的的过程。②写出快速排序算法（伪代码或者c语言代码）。③分析最好情况、最坏情况下的时间复杂度。32010－2011学年第一学期《算法设计与分析》试卷（A卷）授课班号年级专业2008计算机学号姓名参考答案题号123456总分审核题分151515152020得分1.（15分）假设某种算法在输入规模为n时的计算时间为n23nT，在计算机A上完成该算法的时间为t秒，现有另一台计算机B，其运行速度是A的64倍。①那么在计算机B上用同样的t秒时间能解决规模为多大的问题？②如果上述算法的时间时间复杂度改进为3nnT，其余条件不变，则在机器B上的用t/2秒的时间，能解决规模n为多大的问题？③如果算法的时间复杂度进一步优化为n8nT，其余条件不变，在机器B上解决规模为5n的问题，需要的时间是多少？解：①nnabbTT2323216416即得：62323nnb所以：6nnb②3621641bbnTT根据题意：abTT21，3362121nnb即：nnb342③nnTTab8)5.(8641。得abTT64542.（15分）针对n盘子的汉诺塔问题①写出算法的伪代码（或者C语言代码）。②分析算法的最好情况、最坏情况、平均情况时间复杂度（用大O表示）。解：①voidhan(intn,charA,charB,charC){if(n0){han(n-1,A,C,B);move(n,A,C);han(n-1,B,A,C);}}②时间复杂度的递推公式为1)1(2)(nTnT求解递推关系式（过程略）得：12)(nnT最好情况、最坏情况、平均情况时间复杂度都是T(n),即：)2()12(nnOO3.（15分）给定一个随机数据序列X=niix1｝｛①如果X取如下的实例，X=(32,12,44,54,21,7,13,25,30)，写出手工完成插入排序的过程。②写出插入排序算法（伪代码或者c语言代码）。③分析算法的最好情况时间复杂度，最坏情况时间复杂度。解:⑴插入排序过程初始：32,12,44,54,21,7,13,25,30第一轮：12,32,44,54,21,7,13,25,30第二轮：12,32,44,54,21,7,13,25,30……⑵插入排序算法voidinser_sort(intA[],intn){5for(i=1;in;i++){temp=A[i];for(j=i-1;j=0;j--){if(tempA[j])A[j+1]=A[j];elsebreak;}A[j]=temp;}}⑶最好时间复杂度nOnTnibest1111最好时间复杂度2111110)1(211nOnniTniniijworst4.（15分）幂指数计算问题:写出一个时间复杂度最好的算法，计算na，并分析其时间复杂度。解：最好的算法是分治法，算法思路如下：nnn,2222是奇数，是偶数nnnaaa算法：intpower(inta,intn){if(n=1)returna;if(n%2==0){r=power(a,n/2);returnr*r;}else{r=power(a,n/2);6returnr*r*a;}}时间复杂度分析：cnTnT2)(,（当n是偶数时，c=1，当n是奇数时，c=2）解方程得：nnOcnTloglog)(25.（20分）选择问题：找出序列X=niix1｝｛中的第k小元素。写出一个最好情况和平均情况时间复杂度都为O(n)的算法。解：算法描述：时间复杂度分析：①最坏情况情况时间复杂度T(n)=T(n-1)+n-1解得：T(n)=O(n2)7②最好情况和平均情况时间复杂度T(n)=T(n/2)+n-1解得：T(n)=O(n)6.（20分）给定一个随机数据序列X=niix1｝｛①如果X取如下的实例，X=(32,12,44,54,21,7,13,25,30)，写出手工完成快速排序的的过程。②写出快速排序算法（伪代码或者c语言代码）。③分析最好情况、最坏情况下的时间复杂度。解：①操作过程②算法voidQSort(R[],ints,intt){if(s=t){//长度大于1pivotloc=Partition(R,s,t);//对R[s..t]进行一次划分，并返回枢轴位置QSort(R,s,pivotloc-1);//对低子序列递归排序QSort(R,pivotloc+1,t);//对高子序列递归排序}//if}//QsortintPartition(R[],intlow,inthigh){R[0]=R[low];//将枢轴记录移至数组的闲置分量pivotkey=R[low];//枢轴记录关键字while(lowhigh){//从表的两端交替地向中间扫描while(lowhigh&&R[high]=pivotkey)--high;R[low++]=R[high];//将比枢轴记录小的记录移到低端while(lowhigh&&R[low]=pivotkey)++low;R[high--]=R[low];//将比枢轴记录大的记录移到高端8}//whileR[low]=R[0];//枢轴记录移到正确位置returnlow;//返回枢轴位置}③时间复杂度分析最好情况时间复杂度：T(n)≤2T(n/2)＋n≤2(2T(n/4)＋n/2)＋n＝4T(n/4)＋2n≤4(2T(n/8)＋n/4)＋2n＝8T(n/8)＋3n………≤nT(1)＋nlog2n＝O(nlog2n)因此，最好时间复杂度为O(nlog2n)。最坏情况时间复杂度)()1(21211nOnninni）（