算法设计与分析考试题目与答案解析.doc

.

《算法分析与设计》期末复习题

一、 选择题
1.应用Johnson法则流水作业调度采用算法是（D）
A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法

2.Hanoi塔问题如下图所示。现规定将塔座A上所有圆盘移到塔座B上，并仍按同样次序叠置。移动圆盘时遵守Hanoi塔问题移动规则。由此设计出解Hanoi塔问题递归算确为：（B）
A. void hanoi(int n, int A, int C, int B)
{
if (n > 0)
{
hanoi(n-1,A,C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
}

Hanoi塔

B. void hanoi(int n, int A, int B, int C)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
}

C. void hanoi(int n, int C, int B, int A)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
}

D. void hanoi(int n, int C, int A, int B)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
}

3. 动态规划算法基本要素为（C）
A. 最优子构造性质与贪心选择性质
B．重叠子问题性质与贪心选择性质
C．最优子构造性质与重叠子问题性质

D. 预排序与递归调用

4. 算法分析中，记号O表达（B）， 记号表达（A）， 记号表达（D）。
A.渐进下界
B.渐进上界
C.非紧上界
D.紧渐进界
E.非紧下界

5. 如下有关渐进记号性质是对有：（A）
A.
B.
C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})

D.

6. 能采用贪心算法求最优解问题，一般具有重要性质为：（A）
A. 最优子构造性质与贪心选择性质
B．重叠子问题性质与贪心选择性质
C．最优子构造性质与重叠子问题性质

D. 预排序与递归调用

7. 回溯法在问题解空间树中，按（D）方略，从根结点出发搜索解空间树。

A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先

8. 分支限界法在问题解空间树中，按（A）方略，从根结点出发搜索解空间树。

A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先

9. 程序块（A）是回溯法中遍历排列树算法框架程序。
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
swap(x[t], x[i]);
if (legal(t)) backtrack(t+1);
swap(x[t], x[i]);
}
}

A.

void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if (legal(t)) backtrack(t+1);
}
}

B.

void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if (legal(t)) backtrack(t-1);
}
}

C.

D.void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
swap(x[t], x[i]);
if (legal(t)) backtrack(t+1);
}
}

10. 回溯法效率不依赖于如下哪一种原因？（C ）
A. 产生x[k]时间；
B. 满足显约束x[k]值个数；
C. 问题解空间形式；
D. 计算上界函数bound时间；
E. 满足约束函数和上界函数约束所有x[k]个数。
F. 计算约束函数constraint时间；

11. 常见两种分支限界法为（D）
A. 广度优先分支限界法与深度优先分支限界法；
B. 队列式（FIFO）分支限界法与堆栈式分支限界法；
C. 排列树法与子集树法；
D. 队列式（FIFO）分支限界法与优先队列式分支限界法；

12. k带图灵机空间复杂性S(n)是指（B）
A. k带图灵机处理所有长度为n输入时，在某条带上所使用过最大方格数。
B. k带图灵机处理所有长度为n输入时，在k条带上所使用过方格数总和
C. 。
C. k带图灵机处理所有长度为n输入时，在k条带上所使用过平均方格数。
D. k带图灵机处理所有长度为n输入时，在某条带上所使用过最小方格数。

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使得对所有nn0有：0 f(n) cg(n) }；
B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) }；
C. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 f(n)<cg(n) }；
D. O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 cg(n) < f(n) }；

15. 记号定义对是（B）。
A. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有：0 f(n) cg(n) }；
B. O(g(n)) = { f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) }；
C. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 f(n)<cg(n) }；
D. (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有nn0有：0 cg(n) < f(n) }；

二、 填空题
1. 下面程序段所需要计算时间为（ ）。
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} ）。
14
13
12
11
10
9
8
7
6
5
4
f[i]
12
2
8
8
6
5
3
5
0
3
1
S[i]
11
10
9
8
7
6
5
4
3
2
1
i

3. 所谓贪心选择性质是指（所求问题整体最优解可以通过一系列局部最优选择，即贪心选择来达到）。
4. 所谓最优子构造性质是指（问题最优解包含了其子问题最优解）。
5. 回溯法是指（具有限界函数深度优先生成法）。
6. 用回溯法解题一种明显特征是在搜索过程中动态产生问题解空间。在任何时刻，算法只保留从根结点到目前扩展结点途径。
假如解空间树 中从根结点到叶结点最长途径长度为h(n)，则回溯法所需计算空间一般为（O(h(n))
）。
7. 回溯法算法框架按照问题解空间一般分为（子集树）算法框架与（排列树）算法框架。
8. 用回溯法解0/1背包问题时，该问题解空间构造为（子集树）构造。
9.用回溯法解批处理作业调度问题时，该问题解空间构造为（排列树）构造。
10.用回溯法解0/1背包问题时，计算结点上界函数如下所示，请在空格中填入合适容：
Typep Knap<Typew, Typep>::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. 用回溯法解布线问题时，求最优解重要程序段如下。假如布线区域划分为方格阵列，扩展每个结点需O(1)时间，L为最短布线途径长度，则算法共耗时 ( O(mn) )，构造对应最短距离需要（O(L)）时间。
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);}
}

12. 用回溯法解图m着色问题时，使用下面函数OK检查目前扩展结点每一种儿子所对应颜色可用性，则需耗时（渐进时间上限）（O（mn））。
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;
}

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

6.
7.

三、 证明题
1. 一种分治法将规模为n问题提成k个规模为n／m子问题去解。设分解阀值n0=1，且adhoc解规模为1问题花费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题解合并为原问题解需用f(n)个单位时间。用T(n)表达该分治法解规模为|P|=n问题所需计算时间，则有：
通过迭代法求得T（n）显式体现式为：

试证明T（n）显式体现式对性。

2. 举反例证明0/1背包问题若使用算法是按照pi/wi非递减次序考虑选择物品，即只要正在被考虑物品装得进就装入背包，则此措施不一定能得到最优解（此题阐明0/1背包问题与背包问题不一样）。
证明：举例如：p={7,4,4},w={3,2,2},c=4时，由于7/3最大，若按题目规定措施，只能取第一种，收益是7。而此实例最大收益应当是8，取第2，3 个。

3.求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。
证明：对于任意f1(n) O(f(n)) ，存在正常数c1和自然数n1，使得对所有nn1，有f1(n) c1f(n) 。
类似地，对于任意g1(n) O(g(n)) ，存在正常数c2和自然数n2，使得对所有nn2，有g1(n) c2g(n) 。
令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。
则对所有 n n3，有
f1(n) +g1(n) c1f(n) + c2g(n)
c3f(n) + c3g(n)
= c3(f(n) + g(n))
c32 max{f(n),g(n)}
= 2c3h(n) = O(max{f(n),g(n)}) .

4. 求证最优装载问题具有贪心选择性质。
（最优装载问题：有一批集装箱要装上一艘载重量为c轮船。其中集装箱i重量为Wi。最优装载问题规定确定在装载体积不受限制状况下，将尽量多集装箱装上轮船。设集装箱已依其重量从小到大排序，(x1,x2,…,xn)是最优装载问题一种最优解。又设。假如给定最优装载问题有解，则有。）
证明：

四、 解答题
1. 机器调度问题。
问题描述：目前有n件任务和无限多台机器，任务可以在机器上得到处理。每件任务开始时间为si，完毕时间为fi，si<fi 。[si，fi]为处理任务i时间围。两个任务i，j重叠指两个任务时间围区间有重叠，而并非指i，j起点或终点重叠。例如：区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。一种可行任务分派是指在分派中没有两件重叠任务分派给同一台机器。因此，在可行分派中每台机器在任何时刻最多只处理一种任务。最优分派是指使用机器至少可行分派方案。
问题实例：若任务占用时间围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则准时完毕所有任务至少需要几台机器？（提醒：使用贪心算法）
画出工作在对应机器上分派状况。

2. 已知非齐次递归方程： ，其中，b、c是常数，g(n)是n某一种函数。则f(n)非递归体现式为：。
既有Hanoi塔问题递归方程为： ，求h(n)非递归体现式。
解：运用给出关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有：

3. 单源最短途径求解。
问题描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边权是非负实数。此外，还给定V中一种顶点，称为源。目前要计算从源到所有其他各顶点最短路长度。这里路长度是指路上各边权之和。这个问题一般称为单源最短途径问题。
解法：现采用Dijkstra算法计算从源顶点1到其他顶点间最短途径。请将此过程填入下表中。

4

3

2

1
100
30
maxint
10
-
{1}
初始
dist[5]
dist[4]
dist[3]
dist[2]
u
S
迭代

4. 请写出用回溯法解装载问题函数。
装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2轮船，其中集装箱i重量为wi，且。装载问题规定确定与否有一种合理装载方案可将这n个集装箱装上这2艘轮船。假如有，找出一种装载方案。
解：void backtrack (int i)
{// 搜索第i层结点
if (i > n) // 抵达叶结点
更新最优解bestx,bestw;return;
r -= w[i];
if (cw + w[i] <= c) {// 搜索左子树
x[i] = 1;
cw += w[i];
backtrack(i + 1);
cw -= w[i]; }
if (cw + r > bestw) {
x[i] = 0; // 搜索右子树
backtrack(i + 1); }
r += w[i];
}

5. 用分支限界法解装载问题时，对算法进行了某些改善，下面程序段给出了改善部分；试阐明斜线部分完毕什么功能，以及这样做原因，即采用这样方式，算法在执行上有什么不一样。

// 检查左儿子结点
Type wt = Ew + w[i]; // 左儿子结点重量
if (wt <= c) { // 可行结点
if (wt > bestw) bestw = wt;
// 加入活结点队列
if (i < n) Q.Add(wt);
}
// 检查右儿子结点
if (Ew + r > bestw && i < n)
Q.Add(Ew); // 也许含最优解
Q.Delete(Ew); // 取下一扩展结点

解答：斜线标识部分完毕功能为：提前更新bestw值；
这样做可以尽早进行对右子树剪枝。详细为：算法Maxloading初始时将bestw设置为0，直到搜索到第一种叶结点时才更新bestw。因此在算法搜索到第一种叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。
为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到最优值是所求问题子集树中所有可行结点对应重量最大值。而结点所对应得重量仅在搜索进入左子树是增长，因此，可以在算法每一次进入左子树时更新bestw值。

7. 最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y最长公共子序列。
由最长公共子序列问题最优子构造性质建立子问题最优值递归关系。用c[i][j]记录序列Xi和Yj最长公共子序列长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj最长公共子序列。故此时C[i][j]=0。其他状况下，由最优子构造性质可建立递归关系如下：
在程序中，b[i][j]记录C[i][j]值是由哪一种子问题解得到。
（1） 请填写程序中空格，以使函数LCSLength完毕计算最优值功能。
void LCSLength(int m，int n，char *x，char *y，int **c，int **b)
{
int i，j;
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]=2;}
else { c[i][j]=c[i][j-1]; b[i][j]=3; }
}
}

（2） 函数LCS实现根据b容打印出Xi和Yj最长公共子序列。请填写程序中空格，以使函数LCS完毕构造最长公共子序列功能（请将b[i][j]取值与（1）中您填写取值对应，否则视为错误）。
void LCS(int i，int j，char *x，int **b)
{
if (i ==0 || j==0) return;
if (b[i][j]== 1) {
LCS(i-1，j-1，x，b);
cout<<x[i];
}
else if (b[i][j]== 2) LCS(i-1，j，x，b);
else LCS(i，j-1，x，b);
}

8.对下面递归算法，写出调用f(4)执行成果。
void f(int k)
{ if( k>0 )
{ printf("%d\n ",k);
f(k-1);
f(k-1);
}
}

一、填空题（20分）
1.一种算法就是一种有穷规则集合，其中之规则规定了处理某一特殊类型问题一系列运算，此外，算法还应具有如下五个重要特性:_________,________,________,__________,__________。
2.算法复杂性有_____________和___________之分，衡量一种算法好坏原则是______________________。
3.某一问题可用动态规划算法求解明显特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y一种最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题解空间，问题解空间至少应包含___________。
6.动态规划算法基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________解得到原问题解。
7.以深度优先方式系统搜索问题解算法称为_____________。
8.0-1背包问题回溯算法所需计算时间为_____________,用动态规划算法所需计算时间为____________。
9.动态规划算法两个基本要素是___________和___________。 
10.二分搜索算法是运用_______________实现算法。
二、综合题（50分）
1.写出设计动态规划算法重要环节。
2.流水作业调度问题johnson算法思想。
3.若n=4，在机器M1和M2上加工作业i所需时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为30-1向量构成，规定用一棵完全二叉树表达其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
5.设S=｛X1，X2，···，Xn｝是严格递增有序集，运用二叉树结点来存储S中元素，在表达S二叉搜索树中搜索一种元素X，返回成果有两种情形，（1）在二叉搜索树结点中找到X=Xi，其概率为bi。（2）在二叉搜索树叶结点中确定X∈（Xi，Xi+1），其概率为ai。在表达S二叉搜索树T中，设存储元素Xi结点深度为Ci；叶结点（Xi，Xi+1）结点深度为di，则二叉搜索树T平均路长p为多少？假设二叉搜索树T[i][j]=｛Xi，Xi+1，···，Xj｝最优值为m[i][j]，W[i][j]= ai-1+bi+···+bj+aj，则m[i][j](1<=i<=j<=n)递归关系体现式为何？
6.描述0-1背包问题。
三、简答题（30分）
1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需时间分别为ai和bi，请写出流水作业调度问题johnson法则中对ai和bi排序算法。（函数名可写为sort(s,n)）
2.最优二叉搜索树问题动态规划算法（设函数名binarysearchtree)）
答案：
一、填空
1．确定性 有穷性 可行性 0个或多种输入 一种或多种输出
2.时间复杂性 空间复杂性 时间复杂度高下
3. 该问题具有最优子构造性质
4.{BABCD}或{CABCD}或{CADCD｝
5.一种（最优）解
6.子问题 子问题 子问题
7.回溯法
8. o(n*2n) o(min{nc,2n})
9.最优子构造 重叠子问题
10.动态规划法
二、综合题
1.①问题具有最优子构造性质；②构造最优值递归关系体现式； ③最优值算法描述；④构造最优解；
2. ①令N1={i|ai<bi}，N2={i|ai>=bi}；②将N1中作业按ai非减序排序得到N1’，将N2中作业按bi非增序排序得到N2’；③N1’中作业接N2’中作业就构成了满足Johnson法则最优调度。
3.环节为：N1={1，3}，N2={2，4}；
N1’={1，3}， N2’={4，2}；
最优值为：38
4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),
(1,1,0),(1,1,1)}。
解空间树为：
A
B
C
F
E
D
G
K
J
I
H
O
N
M
L
1
1
1
0
0
0
0
1
0
1
1
0
1
0

