算法设计与分析-期末考试题整理.docx

算法设计与分析-期末考试题整理

1、一个算法应有哪些主要特征?

又穷性，确定性，可行性，0个或多个输入，一个或多个输出

2、分治法(DivideandConquer)与动态规划(DynamicProgramming)有什么不同?

分治算法会重复的求解公共子问题，会做许多不必要的工作，而动态规划对每个子问题之求解一次，将其结果存入一张表中，从而避免了每次遇到各个子问题有从新求解。

3、试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。

贪心算有效性：最小生成树、哈弗曼、活动安排、单元最短路径。

无效反例：0——1背包问题，无向图找最短路径问题。

4、求解方程f(n)=f(n-1)+f(n-2),f(1)=f(2)=1。

由f(n)=f(n-1)+f(n-2)可得

f(n)-f(n-1)-f(n-2)=0,可得方程的特征方程为

x2-x-1=0,设特征方程的2个根本分别为x,x?,则可得

,则有

又f(1)=f(2)=1可得

可得c?=a,c?=b

5、求解方程T(n)=2T(n/2)+1,T(1)=1,设n=2。

T(n)=2T(n/2)+1

2T(n/2)=22T(n/22)+2

22T(n122)=23T(n/23)+22

2?-T(n/2?-|)=2^T(n/2*)+2?-1

上面所有式子相加，相消得

T(n)=2^T(1)+2?+21+22+……+2-

=2+1-1

6、编写一个QuickSorting算法，并分析时间复杂性。

intpart(int*a,intp,intr){

intij,x,t;

x=a[r];

i=p-1;

for(j=p;j=r-1;j++){

if(a[j]=x){

i++;

t=a[i];

a[i]=a[j];

a[j]=t;

t=a[i+1];

a[i+1]=a[r];

a[r]=t;

returni+1;

voidquicksort(int*a,intp,intr){

intq;

if(pr){

q=part(a,p,r);

quicksort(a,p,q-1);

quicksort(a,q+1,r);

快速排序时间复杂度最坏情况为O(n2),平均为O(nlogn);

7、利用QuickSorting的原理，编写一个查找第k小元素的算法。

K不能大于数的长度。

intpart(int*a,intp,intr){

inti,j,x,t;

x=a[r];

i=p-1;

for(j=p;j=r-1;j++){

if(a[j]=x){

i++;

t=a[i];

a[i]=a[j];

a[j]=t;

t=a[i+1];

a[i+1]=a[r];

a[r]=t;

returni+1;

intk_last(int*a,inti,intj,intk){

intmid;

mid=part(a,i,j);

if((mid+1)==k){

printf(Right\n);

returna[mid];

elseif((mid+1)k)returnk_last(a,i,mid-1,k);

elseif((mid+1)k)returnk_last(a,mid+1,j,k);

8、编写一个HeapSorting算法，并分析时间复杂性。

voidmax_heapify(int*A,inti){

intlargest,t,I,r;

1=2*i;r=2*i+1;

if(l=heap_sizeAA[l]A[i])largest=l;elselargest=i;

if(r=heap_sizeAA[r]A[largest])largest=r;

if(largest!=i){

t=A[i];

A[i]=A[largest];

A[largest]=t

max_heapify(A,largest);

//保持最大堆性质

}

//建堆voidbuild_max_heap(int

//建堆

inti;

heap_sizeA=lenth;

for(i=lenth/2;i=1;i--){

max_heapify(A,i);

}

heapsort(int*A,intlenth){

inti,t;

build_max_heap(A,lenth);

for(i=lenth;i=2;i--){

t=A[1];

A[1]=A[i];

A[i]=t;

heap_sizeA--;

max_heapify(A,1);

}

9、编写一个算法，可以检测一个字符串是否回文(如：afaddafa,abwba等)。

intfun(c