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

华南农业大学期末考试试卷（A卷）

2012学年第1学期 考试科目： 算法设计与分析 考试类型：（闭卷）考试 考试时间： 120 分钟

学号 姓名 年级专业

题号

装

一(20)

二(25)

三(16)

四(24)

五(15)

总分

得分 评阅人

订

说明：

（1）请勿漏填学号姓名等信息。本试卷仅一份，请将答案直接填于试卷上，莫将试卷当草稿，想好了再写，若空白的位置不够，标注清楚后可以写反面；

（2）答题时，对算法的描述可以采用文字、公式、图、伪代码、实例说明等混合形式。请注意表达应条理清晰，思想简洁，勿长篇累述不得要领。

得分

线

一、填空题（1~3题每空1分，第4题每空2分，共20分，结果直接填于划线处） 1、化简下面f(n)函数的渐进上界表达式。（5分） f1(n) n2/2 3n， 则O(f1(n)) O(_____________) f2(n) 2n 3，

f3(n) logn3，

则O(f2(n)) O(_____________) 则O(f3(n)) O(_____________) 则O(f4(n)) O(_____________) 则O(f5(n)) O(_____________)

n

f4(n) 2logn，

f5(n) log3n，

2

参考解答：O(f1(n)) O(3)；O(f2(n

)) O(2n)；O(f

3(n)) O(logn)；

O(f4(n)) O(n2)；O(f5(n)) O(n)。

2、用大O符号和关于n的渐进函数来表征如下算法Loop1至Loop3的运行时间。（3分）

算法1：)；

算法2：；

1

算法3：参考解答：算法1：O(n2)；算法2：O(n3)；算法3：O(n4)。

3、假设算法A的计算时间为T(n) 2n，现在一慢一快的两台计算机上测试算法A，为解决规模n的问题慢机运行算法A花费t秒，而另一台快机速度是慢机的256倍，则在快机上算法A同样运行t秒能解决n1规模，则n1和n的关系为：B的计算时间为T(n) n2，其余条件不变，则。（2分）

参考解答：对算法A，n1

n 8；对算法B，n1 16n。

4、求最大的i个数问题：给定n个不同数的集合S和正整数i（i<=n），S中元素无序，求S中最大的i个数且有序输出（按照升序或降序皆可）。有下述多种算法：（10分）

（1）算法A：调用i次顺序比较查找最大元素的算法findmax，每调用一次删除此最大的数。 （2）算法B：对S排序，并输出S中最大的i个数。

（3）算法C：对输入集合S中的n个数建立一个长度为n的最大堆，接着反复调用i次堆的extract_Max过程。其中extract_Max过程为堆顶元素删除操作，该过程时间代价为O(logn)，而建立一个n个元素的最大堆过程需要O(n)。

（4）算法D：利用O(n)线性时间的分治算法找第i大元素x，然后调用partition过程对n个数以x进行划分，比x大的i-1个元素被置于x的右边（即后边），再对这i个数进行排序。 （5）算法E：先对集合S的前i个元素建立一个长度为i的最小堆，利用extract_Min过程可得最小堆的堆顶元素为x，让集合S的后续n-i个元素（称当前元素y）逐个去和堆顶元素x比较，若y>x，将y插入堆中并重新整合成最小堆和形成新的堆顶元素x；否则丢弃y。当后续n-i个元素全部比较完毕，则最小堆中的i个元素即为原序列n个数中最大的i个数，最后对这堆中的i个数调用i次extract_Min过程即可有序输出。

请分析A、B、C、D和E这五个算法在最坏情况下的渐进时间复杂性（用n和i表示，但需化简，即忽略系数且略去低阶项）。

算法A：TA(n) O(_______________)； 算法B：TB(n) O(_______________)； 算法C：TC(n) O(______________)； 算法E：TE(n) O(______________)。

参考解答：算法A：

算法D：TD(n) O(_______________)；

TA(n) O(i n)； TB(n) O(nlogn i)或TB(n) O(nlogn)

TC(n) O(n ilogn)，其中建立堆需要O(n)，i次堆顶元素删除O(ilogn)。

2

装

订

线

TD(n) O(n ilogi)，其中找第i大元素需要O(n)，对i个元素排序需要O(ilogi)。