该问题最优值为：16 最优解为：（1，1，0）
5.二叉树T平均路长P=+
m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]} (1<=i<=j<=n,m[i][i-1]=0)
m[i][j]=0 (i>j)
6.已知一种背包容量为C，有n件物品，物品i重量为Wi，价值为Vi，求应怎样选择装入背包中物品，使得装入背包中物品总价值最大。
三、简答题
1.
void sort(flowjope s[],int n)
{
int i,k,j,l;
for(i=1;i<=n-1;i++)//-----选择排序
{
k=i;
while(k<=n&&s[k].tag!=0) k++;
if(k>n) break;//-----没有ai，跳出
else
{
for(j=k+1;j<=n;j++)
if(s[j].tag==0)
if(s[k].a>s[j].a) k=j;
swap(s[i].index,s[k].index);
swap(s[i].tag,s[k].tag);
}
}
l=i;//-----记下目前第一种bi下标
for(i=l;i<=n-1;i++)
{
k=i;
for(j=k+1;j<=n;j++)
if(s[k].b<s[j].b) k=j;
swap(s[i].index,s[k].index); //-----只移动index和tag
swap(s[i].tag,s[k].tag);
}
}
2.
void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w)
{
int i,j,k,t,l;
for(i=1;i<=n+1;i++)
{
w[i][i-1]=a[i-1];
m[i][i-1]=0;
}
for(l=0;l<=n-1;l++)//----l是下标j-i差
for(i=1;i<=n-l;i++)
{
j=i+l;
w[i][j]=w[i][j-1]+a[j]+b[j];
m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];
s[i][j]=i;
for(k=i+1;k<=j;k++)
{
t=m[i][k-1]+m[k+1][j]+w[i][j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}

一、 填空题（本题15分，每题1分）
1、 算法就是一组有穷，它们规定了处理某一特定类型问题 。
2、 在进行问题计算复杂性分析之前，首先必须建立求解问题所用计算模型。3个基本计算模型是、、。
3、 算法复杂性是度量，是评价算法优劣重要根据。
4、 计算机资源最重要是和资源。因而，算法复杂性有和之分。
5、 f(n)= 6×2n+n2，f(n)渐进性态f(n)= O(   )
6、 贪心算法总是做出在目前看来选择。也就是说贪心算法并不从整体最优考虑，它所做出选择只是在某种意义上。
7、 许多可以用贪心算法求解问题一般具有2个重要性质：性质和性质。
二、简答题（本题25分，每题5分）
1、 简单描述分治法基本思想。
2、 简述动态规划措施所运用最优化原理。
3、 何谓最优子构造性质？
4、 简单描述回溯法基本思想。
5、 何谓P、NP、NPC问题
三、算法填空（本题20分，每题5分）
1、n后问题回溯算法
(1)用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。
(2)分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表达竖列、左斜线、右斜线与否放有棋子，有则值为1,否则值为0。
for(j=0;j<N;j++)
if( 1 ) /*安全检查*/
{ A[i][j]=i+1; /*放皇后*/
2 ；
if(i==N-1) 输出成果；
else 3 ；; /*试探下一行*/
4 ； /*去皇后*/
5 ；;
}
2、数塔问题。有形如下图所示数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走究竟层，规定找出一条途径，使途径上值最大。
for(r=n-2;r>=0;r--) //自底向上递归计算
for(c=0; 1 ;c++)
if( t[r+1][c]>t[r+1][c+1]) 2 ；
else 3 ；
3、Hanoi算法
Hanoi(n,a,b,c)
if （n==1） 1 ；
else
{ 2 ；
3 ；
Hanoi(n-1,b, a, c);
}
4、Dijkstra算法求单源最短途径
d[u]:s到u距离 p[u]:记录前一节点信息
Init-single-source(G,s)
for each vertex v∈V[G]
do { d[v]=∞; 1 }
d[s]=0
Relax(u,v,w)
if d[v]>d[u]+w(u,v)
then { d[v]=d[u]+w[u,v];
2
}
dijkstra(G,w,s)
1. Init-single-source(G,s)
2. S=Φ
3. Q=V[G]
4.while Q<> Φ
do u=min(Q)
S=S∪{u}
for each vertex 3
do 4
四、算法理解题（本题10分）
根据优先队列式分支限界法，求下图中从v1点到v9点单源最短途径，请画出求得最优解解空间树。规定中间被舍弃结点用×标识，获得中间解结点用单圆圈○框起，最优解用双圆圈◎框起。
五、算法理解题（本题5分）
设有n=2k个运动员要进行循环赛，现设计一种满足如下规定比赛日程表：
①每个选手必须与其他n-1名选手比赛各一次；
②每个选手一天至多只能赛一次；
③循环赛要在最短时间完毕。
（1）假如n=2k，循环赛至少需要进行几天；
（2）当n=23=8时，请画出循环赛日程表。
六、算法设计题（本题15分）
分别用贪心算法、动态规划法、回溯法设计0-1背包问题。规定：阐明所使用算法方略；写出算法实现重要环节；分析算法时间。
七、算法设计题（本题10分）
通过键盘输入一种高精度正整数n(n有效位数≤240)，去掉其中任意s个数字后，剩余数字按原左右次序将构成一种新正整数。编程对给定n 和s，寻找一种方案，使得剩余数字构成新数最小。
【样例输入】
178543
S=4
【样例输出】
13

一、填空题（本题15分，每题1