算法设计与分析 期末试卷 A卷(完整含答案)(2)

2021-09-24 18:05

m[1][4] min m[1][2] m[3][4] p0p2p4 5000 2500 500 8000

m[1][3] m[4][4] ppp 7500 0 5000 12500

034

因此:m[1][4] 8000

4、操场上摆放一行共n堆石头,呈直线排列。n堆石子从左到右方向编号为1~n,每堆石子个数分别为a[1],…,a[n],现在要将石子有次序的合并为一堆,规定每次只能选相邻的2堆合并为新的一堆,并将新的一堆的石子数记为该次合并的得分,经过n-1次合并,最终合并为一堆,总得分为n-1次合并得分之和。现要设计一个算法,计算出将一行的n堆石子合并为一堆的最小得分。这里假设m[i,j]为合并石子Ai…Aj, 1≤i≤j≤n,所得到的最小得分。请写出m[i,j]的递推公式。(5分)

参考解答:设n堆石子从左到右方向编号为1,2,…,n,每堆石子个数分别为a[1],…,a[n]。n堆石子的合并有许多不同的方式,每种合并方式对应于n个矩阵连乘的一种完全加括弧方式。显然,这里合并是满足最优子结构性质的,用A1…An来代表每堆的石子,则最后一次合并在Ak和Ak+1之间,则A1…An的最优合并为((A1…Ak)(Ak+1…An)),可以看出最优解左边部分(A1…Ak)和右边部分(Ak+1…An)的合并也分别是最优的。

假设m[i,j]为合并石子Ai…Aj, 1≤i≤j≤n,所得到的最小得分,若没有“合并”这个动作,则为0。原问题所求的最优值即为m[1,n]。

i j 0 j

m[i,j]

min{m[i,k] m[k 1,j]} a[t]i j t i i k j

填充m[i,j]即可得到任意行状摆放的石子合并的最小得分。

5、有这样一类特殊0-1背包问题:可选物品重量越轻的物品价值越高。n=6,c=20,P=(4,8,15,1,6,3),W=(5,3,2,10,4,8)。其中n为物品个数,c为背包载重量,P表示物品的价值,W表示物品的重量。请问对于此特殊的0-1背包问题,为使放进背包的物品总价值最大,应如何选择放进去的物品?此例能获得的最大总价值多少?(5分)

参考解答:因为该0-1背包问题比较特殊,恰好重量越轻的物品价值越高,所以优先取重量轻的物品放进背包。最终可以把重量分别为2,3,4,5的三个物品放进背包,得到的价值和为15 + 8 + 6 + 4 = 33,为最大值。

得分

三、画图题(共16分,每图4分)

1、字符a~h出现的频率恰好是前八个Fibonacci数(数列最开始两个元素都为1,之后每个元素都等于前两个元素之和),请画出a~h这八个字符的Huffman编码树。(4分)

参考解答:若字符a~h出现的频率恰好是前8个Fibonacci数,它们的Haffman编码树如下图所示。

4

装

订

线

2、对如下问题采用回溯的搜索算法,请画出搜索状态的解空间树。注意这题无需说明算法或搜索过程,只画解空间树即可。(8分:4分+4分)

(1)作业分配问题:n个作业分配给n个人,将第i个作业分给第j个人所需费用代价为c[i][j],

为每个作业分配给不同的人来完成,并使得所有工作的总费用和最小。以n=3为例,请画出搜索的解空间树。

(2)图的m着色问题:给定n个顶点的无向连通图G和m种不同的颜色,用这m种颜色为图G的各顶点着色,且G中邻接顶点(指有边相连的顶点)不能着同色,求所有不同的着色方法

数。以n=3,m=3为例,请画出搜索的解空间树。

参考解答:

(1)

(2)

(1)n=3的排列树

(2)n=3,m=3的n层完全m叉树)

3、折纸留痕:你喜欢折纸吗?给你一张很大的纸,对折以后再对折,再对折……,每次对折都是从右往左折(沿逆时针),因此折了很多次以后,原来的大纸就会变成窄窄的纸条。现在把这个纸条沿着折纸的痕迹打开,把每个痕迹视为一个“直角”,那么从纸的一端沿着与纸面平行的方向看过去(即截面图),会看到一个曲线。例如,对折2次和3次,看到如下曲线。请你画出对折4次的截面曲线。(4分)

对折两次后形成的曲线

对折三次后形成的曲线

参考解答:

5

对折四次后形成的曲线

得分

四、程序填空题(共12个空格,每空2分,共24分, 结果集中的填于程序下方划线处) 1、有重复元素的全排列:对n个元素集 R = {r1, r2, …, rn}进行全排列,其中r1,r2,…,rn可能相同,下面算法框架Permpp( )可以输出R的所有不同的排列,请补充完整。

{

if(k==m) {

输出list内的所有元素; return; }

for(int i=k; i<=m; i++) {

if ( Findsame(list,k,i) )//判断第i个元素是否在list[k,i-1]中出现过

continue; Swap(list[k], list[i]); (1) ; }

}

int Findsame (int a[], int k, int m)//判断第m个元素是否在a[k,m-1]中出现过 {

for (int j=k; j<m; j++) if ( (3) ) return 1; }

(1) (2) (3)

参考解答:

(1) Permpp(list, k+1, m); (2) Swap(list[k], list[i]); (3) a[m]==a[j]

2、求二维数组的“最大子矩阵和”算法框架MaxSum2( )如下,请补充完整。

{

int sum=0,b=0;

for (int i=0;i<n;i++) {

if(b>0) b+=a[i]; else b=a[i];

if(b>sum) sum=b; }

return sum;

6

装

订

线

int MaxSum2(int m, int n, int **a) //{

求解二维整数数组的最大子矩阵和 int sum=0;

int *b=new int[n]; for(int i=0;i<m;i++) {

for(int k=0;k<n;k++) //b b[k]=0;

数组初始化 for(int j=i;j<m;j++) {

for(int k=0;k<n;k++) (4) ;

//先纵向相加到b数组中

//调用一维最大子段和

} sum = max;

}

return sum; }

(4) (5) 参考解答:

(4) b[k]+=a[j][k]; (5) MaxSum(n,b);

3、“子集和问题”是求解:n个元素的整数集合,是否能找到一个子集,使得子集元素之和为c。其回溯搜索算法框架Backtrack( )如下,请补充完整。

{

if(i>n) // {

搜索到子集树的叶子 if (cw == c) found=1; //cw else found=0; //found return;

是一个寻找标志,找到则为为当前的子集之和,foundtrue,否则为已被初始化为false false } if(found==0)

算法设计与分析 期末试卷 A卷(完整含答案)(2).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:新苏教版小学六年级 比例的基本性质下册数学教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: