算法复习题-2015

算法分析与设计复习提纲

第一章 算法引论

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次多项式，且am>0，则有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(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)）

1

int Sum4(int n){ int i=1, total=0;

while(i<=n) { total=total+i; i=i*2; } return total; }

12、下面算法的时间复杂度是（O(n)）

i=s=0;

while(s

13、下面算法的时间复杂度是（O(n2)）

sum=0;

for(int i=0;i

第二章 枚举算法

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），当ia[j]，则数偶（a[i]，a[j]）就称为数组a的一个逆序。例如，对于数组a[1:5]={2，3，8，6，1}来说，因为a[1]=2>a[5]=1，a[2]=3>a[5]=1，a[3]=8>a[5]=1，a[4]=6>a[5]=1，a[3]=8>a[4]=6，所以数组a共有5个逆序。

（1）数组a[1：6]={4，7，3，6，8，2}共有（ A ）个逆序数 A 8 B 9 C 10 D 7 （2）求逆序数的枚举程序如下

2

int main() {

int i,j,n,number=0; int a[100];

scanf(\ for(i=1;i<=n;i++)

scanf(\

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\ system(\ return 0; }

3、最简真分数

对于一个分数而言，如果它的分子小于分母，则我们称这样的分数为真分数，如果一个真分数的分子与分母无大于1的公因子，即不存在大于等于2的公因子，则称这样的真分数为最简真分数。例如2/3,3/7,5/9等都是最简真分数，而3/9,7/5就不是最简真分数。

（1）下面所给出的分数中是最简真分数的为（ B ） A 2/4 B 3/4 C 7/3 D 4/8

（2）分母在2到5之间的最简真分数共有（ B ）个。

A 8 B 9 C 10 D 7

注意：这9个最简真分数分别是1/2,1/3,2/3,1/4,3/4,1/5,2/5,3/5,4/5

（3）最简真分数问题的枚举算法如下

int main() //该程序求分母在[a,b]区间内的最简真分数的个数，并求这些//最简真分

数以递增次序排列时的第k项

{ int i,j,u,t,a,b,k,n=0; int c[3000],d[3000];

scanf(\

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(u>i) {

n++; //累计最简真分数的个数

c[n]=i; //数组c存储每个最简真分数的分子 d[n]=j; //数组d存储每个最简真分数的分母 } }

for(j=1;j

3

for(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(\ \\n\

printf(\第%d个最简真分数为%d/%d \ getch(); return 0; }

第三章 分治算法

1、分治法解题步骤（简答题）

第一步是将待求解的问题分解成若干规模较小、相互独立，且与原问题类型相同的子问题；第二步是递归地求解这些子问题的解；第三步是将各个子问题的解合并成原问题的解。用三个字来概括就是“分，治，合”。 2、分治法求解的基本要素（简答题）

第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；

第二，子问题足够小时可以直接求解；

第三，能够将子问题的解组合成原问题的解； 3、分治算法的执行时间一般满足下列递归式：

O(1)n?1??T(n)??n)?cnkn?1 aT(?b?该递归式的解的形式为：

?O(nk)a?bk?T(n)??O(nklog2n)a?bk

?logbak?O(n)a?b（1）若一个分治算法的运行时间满足T(n)=8T(n/2)+2n3，则该算法的时间复杂度为（ O(n3logn) ）。

（2）若另一个分治算法的运行时间满足T(n)=8T(n/2)+2n2，则该算法的时间复杂度为（ O(n3) ）。

4、分治法求解最大最小元素问题

以下是分治法求解最大最小元素问题算法。

void MaxMin(int a[], int i,int j,int &max,int &min) //求数组a[i:j]的最大值和最小值，用

//max返回最大值，用min返回最小值

{ if(i==j) max=min=a[i]; //数组中只有一个元素的情况 else if( i+1==j ) //数组中只有两个元素的情况 { if(a[i]>a[j])

{ max=a[i]; min=a[j]; } else

4

{ max=a[j]; min=a[i]; } }

else //数组中元素个数大于2时 { int mid= (i+1)/2 ; //问题分解，求分割点 int max1,min1;

MaxMin(i,mid,max,min) ; //递归求解左子数组的最大子段和 MaxMin(mid+1,j,max1,min1); //递归求解右子数组的最大子段和 if(max

if(min>min1) //两个子数组的最小值进行比较 min=min1; } }

2．若用T(n)表示该算法的运行时间，则T(n)满足下式：

0 n=1

T(n)= 1 n=2

请选择下面两个问题的解。

（1）当n>2时，若解出T(n)，则T(n)=（ C ） A. 2n+2 B. 2n+3 C. （2）该算法的时间复杂度为（ D ）

A. O（n4） B. O（n3） C. O（n2） D. O（n）

5、将待排序的数组分解成左右两个规模大致相同的子数组，然后对这两个子数组分别进行排序，再将排好序的两个有序子数组归并成一个数组是归并排序的基本思想。以待排序数组的某个元素x为主元，将待排序数组划分成小于x、等于x和大于x的三部分，并对不等于x的两部分分别递归排序的方法是快速排序的基本思想。 6、快速排序

（1）基于分治策略的快速排序算法如下。

int partition(int a[ ],int low,int high) //对数组a[low:high]进行分划操作 {

int i=low, j=high+1,t; //i指向主元位置，j指向哨兵位置 while(i

i++;

while(a[i]

while(a[j]>a[low]) j--; //当右指针j指向的元素大于主元时，右指针j左移 if(i

{ t=a[i]; a[i]=a[j]; a[j]=t; } }

t=a[low]; a[low]=a[j]; a[j]=t;

5

2T(n/2)+2 n>2

3n?2 D. 2n-2 2

本文来源：https://www.bwwdw.com/article/o2wt.html