2006-2007(2)算法设计与分析试题答案(软件)

2006-2007学年第二学期《计算机算法设计与分析》试题

院系：软件学院 专业：软件工程 年级：2004级

（参）

一．简答题（共10分） （5分）

二．计算题（35分）

１．(6分) 对下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=

θ(g(n))。

(1) f(n)=3n，g(n)=2n

(2) f(n)=log n + 5，g(n)=log n2

(3) f(n)=log n，g(n)=n

答：

(1) f(n) = Ω(g(n)) (2分) (2) f(n) = θ(g(n)) (2分) (3) f(n) = O(g(n)) (2分) 2．（８分）采用动态规划策略，计算a=｛5,-3,7,-4,-5,9,-2,10,-3,2｝的最大子段和，并给出这个最大子段和的起始下标和终止下标。［设数组a中的元素下标从１开始。］要求给出过程。 答：

b[1]=5；

b[2]=max{b[1]+a[2]，a[2]}=max{2,-3}=2 b[3]=max{b[2]+a[3]，a[3]}=max{9,7}=9 b[4]=max{b[3]+a[4]，a[4]}=max{5,-4}=5 b[5]=max{b[4]+a[5]，a[5]}=max{0,-5}=0 b[6]=max{b[5]+a[6]，a[6]}=max{9,9}=9 b[7]=max{b[6]+a[7]，a[7]}=max{7,-2}=7 b[8]=max{b[7]+a[8]，a[8]}=max{17,10}=17 b[9]=max{b[8]+a[9]，a[9]}=max{14,-3}=14 b[10]=max{b[9]+a[10]，a[10]}=max{16,2}=16 (上述每两行１分，共５分) 最大子段和为17（1分）

（若数组下标从１开始）起始下标：６（１分），终止下标：８（１分） （若数组下标从０开始）起始下标：５（0.5分），终止下标：7（0.5分） ３．（11分）设有３件工作分配给３个人，将工作i分配给第j个人所花的费用为Cij，现将为每一个人都分配１件不同的工作，并使总费用达到最小。设：

1

8C2323434 5要求：

（1）画出该问题的解空间树；（６分）

（2）写出该问题的剪枝策略(限界条件)；（1分）

（3）按回溯法搜索解空间树，并利用剪枝策略对应该剪掉的子树打；（２分） （4）最终给出该问题的最优值和最优解。（２分） 答：

（1）

1 2 3 2 3 1 3 1 2

1 1 2 2 3 3

3 2 3 1 2 1 16 16 9 9 9 9 ╳ ╳ ╳ ╳ （每个分枝1分，或者是每层2分，共6分） （2）当耗费大于等于当前最优值时，剪枝。（1分） （3）见上图。（每2个╳ 1分，共2分） （4）最优值： 9 （1分） 最优解：2，1，3 ４．（８分）给定两个序列X=，Y=，请采用动态规划策略求出其最长公共子序列。要求给出过程。

答：

j 0 1 2 3 4 5

i yi B D C A B 0 xi 0 0 0 0 0 0

2

1 A 0 0 0 0 1 1 2 B 0 1 1 1 1 2 3 C 0 1 1 2 2 2 4 B 0 1 1 2 2 3 5 Ａ 0 1 2 2 2 3

（上述表内每一行一分，共６分）

最长公共子序列为 （２分）

5．（2分）考虑n=3时的0-1背包问题的实例：W={15,10,10}，P={50,30,30}，c=20。当x[1]=1，x[2]=0时，请计算Bound(2)。 答：

Bound(3)=50+5/10 * 20 = 65 (2分)

三、算法填空题（共10分，每空2分）

给定n种物品和一个背包，物品i的重量是w[i], 其价值是p[i], 背包的容量为c。设物品已按单位重量价值递减的次序排序。每种物品不可以装入背包多次，但可以装入部分的物品i。求解背包问题的贪心算法如下：

float Knapsack (float x[ ], float w[ ], float p[ ],float c, int n)

{ float maxsum= ; // maxsum表示装进包的物品价值总和 for ( int i=1;i<=n; i++) x[i]=0 // x[i]=0表示第i个物品未装进包 for ( )

if( )

{ x[i] =1;

maxsum+= ; c- = w[i]; }

else break;

if (c>0) {x[i]=c/w[i]; ;} return maxsum; }

答：(共５个空，每空2分，总计10分) ０

int i=1；i<=n；ｉ++

3

w[i]<=C p[i]

maxsum+ = p[i] * c / w[i]

四、算法设计及分析题（共45分） 1．（20分）请用分治策略设计递归的二分检索算法，并分析其时间复杂性（要求给出每个阶段所花的时间，在此基础上列出递归方程，并求出其解的渐进阶）。 答：（此题解法不唯一）

算法：

int bsearch(A[],K,L,H) （1分） { if (H{ mid=(L+H) /2; (2分) if (A[mid] == K) (1分) return(mid)； (1分) else if （A[mid]>K） (2分)

return(bsearch(A,K,L, mid-1)) ; (2分)

else return(bsearch(K, mid+1,H)); (2分) }

算法时间复杂性分析：

∵ Divide阶段所花时间为O(1) (1分) Conquer阶段所花时间为T(n/2) (1分) merge阶段没有花时间（或者说，merge阶段所花时间为O(1)） (1分) ∴ 算法时间复杂性递归方程如下： T(n)=O(1) 当n≤0

T(n)= T(n/2)+O（1） 当n>1 (2分) 用套用公式法（master method）求解递归方程： ∵a=1,b=2, nlogbanlog211

logba f(n)=O(1), ∴ n

与f(n)同阶

∴ T(n)= O(log n) (2分) 2．（15分）请用回溯法设计算法，用四种颜色给地图着色（若在调用了其它算

法，也需将该算法写出）。请在每个循环语句和条件判断语句后加注释。 答：（此题解法不唯一） 算法：

boolColor::Ok(int k) { for (int j=1; jif ((a[k][j]==1)&&(x[j]==x[k]))

//判断第j点与当前点（第k点）颜色是否冲突 (2分)

4

return false; (1分)

else return true; (1分) }

void Color::Backtrack(int t) { if (t > n) // 判断是否到叶节点 (1分)

{ sum++; for (int i=1;i<=n; i++) //输出每个点的色号

cout << x[i]<< ’ ’ ;

cout << endl; （2分） } else

for (int i=1; i<=4; i++) // 依次检查当前点（第t点）是否可着第i(1≤i≤4)种颜色 (2分) { x[t]=i; (1分) if (Ok(t)) Backtrack(t+1); //若当前点（第t点）可着第i种颜色，则递归调用 (3分) } }

3．（10分）请设计一个算法，实现优先队列的出队操作。要求：

（1）指出用什么数据结构实现优先队列； （2）用C语言描述算法。 答：（此题解法不唯一）

（1）用堆实现优先队列。 （2分） （2）算法 SIFT(k,i,m) {temp = k[i]; j=2*i; (1分) while (j<=m) (1分) { if（（jif （temp.key else break; (0.5分)

R[i]=temp; (0.5分) }

Delete（n）

{ temp = R[1]; R[1]=R[i]; R[i]=temp; (1分)

SIFT(k,1,n-1); （1分）

}

5