TE(n) O(i (n i)logi ilogi)或TE(n) O(nlogi)，其中建立长度为i的最小堆需要O(i)，

后续n-i个元素比较并判定是否逐个插入堆，最坏情况为O((n i)logi)，最后对i个堆中元素逐个输出堆顶元素需要O(ilogi)，合计后略去低阶项为O(nlogi)。

得分

二、简答题（共5小题，每题5分，共25分） 1、请将下列函数的阶按上升顺序排列。（5分）

n1/2，logn2，2n，log2n，nlogn，n2logn，210，2logn，22n

，2n2

参考解答：2

10

，logn2，log2n，n

1/2

，2

logn

，nlogn，n2logn，2n

，2n2，22n

提示：拿不准两个函数f(n)和g(n)时，考虑logf(n)和logg(n)，或2^f(n)或2^g(n)。学生答题的排序后若有一个不在位，扣1分。

2、复数a+bi可以用数对(a, b)表示（其中i2 1）。描述一个方法，只需构造进行三次实数

乘法（可采用有限次实数加减），即可计算a+bi和c+di相乘的结果数对(e, f)。请写出采用了哪三次实数乘法？（5分）

参考解答：

(a,b)(c,d) ac (ad bc)i bd( 1) ac [(a b)(d c) ac bd]i bd

三次实数乘法分别是：ac,

(a b)(d c),bd

评分准则：此参考解答并非唯一解，只要能凑出ac, bd, (ad+bc)三部分的解皆可。

3、对于矩阵连乘所需最少数乘次数问题，其递推关系式为：

m[i,j]

0i j

min{i k jm[i,k] m[k 1,j] pi 1pkpj}i j

其中m[i，j]为计算矩阵连乘Ai…Aj所需的最少数乘次数，pi 1为矩阵Ai的行数，pi为矩阵Ai的列数。现有四个矩阵，其中各矩阵维数分别为：

A1 A2 A3 A4 10 100 100 5

5 50

50 10

p 0 p 1

p 1 p 2 p 2 p 3p 3 p 4请根据递推关系，计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数。（5分）

参考解答：根据递推公式：

m[1][1] 0;m[2][2] 0;m[3][3] 0;m[4][4] 0;

m[1][2] p0p1p2 5000;m[2][3] p1p2p3 25000;m[3][4] p2p3p4 2500;

3

m[1][3] min{m[1][1] m[2][3] p0p1p3,m[1][2] m[3][3] p0p2p3} 7500;m[2][4] min{m[2][2] m[3][4] p1p2p4,m[2][3] m[4][4] p1p3p4} 5000;

m[1][1] m[2][4] p0p1p4 0 5000 10000 15000

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)

{

// x[i] = 1; 无条件左子树 cw += a[i];

Backtrack(i+1);

(6) ; // x[i] = 0;

搜索完左子树，无条件右子树 } (7) ;

}

(6) (7) 参考解答：

(6) cw -= a[i]; (7) Backtrack(i+1);

4、“n皇后问题”是求解：n×n的棋盘上放置n个不同行不同列不同斜线的皇后，是否有放置方案，有请输出可行的放置方案数。其算法框架nQueen( )如下，请补充完整。

{

……

//假定n,sum,x[]数组等都为全局变量，并在nQueen中初始化；

7

}

void Backtrack(int t) //完全n叉树的搜索算法，根节点t=1 {

if(t>n) //搜索到n叉树的叶子 {

sum++; //sum为可行放置方案个数的统计变量

…… //并输出x[]解向量,此处略

} else {

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

x[t] = i;

if( Place(t) )

Backtrack(t+1); } } }

int Place(int k) {

for(int j=1;j<k;j++)

if( (8) || (9) ) return 0; //可使用abs()库函数求绝对值 }

for(int i=1; i<=n; i++) x[i]=0; Backtrack(1); return sum;

(8) (9)

参考解答：

(8) abs(k-j)==abs(x[k]-x[j]) (9) x[j]==x[k]

5、大于1的正整数 n 都可以分解为 n = x1×x2×...×xm，对于给定正整数n，计算n共有多少种不同的分解式的solve( )过程如下。例如：当n=12时，共有8种不同的分解式： 12 = 12； 12 = 6*2； 12 = 4*3； 12 = 3*4；12 = 3*2*2；12 = 2*6； 12 = 2*3*2； 12 = 2*2*3

void solve(int n) //递归实现对n的不同分解式的个数统计 {

if (n==1) total++;

else for (int i=2; i<=n; i++)

if (n%i == 0) (10) ; }

