算法设计与分析复习试题及答案.docx

一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特 殊类型问题的一系列运算，此外，算法还应具有以下五个重要特 性: , , , , 。
算法的复杂性有 和 之分，衡量一个算法
好坏的标准是 。
某 一 问 题 可 用 动 态，使得装入背包中物品的总
i
价值最大。
三、简答题
l.
void sort(flowjope s[],int n)
int i,k,j,l;
for(i=1;i<=n-1;i++)// 选择排序
{
k=i;
while(k<=n&&s[k].tag!=0) k++;
if(k>n) break;// 没有 a^ 跳出
else
{
for(j=k+1;j<=n;j++)
if(s[j].tag==0)
if(s[k].a>s[j].a) k=j;
swap(s[i].index,s[k].index);
swap(s[i].tag,s[k].tag); }
}
Z——记下当前第一个bi的下标
for(i=l;i<=n-1;i++)
{
k=i;
for(j=k+1;j<=n;j++)
if(s[k].b<s[j].b) k=j;
swap(s[i].index,s[k].index); // 只移动 index 和 tag
swap(s[i].tag,s[k].tag); }
2.
void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) {
int i,j,k,t,l;
for(i=1;i<=n+1;i++)
{ w[i][i-1]=a[i-1];
m[i][i-1]=0;}
for(l=0;l<=n-1;l++)// l 是下标 j-i 的差
for(i=1;i<=n-l;i++)
{ j=i+l;
w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];
s[i][j]=i; for(k=i+1;k<=j;k++)
{ t=m[i][k-1]+m[k+1][j]+w[i][j]; if(t<m[i][j])
{ m[i][j]=t; s[i][j]=k;
}
}
一、 填空题(本题15分，每小题 1分)
1、 算法就是一组有穷的 ,它们规定了解决某一特定类型问
题的 。
2、 在进行问题的计算复杂性分析之前,首先必须建立求解问题所
用的计算模型。3个基本计算模型是 、 、 。
3、 算法的复杂性是 的度量，是评价算法优劣的重要依据。
4、 计算机的资源最重要的是 和 资源。因而，算法的复
杂性有 和 之分。
5、 f(n)= 6x2n+n2，f(n)的渐进性态 f(n)= 0(? ??)
6、 贪心算法总是做出在当前看来 的选择。也就是说贪心算
法并不从整体最优考虑，它所做出的选择只是在某种意义上
的 。
7、 许多可以用贪心算法求解的问题一般具有2个重要的性质：
性质和 性质。
二、 简答题(本题25分，每小题5分)
1、 简单描述分治法的基本思想。
2、 简述动态规划方法所运用的最优化原理。
3、 何谓最优子结构性质？
4、 简单描述回溯法基本思想。
5、 何谓P、NP、NPC问题
三、 算法填空(本题20分，每小题5 分)
1、n后问题回溯算法
用二维数组A[N][N]存储皇后位置，若第i行第j列放有皇后，则
为非0值，否则值为0。
分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、 右斜线是否放有棋子，有则值为1，否则值为0。
for(j=0;j<N;j++)
if( 1 ) /*安全检查*/
{ A[i][j]=i+1; /*放皇后*/
2 ；
if(i==N-1) 输出结果；
else 3 ； ; /*试探下一行*/
4 ； /*去皇后*/
2、数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可 以选择向左走或是向右走，一起走到底层，要求找出一条路径，使
路径上的值最大。
for(r二n-2;r〉=0;r--) //自底向上递归计算
for(c=0; 1 ；c++)
if( t[r+l][c]〉t[ r+l][c+l]) else 3 ；
3、Hanoi 算法
Hanoi(n,a,b,c)
if (n==1) 1
else
{ 2 ;
3 ；
Hanoi(nT,b, a, c);
}
4、Dijkstra算法求单源最短路径
d[u]:s到u的距离 p[u]:记录前一节点信息
Init-single-sou