《算法设计与分析》考试题目及答案解析

13. NP类语言在图灵机下的定义为（D）

A. NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}； B. NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}； C. NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}； D. NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；

14. 记号O的定义正确的是（A）。

A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? f(n) ?

cg(n) }；

B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? cg(n) ?

f(n) }；

C. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0

有：0 ?f(n)

D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有

n?n0有：0 ?cg(n) < f(n) }；

15. 记号?的定义正确的是（B）。

A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? f(n) ?

cg(n) }；

B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n?n0有：0? cg(n) ?

f(n) }；

C. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0

有：0 ?f(n)

D. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n?n0

有：0 ?cg(n) < f(n) }；

二、

填空题

21. 下面程序段的所需要的计算时间为（ O(n ) ）。

int MaxSum(int n, int *a, int &besti, int &bestj) { int sum=0; for(int i=1;i<=n;i++){ int thissum=0; for(int j=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } return sum; } 2. 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果

以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活

动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ {1，4，8，11} ）。

3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最

优的选择，即贪心选择来达到）。

4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。 5. 回溯法是指（具有限界函数的深度优先生成法）。

6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。

7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。

8. 用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。 9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。

10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：

i S[i] f[i]

1 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 2 13

11 12 14

Typep Knap::Bound(int i) {// 计算上界 Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 结点的上界 // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; } // 装满背包 if (i <= n) （b += p[i]/w[i] * cleft）; return b; }

11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为

n?m的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则

算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。 12. 用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn））。

13. 旅行售货员问题的解空间树是（排列树）。

Bool Color::OK(int k) {// for(int j=1;j<=n;j++) if((a[k][j]= =1)&&(x[j]= =x[k])) return false; return true; } for (int i = 0; i < NumOfNbrs; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) { // 该方格未标记 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布线 Q.Add(nbr);} }