(10)

参考解答：

(10) solve(n/i); 或if (n==1) total=1; else … total=solve(i)*solve(n/i);

6、二维0-1背包问题：n种物品，每种物品仅1件，物品i的重量wi，体积bi，价值vi，背包容量为c，容积为d。所有参数均为正整数，如何选择装入背包的物品子集，使得装入背包物品的总价值最大？其动态规划算法Knapsack2( )算法如下，其中m[i][x][y]含义：每种物品仅1件，但可选物品1…i，背包容量为x容积为y（1≤i≤n，0≤x≤c，0≤y≤d），可获得装入物品的最大价值和存于m[i][x][y]中。

//全局变量有n, w[], b[], v[]；含义如题说明。 //全局变量有m[][][]数组；含义如题说明。 ……

8

int Knapsack2() //动态规划法计算二维背包问题，填充m数组 {

int i,x,y;

for(x=0;x<=c;x++) //初始化m[1][x][y] { for(y=0;y<=d;y++) {

if(x>=w[1] && y>=b[1]) m[1][x][y]=v[1]; else m[1][x][y]=0; }

}

for(i=2;i<=n;i++) //递推填充m[i][x][y],2<=i<=n { for(x=0;x<=c;x++) { for(y=0;y<=d;y++) { if(x>=w[i] && y>=b[i] && m[i-1][x][y]<m[i-1][x-w[i]][y-b[i]]+v[i]) m[i][x][y] = (11) ; else

m[i][x][y] = (12) ; } } }

return m[n][c][d]; }

装

订

线

(11) (12) 参考解答：

(11) m[i][x][y] = m[i-1][ x-w[i] ][ y-b[i] ] + v[i]; (12) m[i][x][y] = m[i-1][x][y];

得分

五、算法设计题（共2小题，共15分）

此大题请写出算法设计的详细步骤，可用伪代码、文字、图表来描述。 1、【区间相交问题】（7分）

给定数轴上n个区间。去掉尽可能少的区间，使剩下的区间都不相交。请给出删除区间的方案。（这里：两区间仅边界有交点不算相交）

参考解答：区间相交问题基本等同于活动安排问题。 1）、将区间按照区间后端点排序（从小到大）。 2）、选择第一个区间

3）、依次扫描后续区间，和第一个不相交的，拉入相容区间集合 4）、总区间数减去相容区间集合得到的就是最少的需要去掉的区间数

评分准则： 1) 2) 3)

答到贪心算法，且贪心算法表述正确，本题即可得满分； 说明用到贪心算法，但表述不正确或含糊，扣2分以上；

未提及贪心算法，但有解题思路，若错误，扣一大半分数，若正确，扣一半，因为贪心算法在这个问题中求解的效率最高；

9

其它情况酌情考虑。

2、【最长上升子序列问题】（8分）

对于给定的一个序列(a1,a2,...,aN),1 N 10000。我们可以得到一些递增上升的子序列。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。你的任务：对于给定的序列，求出最长上升子序列的长度。要求写出算法思想和递推公式，并分析算法时间复杂度。

参考解答：设f(i)表示：从左向右扫描过来直到以a[i]元素结尾的序列，获得的最长上升子序列的长度，且子序列包含a[i]元素（1≤i≤n）。

1i 1

f(i) max{f(j) 1:当a[i] a[j];1 j i}i 1

1i 1; j(1 j i),都有a[i] a[j]

即，f(i)是从f(1), f(2),…f(i-1)中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。

最后，所要求的整个序列的最长公共子序列长度为max{f(i): 1<=i<=n} 例如，对于序列：4 2 6 3 1 5 2

i array f(i)

评分准则： 1) 2)

答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边界设定清晰，本题即可得满分；（阅卷时仔细看递推公式表达，公式表达含义正确即可，因其表达形式可能不唯一） 说明使用动态规划算法，但对递推函数表达错误或含糊，扣2分以上； 其它情况酌情考虑。

1 4 1

2 2 1

3 6 2

4 3 2

5 1 1

6 5 3

7 2 2

10

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