算法复习题-2015

1算法分析与设计复习提纲第一章算法引论1、算法的定义以及五个特征算法是完成特定任务的有限指令集，所有的算法都必须满足以下5个特征：即，输入、输出、确定性、有限性、能行性或可行性。2、算法与程序的主要区别算法必须满足定义中的5个特征，而程序不需要满足5个特征中的（C）A.输入B.确定性C.有限性D.能行性3、算法的空间复杂度算法的空间复杂度是指其运行所需的存储空间。程序运行所需的存储空间主要由两部分组成，即固定空间需求和可变空间需求。4、算法的时间复杂度算法的时间复杂度是指算法运行所需的时间，时间复杂度通常包括最好、最坏和平均时间复杂度。5、在算法的时间复杂度分析中，其中比较容易分析和计算且最有实际价值的是（A）A.最坏时间复杂度B.最好时间复杂度C.平均时间复杂度D.最好时间复杂度和最坏时间复杂度6、程序步一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。7、给定的一个m次多项式，f(n)=amnm+am-1nm-1+......+a1n+a0是m次多项式，且am0，则有f(n)=O(nm)。例如：若f(n)=3.6n3+2.5n2+3.8，则有f(n)=O(n3)。8、多项式时间算法凡可用多项式函数来对其计算时间限界的算法称为多项式时间算法。常用的多项式时间算法的时间复杂度可能为O(1)，O(log2n)，O(nlog2n)，O(n3)，O(n2)，O(n)则给定的这六种多项时间算法的时间复杂度的大小关系为O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)9、指数时间算法凡可用指数函数来对其计算时间限界的算法称为指数时间算法。常用的指数时间算法的时间复杂度可能为：O(nn)，O(2n)，O(n!)则给定的这三种指数时间算法的时间复杂度的大小关系为O(2n)O(n!)O(nn)10、下面算法的时间复杂度是（O(n)）intSum2(intn){inttotal,i;total=0;i=1;while(i=n){total=total+i;i=i+2;}returntotal;}11、下面算法的时间复杂度是（O(log2n)）2intSum4(intn){inti=1,total=0;while(i=n){total=total+i;i=i*2;}returntotal;}12、下面算法的时间复杂度是（O(n)）i=s=0;while(sn){i++;s+=i;}13、下面算法的时间复杂度是（O(n2)）sum=0;for(inti=0;in;i++)for(intj=0;j=i;j++)sum=sum+a[i][j];第二章枚举算法1、完美数的判定算法（1）任何一个自然数都能被1和它本身所整除，而所有小于它本身的因子称为这个自然数的真因子，如果一个自然数的所有真因子之和等于这个自然数本身，则称这个自然数为完美数。下面给出的（B）是完美数。A5B6C7D8（2）完美数的判定算法如下intperfect(intn)//判断自然数n是否为完美数{inti,sum=0;for(i=1;i=n/2;i++)//穷举出n的所有可能的真因子if(n%i==0)//条件成立，则说明i是n的一个真因子sum=sum+i;//将真因子累加到变量sum中if(sum==n)//条件成立，则满足了完美数的定义return1;elsereturn0;}2、逆序数问题设a[1:n]是一个具有n个不同元素的数组，数组的下标从1开始存储，用a[1]~a[n]这n个单元存储这n个元素。如果对于数组中的任意两个下标i和j（1≤i≤n，1≤j≤n），当ij时，有a[i]a[j]，则数偶（a[i]，a[j]）就称为数组a的一个逆序。例如，对于数组a[1:5]={2，3，8，6，1}来说，因为a[1]=2a[5]=1，a[2]=3a[5]=1，a[3]=8a[5]=1，a[4]=6a[5]=1，a[3]=8a[4]=6，所以数组a共有5个逆序。（1）数组a[1：6]={4，7，3，6，8，2}共有（A）个逆序数A8B9C10D7（2）求逆序数的枚举程序如下3intmain(){inti,j,n,number=0;inta[100];scanf(%d,&n);for(i=1;i=n;i++)scanf(%d,&a[i]);for(i=1;i=n-1;i++)//i是数偶中第一个数的可能下标for(j=i+1;j=n;j++)//j是数偶中第二个数的可能下标if(a[i]a[j])number++;//累计逆序数偶个数printf(数组中的逆序个数为%d\n,number);system(pause);return0;}3、最简真分数对于一个分数而言，如果它的分子小于分母，则我们称这样的分数为真分数，如果一个真分数的分子与分母无大于1的公因子，即不存在大于等于2的公因子，则称这样的真分数为最简真分数。例如2/3,3/7,5/9等都是最简真分数，而3/9,7/5就不是最简真分数。（1）下面所给出的分数中是最简真分数的为（B）A2/4B3/4C7/3D4/8（2）分母在2到5之间的最简真分数共有（B）个。A8B9C10D7注意：这9个最简真分数分别是1/2,1/3,2/3,1/4,3/4,1/5,2/5,3/5,4/5（3）最简真分数问题的枚举算法如下intmain()//该程序求分母在[a,b]区间内的最简真分数的个数，并求这些//最简真分数以递增次序排列时的第k项{inti,j,u,t,a,b,k,n=0;intc[3000],d[3000];scanf(%d%d%d,&a,&b,&k);for(j=a;j=b;j++)//j表示分母的取值范围for(i=1;i=j-1;i++)//i表示最简真分数的分子的可能取值范围{for(u=2;u=i;u++)//u表示分子i和分母j的可能存在的大于1的公因子if(i%u==0&&j%u==0)break;if(ui){n++;//累计最简真分数的个数c[n]=i;//数组c存储每个最简真分数的分子d[n]=j;//数组d存储每个最简真分数的分母}}for(j=1;jn;j++)//用冒泡排序法对n个分数进行递增排序4for(i=1;i=n-j;i++)if(c[i]*d[i+1]c[i+1]*d[i])//比较c[i]/d[i]和c[i+1]/d[i+1]的大小{t=c[i];c[i]=c[i+1];c[i+1]=t;//分子分别相交换t=d[i];d[i]=d[i+1];d[i+1]=t;//分母分别相交换}printf(%d\n,n);printf(第%d个最简真分数为%d/%d,k,c[k],d[k]);getch();return0;}第三章分治算法1、分治法解题步骤（简答题）第一步是将待求解的问题分解成若干规模较小、相互独立，且与原问题类型相同的子问题；第二步是递归地求解这些子问题的解；第三步是将各个子问题的解合并成原问题的解。用三个字来概括就是“分，治，合”。2、分治法求解的基本要素（简答题）第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解；3、分治算法的执行时间一般满足下列递归式：(1)1()()1kOnTnnaTcnnb该递归式的解的形式为：2()()()()bkkkklogakOnabTnOnlognabOnab（1）若一个分治算法的运行时间满足T(n)=8T(n/2)+2n3，则该算法的时间复杂度为（O(n3logn)）。（2）若另一个分治算法的运行时间满足T(n)=8T(n/2)+2n2，则该算法的时间复杂度为（O(n3)）。4、分治法求解最大最小元素问题以下是分治法求解最大最小元素问题算法。voidMaxMin(inta[],inti,intj,int&max,int&min)//求数组a[i:j]的最大值和最小值，用//max返回最大值，用min返回最小值{if(i==j)max=min=a[i];//数组中只有一个元素的情况elseif(i+1==j)//数组中只有两个元素的情况{if(a[i]a[j]){max=a[i];min=a[j];}else5{max=a[j];min=a[i];}}else//数组中元素个数大于2时{intmid=(i+1)/2;//问题分解，求分割点intmax1,min1;MaxMin(i,mid,max,min);//递归求解左子数组的最大子段和MaxMin(mid+1,j,max1,min1);//递归求解右子数组的最大子段和if(maxmax1)//两个子数组的最大值进行比较max=max1;if(minmin1)//两个子数组的最小值进行比较min=min1;}}2．若用T(n)表示该算法的运行时间，则T(n)满足下式：请选择下面两个问题的解。（1）当n2时，若解出T(n)，则T(n)=（C）A.2n+2B.2n+3C.3n22D.2n-2（2）该算法的时间复杂度为（D）A.O（n4）B.O（n3）C.O（n2）D.O（n）5、将待排序的数组分解成左右两个规模大致相同的子数组，然后对这两个子数组分别进行排序，再将排好序的两个有序子数组归并成一个数组是归并排序的基本思想。以待排序数组的某个元素x为主元，将待排序数组划分成小于x、等于x和大于x的三部分，并对不等于x的两部分分别递归排序的方法是快速排序的基本思想。6、快速排序（1）基于分治策略的快速排序算法如下。intpartition(inta[],intlow,inthigh)//对数组a[low:high]进行分划操作{inti=low,j=high+1,t;//i指向主元位置，j指向哨兵位置while(ij){i++;while(a[i]a[low])i++;//当左指针i指向的元素小于主元时，左指针i右移j--;while(a[j]a[low])j--;//当右指针j指向的元素大于主元时，右指针j左移if(ij){t=a[i];a[i]=a[j];a[j]=t;}}t=a[low];a[low]=a[j];a[j]=t;T(n)=0n=11n=22T(n/2)+2n26returnj;}voidquicksort(inta[],intlow,inthigh)//对数组a[low:high]进行递增快速排序{if(lowhigh){intj=partition(a,low,high);quicksort(a,low,j-1);quicksort(a,j+1,high);}}（2）设有9个元素的数组a[1:9]=(65,70,75,80,85,60,55,50,45)，则该序列的第一趟快速排序后的结果为604550556585807570（3）设有9个元素的数组a[1:9]=(70,26,57,88,42,80,72,48,60)，则该序列的第一趟快速排序后的结果为4826576042707280887、分治法求解最大子段和问题的算法如下intmaxsum_dac(inta[],intleft,intright){intsum=0,mid,leftsum=0,rightsum=0,s1=0,s2=0,lefts=0,rights=0,i;if(left==right)sum=a[left]0?a[left]:0;else{mid=(left+right)/2;//求分割点，二分等分leftsum=maxsum_dac(a,left,mid);rightsum=maxsum_dac(a,mid+1,right);for(i=mid;i=left;i--){lefts+=a[i];if(leftss1)s1=lefts;}for(i=mid+1;i=right;i++){rights+=a[i];if(