武科大算法设计与分析试卷A及答案(2008级).doc

（附 5 页 ）
试题纸（A卷）
课程名称： 算法设计与分析 适用专业年级： 2008级计算机、电本
考生学号： 考 生 姓 名：
………………………………………………………………………………………………………………………
题号
一
二
三
四
总分
分数

一、 填空题（10空×2分，共20分）　　
1、 算法在运行时占有的机器资源的量称为算法复杂性，主要包括（ ）和（ ）。
2、 当一个算法的运行时间为n2+n+1时，由于n2+n+1与n2的数量级相等，则称n2为这个算法的（ ）。
3、 多项式A(n)=amnm+…+ a2n2+ a1n+ a0的上界为（ ）。
4、 递归算法设计的关键在于找出（ ）和（ ）。
5、 （ ）是问题能用贪婪算法或动态规划方法求解的前提。
6、 拆半查找、合并排序、二叉树遍历等算法中均采用了（ ）策略。
7、 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种（ ）的思想作为其控制结构 。
8、 用分支限界法解决布线问题时，对问题解空间搜索尝试结束的标志是（ ）。
二、 判断题（10题×2分，共20分）
1. 若c是正常数，则O(cf(n))=O(f(n))。
2. 在最好情况下、最坏情况下、平均情况下的时间复杂度中，可操作性最好的且最有实际价值的，是平均情况下的时间复杂度。
3. 所有的递归函数都能找到对应的非递归定义。
4. 好的算法在很大程度上取决于问题中数据所采用的数据结构。
5. 迭代模型是通过小规模问题的解逐步求解大规模问题的解，正好与递归算法设计相反。
6. 用贪婪算法解决零钱兑换问题时，总能找到问题的最优解。
7. 适用动态规划算法解决问题应该具有最优化原理和子问题重叠。
8. 深度优先搜索算法可以搜索到问题所有可能的解方案。
9. 解决马的遍历问题采用回溯法，对解空间树的搜索采用广度优先搜索方式
10. 分支限界法的求解目标是找出满足约束条件的一个解或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解。
三、 简答题（3题×6分，共18分）
1、叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。
2、在算法设计的实际应用中，遇到的问题主要分为4类：判定性问题、计算问题、最优化问题和构造性问题，请指出递归法、递推法、贪婪算法、分治法、动态规划法、搜索算法各自适合解决的问题。
3、简述回溯法求解问题的一般步骤。
四、 程序填空题（6空×3分，共18分）
1、 找出n个自然数(1，2，3，…，n)中取r个数的组合。例如，当n=4,r=3时，所有的组合为：
4 3 2
4 3 1
4 2 1
3 2 1
以下是算法，请填空。
void comb(int n,int r)
{
int i,j;
for(i=n; ① ; i--)
{
② ;
if(r>1)
③ ;
else
{
for(j=a[0]; j>0; j--)
printf("%3d",a[j]);
printf("\n");
}
}
}

2、 走迷宫问题。迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（用 “1”表示）有的是路（用“0”表示）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)，出口是右下角(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。
数据结构：数组maze[8][8]存放迷宫；用数组fx[4]={1,-1,0,0},fy[4]={0,0,-1,1}模拟上下左右搜索时的下标的变化过程；用迷宫原有的存储空间置元素值为“-1”时，标识已经访问过该方格。用数组做队的存储空间，队中的成员有三个：行号、列号、前一个方格在队列中的下标。
struct {int x,y,pre}sq[100];
search()
{ qh=0; qe=1;
maze[1][1]= ④ ;
sq[1].pre=0; sq[1].x=1; sq[1].y=1;
while( ⑤ )
{ qh=qh+1;
for(k=1;k<=4;k++)
{ i=sq[qh].x+fx[k];
j=sq[qh].y+fy[k];
if (check(i,j)=1) //check()用来检查该方格是否可行
{ ⑥ ;
sq[qe].x=i; sq[qe].y=j; sq[qe].pre=qh;
maze[i][j]=-1;
if(sq[qe].x=8 and sq[qe].y=8)
{ out(); return;} // out ()用来输出找到的路径
}
}
}
print(“No avaliable way.”);
}

五、 算法设计题（2题×12分，共24分）
1、输入一个高精度数据s和一个长整数c， 求s×c的精确值。
2、如下图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。

08级算法设计与分析（A卷）答案
一、 填空题（10空×2分，共20分）
1、 时间复杂度 空间复杂度
2、 渐近时间复杂度或时间复杂度
3、 nm
4、 递归关系（递归方程） 递归终止（边界）条件
5、 无后效性
6、 分治算法
7、 走不能就掉头
8、 搜索到达b结点 或 活结点队列为空
二、 判断题（10题×2分，共20分）
1-5
√
×
×
√
√
6-10
×
×
√
×
√
三、 简答题（3题×6分，共18分）
1、 答：两者都是递归算法思想的应用，根本策略是找出大规模问题与小规模子问题之间的关系，直到小规模的子问题容易得到解决，再由小规模子问题的解逐步导出大问题的解。
分治法能解决问题的特征：
1)问题的规模缩小到一定的程度就可以容易地解决。
2)问题可以分解为若干个规模较小的相似问题，即该问题具有最优子结构性质。
3)利用该问题分解出的子问题的解可以合并为该问题的解。
4)该问题所分解出的各个子问题是相互独立的且子问题之间不包含公共的子问题。
当问题满足1，2，3，4条时采用分治法，当满足1、2、3条时采用动态规划方法。

2、"递推法"、"递归法"适合解决判定性问题和计算问题。
“贪婪算法”、“分治法” 、“动态规划法” 适合解决最优化问题。
“贪婪算法”、“分治法” 、“搜索算法” 适合解决 构造性问题。

3、回溯法是在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树，当算法搜索至解空间树的任一结点时，总是先判断该结点是否满足问题的约束条件。如果满足进入该子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。

四、 程序填空题（6空×3分，共18分）
1
i>=r
a[r]=i
comb(i-1,r-1)
2
-1
qh<>qe
qe=qe+1
五、 算法设计题（2题×12分，共24分）
1、
main( )
{
long b,c,d; int a[256],i,j,n; char s1[256];
input(s1,c);
n=strlen(s1);
d=0;
for(i=0,j=n-1;i<n;i++,j--)
{ b=(s1[j]-48)*c+d;
a[i]=b%10;
d=b/10;
}
while(d!=0)
{ a[n]=d%10;
d=d/10;
n++;
}
for(i=n-1;i>=0;i--)
print(a[i]);
}
2、
main( )
{ int a[50][50][3],i,j,n;
print( 'please input the number of rows:');
input(n);
　for(i=1;i<=n;i++)
　　 for(j=1;j<=i;j++)
　　 { input(a[i][j][1]);
　　　　 a[i][j][2]=a[i][j][1];
　　　　 a[i][j][3]=0;
}
for(i=n-1;i>=1;i--)
for(j=1;j>=i ;j++)
　　　if(a[i+1][j][2]>a[i+1][j+1][2])
　　 { a[i][j][2]=a[i][j][2]+a[i+1][j][2];
a[i][j][3]=0;
}
　 else
　　　 { a[i][j][2]=a[i][j][2]+a[i+1][j+1][2];
a[i][j][3]=1;
}
print(“max=“,a[1][1][2]);
j=1;
for(i=1;i<=n-1;i++)
{ print(a[i][j][1],‘->’);
　 j=j+a[i][j][3];
}
print(a[n][j][1]);
}

注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。