算法复习题-2015.doc

算法分析与设计复习提纲 第一章 算法引论 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)） int Sum2(int n){ int total, i; total=0; i=1; while(i=n) { total=total+i; i=i+2; } return total; } 11、下面算法的时间复杂度是（O(log2n)） int Sum4(int n){ int i=1, total=0; while(i=n) { total=total+i; i=i*2; } return total; } 12、下面算法的时间复杂度是（O()） i=s=0; while(sn){ i++; s+=i; } 13、下面算法的时间复杂度是（O(n2)） sum=0; for(int i=0;in;i++) for(int j=0;j=i;j++) sum=sum+a[i][j]; 第二章 枚举算法 1、完美数的判定算法 （1）任何一个自然数都能被1和它本身所整除，而所有小于它本身的因子称为这个自然数的真因子，如果一个自然数的所有真因子之和等于这个自然数本身，则称这个自然数为完美数。下面给出的（ B ）是完美数。 A 5 B 6 C 7 D 8 （2）完美数的判定算法如下 int perfect(int n) //判断自然数n是否为完美数 { int i,sum=0; for(i=1;i=n/2;i++) //穷举出n的所有可能的真因子 if(n%i==0) //条件成立，则说明i是n的一个真因子 sum=sum+i; //将真因子累加到变量sum中 if(sum==n) //条件成立，则满足了完美数的定义 return 1; else return 0; } 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]=