2009-2010学年第二学期《计算机算法设计与分析》试卷A--参考答案（软07级）

2009—2010 学年第二学期《计算机算法设计与分析》试卷（A）

（院系：软件学院 专业：软件工程 年级：07级 考核形式： 开卷 ）

参考答案

一、简答题（共3小题，第1,2小题3分，第3小题4分，总计10分） 1.(3分) 请用英文写出三种以上能求解0-1背包问题的设计算法策略。 答：

Dynamic Programming Backtrack

Branch-and-Bound （每答对一条给一分）

2.(3分) 请说明动态规划方法为什么需要最优子结构性质。 答：

最优子结构性质是指大问题的最优解包含子问题的最优解。

动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构 3. (4分) 请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入算法时间复杂度？ 答：（1）堆。(1分)

（2）在小根堆中，将元素x插入到堆的末尾，

然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字， 则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。 （3）O( log n)（1分） 二、填空题 （共15个空，每空1分，总计15分）

1．递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer

阶段所花的时间是 T(n/2) ，算法的时间复杂度是 O( log n) 。 2．Prim算法利用 贪心 策略求解 最小生成树 问题，其时间复杂度是 O(n2) 。

3．背包问题可用 贪心法 ， 回溯法 等策略求解。

4．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n3) ， 子问题空间大小是 O(n2) 。

5．图的m着色问题可用 回溯 法求解，其解空间树中叶子结点个数是 mn ，解空间树中每个内结点的孩子数是 m 。

6．单源最短路径问题可用 贪心法 、 分支限界 等策略求解。

1

三、计算题（共4小题，第1,2,3小题10分，第4小题15分， 总计45分） 1．用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。 （3分）

（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出

其最长公共子序列，要求给出过程。(7分)

答：

(1)（3分）

当i?0或j?0时?0?c[i,j]??c[i?1,j?1]?1当i,j?0且xi?yi时

?max(c[i,j?1],c[i?1,j])当i,j?0且xi?yi时?(2)

Ｙ Ａ Ｂ Ｃ Ｂ

Ｘ 0 0 0 0 Ｂ 0 0 1 1 1 Ｃ 0 0 1 2 2 Ｄ 0 0 1 2 2 Ａ 0 1 1 2 2 最长公共子序列：｛ＢＣ｝ （矩阵部分5分，最长公共子序列2分，共7分。）

2．（10分）对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))

或f(n) =θ(g(n))，并简要说明理由。

(1) f(n)=2； g(n)=n! (2) f(n)=n； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3

n

n

(5) f(n)=3n； g(n)=2n 答：（每小题2分，共10分。）

(1) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。 (2) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。 (3) f(n) = θ(g(n)) 因为g(n)与f(n)同阶。

2

(4) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。 (5) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。

3．（10分）对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。

1 11 5 18 21 26 6 17 19 15 2 9 4 6 7 3 答：

TE={(3,4), (2,3),(1,5),（4,6）（4,5）} （5分）

贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。 基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。（4分）

时间复杂度为：O(eloge) （1分）

4． （15分）考虑n=3的批处理作业调度实例：

tji 作业1 作业2 作业3

其中tji是作业Ji需要在机器j上处理的时间。对于给定的3个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。 要求：

（1）画出该问题的解空间树； （5分） （2）写出该问题的剪枝策略(即限界条件)，要求只保留第一个最优解；

（2分）

（3）按优先队列式分支限界法搜索解空间树，并用剪枝策略对解空间树中该

剪枝的位置打?； （5分） （4）给出最优解及最优值。 （3分） 答：

3

机器1 1 3 2 机器2 10 1 1 （1）

V0 1 11 2 23 3 36 3 23 2 36 3 33 1 18 1 2 4 3 10 1 2 16 2 3 3 1 9 30 25 26 ※ （2）若当前代价f >= 当前最优解代价bestf，则剪枝。 （3）见（1）中所画的图。

（4）最优解为{3，1，2}，最优值为25。

四、算法题（共2小题，每小题15分，总计30分） 1．（15分）请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。 答 ： Template

void MergeSort (Type a[ ], int left, int right) （1分） { if (left

}

Divide 阶段的时间复杂性： O(1) （1分） Conquer阶段的时间复杂性： 2T(n) （1分） Combine阶段的时间复杂性： Θ(n) （1分）

θ(1)当n?1?T(n)? ? (2分)

?θ(n)当n?1?2T(n/2) 用套用公式法：a=2, b=2, nlog ba = n , f(n)=n, 因为f(n)与nlog ba 同阶，（2分） ∴T(n) =Θ(nlogn) （1分）

4

2．（15分）设n后问题的显约束条件是两个皇后不能在同一行及同一列，求解n后问题的递归的回溯算法如下。它计算可行解的个数，并将所有可行解输出。请给算法填空（包括部分循环语句和条件判断语句后面的注释）。

设x[i]的初值为i（1≤i≤n），sum的初值为0。

bool Queen :: Place(int k) {for (int j=1； j

if( abs(k-j)==abs(x[j]-x[k]) ) // 判断两个皇后是否在同一斜线 return false; return true ; }

void Queen：：Backtrack(int t) {if (t>n) // 得到一个可行解 {sum++; // 可行解个数加1 for( int i=1; i<=n; i++ ) //输出可行解 count<

else for ((int j= t ； j<=n ； j++ ) {Swap（ x[t] ， x[j] ）；

if (Place(t)) // 检查第t个皇后与前t-1个皇后是否在同一斜线 Backtrack( t+1 )； Swap（ x[t] ， x[j] ） ； } }

5