算法分析期末试题集答案


算法分析设计期末复题()

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

2Hanoi塔问题图示现求塔座A圆盘移塔座B样序叠置移动圆盘时遵守Hanoi塔问题移动规设计出解Hanoi塔问题递算法正确：（B）
A void hanoi(int n int A int C int B)
{
if (n > 0)
{
hanoi(n1AC B)
move(nab)
hanoi(n1 C B A)
}
}


Hanoi塔




B void hanoi(int n int A int B int C)
{
if (n > 0)
{
hanoi(n1 A C B)
move(nab)
hanoi(n1 C B A)
}
}







C void hanoi(int n int C int B int A)
{
if (n > 0)
{
hanoi(n1 A C B)
move(nab)
hanoi(n1 C B A)
}
}






D void hanoi(int n int C int A int B)
{
if (n > 0)
{
hanoi(n1 A C B)
move(nab)
hanoi(n1 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 iti 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 i0i<1i++) {
x[t]i
if (legal(t)) backtrack(t+1)
}
}

B






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

C




Dvoid backtrack (int t)
{
if (t>n) output(x)
else
for (int iti 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) | 存正常数cn0nn0：0 f(n) cg(n) }
B O(g(n)) { f(n) | 存正常数cn0nn0：0 cg(n) f(n) }
C O(g(n)) { f(n) | 正常数c>0存正数n0 >0nn0：0 f(n)D O(g(n)) { f(n) | 正常数c>0存正数n0 >0nn0：0 cg(n) < f(n) }





15 记号定义正确（B）
A O(g(n)) { f(n) | 存正常数cn0nn0：0 f(n) cg(n) }
B O(g(n)) { f(n) | 存正常数cn0nn0：0 cg(n) f(n) }
C (g(n)) { f(n) | 正常数c>0存正数n0 >0nn0：0 f(n)D (g(n)) { f(n) | 正常数c>0存正数n0 >0nn0：0 cg(n) < f(n) }


二 填空题
1 面程序段需计算时间（ ）
int MaxSum(int n int *a int &besti int &bestj)
{
int sum0
for(int i1i int thissum0
for(int jij thissum+a[j]
if(thissum>sum) {
sumthissum
bestii
bestjj
}
}
}
return sum
}


















2 11安排活动具表示开始时间结束时间果贪心算法求解活动优安排（活动安排问题：活动集合中选出相容活动子集合）相容活动子集合活动（ {14811} ）
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 回溯法解01背包问题时该问题解空间结构（子集树）结构
9回溯法解批处理作业调度问题时该问题解空间结构（排列树）结构
10回溯法解01背包问题时计算结点界函数示请空格中填入合适容：
Typep KnapBound(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++) {
nbrrow hererow + offset[i]row
nbrcol herecol + offset[i]col
if (grid[nbrrow][nbrcol] 0) {
该方格未标记
grid[nbrrow][nbrcol]
grid[hererow][herecol] + 1
if ((nbrrow finishrow) &&
(nbrcol finishcol)) break 完成布线
QAdd(nbr)}
}












12 回溯法解图m着色问题时面函数OK检查前扩展结点子相应颜色性需耗时（渐进时间限）（O（mn））
Bool ColorOK(int k)
{
for(int j1jif((a[k][j] 1)&&(x[j] x[k])) return false
return true
}







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

6
7




三 解答题
1 机器调度问题
问题描述：现n件务限台机器务机器处理件务开始时间si完成时间fisi问题实例：务占时间范围{[14][25][45][26][47]}时完成务少需台机器？（提示：贪心算法）
画出工作应机器分配情况

2 已知非齐次递方程： 中bc常数g(n)n某函数f(n)非递表达式：
现Hanoi塔问题递方程： 求h(n)非递表达式
解：利出关系式时：b2 c1 g(n)1 n递推1：


3 单源短路径求解
问题描述：定带权图（图示）G (VE)中条边权非负实数外定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艘载重量分c1c2轮船中集装箱i重量wi装载问题求确定否合理装载方案n集装箱装2艘轮船果找出种装载方案
解：void backtrack (int i)
{ 搜索第i层结点
if (i > n) 达叶结点
更新优解bestxbestwreturn
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) QAdd(wt)
}
检查右子结点
if (Ew + r > bestw && i < n)
QAdd(Ew) 含优解
QDelete(Ew) 取扩展结点












解答：斜线标识部分完成功：提前更新bestw值
样做早进行右子树剪枝具体：算法Maxloading初始时bestw设置0直搜索第叶结点时更新bestw算法搜索第叶子结点前总bestw0r>0 Ew+r>bestw总成立说时右子树测试起作
述右子树测试早生效应提早更新bestw知算法终找优值求问题子集树中行结点相应重量值结点相应重量仅搜索进入左子树增加算法次进入左子树时更新bestw值


7 长公子序列问题：定2序列X{x1x2…xm}Y{y1y2…yn}找出XY长公子序列
长公子序列问题优子结构性质建立子问题优值递关系c[i][j]记录序列XiYj长公子序列长度中 Xi{x1x2…xi}Yj{y1y2…yj}i0j0时空序列XiYj长公子序列时C[i][j]0情况优子结构性质建立递关系：
程序中b[i][j]记录C[i][j]值子问题解
（1） 请填写程序中空格函数LCSLength完成计算优值功
void LCSLength(int mint nchar *xchar *yint **cint **b)
{
int ij
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[i1][j1]+1 b[i][j]1}
else if (c[i1][j]>c[i][j1]) {
c[i][j]c[i1][j] b[i][j]2}
else { c[i][j]c[i][j1] b[i][j]3 }
}
}















（2） 函数LCS实现根b容印出XiYj长公子序列请填写程序中空格函数LCS完成构造长公子序列功（请b[i][j]取值（1）中您填写取值应否视错误）



void LCS(int iint jchar *xint **b)
{
if (i 0 || j0) return
if (b[i][j] 1) {
LCS(i1j1xb)
cout< }
else if (b[i][j] 2) LCS(i1jxb)
else LCS(ij1xb)
}










8面递算法写出调f(4)执行结果
void f(int k)
{ if( k>0 )
{ printf(d＼n k)
f(k1)
f(k1)
}
}













算法分析设计期末复题(二)
简回答列问题 ：
1 算法重特性什？
2 算法分析目什？
3 算法时间复杂性问题什素相关？
4 算法渐进时间复杂性含义？
5 坏情况时间复杂性均时间复杂性什？
6 简述二分检索（折半查找）算法基程
7 背包问题目标函数贪心算法优化量度相？
8 采回溯法求解问题解表示？什规定？
9 回溯法搜索特点什？
10 n皇问题回溯算法判函数place基流程什？
11 什分治法设计算法般递调？
12 什分析坏情况算法时间复杂性？
13 简述渐进时间复杂性界定义
14 二分检索算法较次数？
15 快速排序算法坏情况需少次较运算？
16 贪心算法基思想？
17 回溯法解（x1x2……xn）隐约束般指什？
18 阐述排序分治思路
19 快速排序基思想什
20 什直接递间接递？消递般什数结构？
21 什哈密顿环问题？
22 回溯法求解哈密顿环定义判定函数？
23 请写出prim算法基思想
参考答案：1 确定性实现性输入输出穷性
2 分析算法占计算机资源情况算法做出较评价设计出额更算法
3 算法时间复杂性问题规模相关问题n函数
4．问题规模n趋穷时影响算法效率重素T(n)数量级素仅时间复杂度相差常数倍T(n)数量级(阶)评价算法时间复杂度T(n)数量级(阶)称渐进时间复杂性
5 坏情况时间复杂性均时间复杂性考察n固定时输入实例算法耗时间坏情况时间复杂性取输入实例中时间复杂度：
W(n) max{ T(nI) } I∈Dn
均时间复杂性输入实例处理时间概率积：
A(n) ∑P(I)T(nI) I∈Dn
6 设输入非降次序排列元素表A[i：j] x选取A[(i+j)2]x较果A[(i+j)2]x返回(i+j)2果A[(i+j)2]回溯法搜索特点什
7 相目标函数：获利润优量度：利润重量
8 问题解表示n元组：（x1x2……xn）xi∈Si Si穷集合xi∈Si （x1x2……xn）具备完备性（x1x2……xn）合理（x1x2……xi）(i9 解空间树跳跃式深度优先搜索判定函数考察x[k]取值果x[k]合理搜索x[k]根节点子树果x[k]取完值便回溯x[k1]
10 第K行皇分前k1行皇较否相容果相容返回false测试完毕返回true
11 子问题规模时必须继续分治法反复分治必然递
12 坏情况时间复杂性决定算法优劣坏情况时间复杂性较均时间复杂性游操作性
13 T(n)某算法时间复杂性函数f(n)简单函数存正整数NoCn〉NoT(n)14 二分检索算法较次数 log n
15．坏情况快速排序退化成泡排序需较n2次
16 种优化量度次选择输入分级处理方法基思路：首先根题意选取种量度标准然种量度标准n输入排序次选择输入量加入部分解中果前输入量加入满足约束条件输入加部分解中
17．回溯法解（x1x2……xn）隐约束般指元素间应满足某种关系
18 讲数组分二分集合单独排序然已排序两序列成含n元素分类序列果分割子问题继续分治直元素
19快速排序基思想排序N记录中意取记录该记录放终位置数序列记录分成两部分关键字该记录关键字放前部分放置部分该记录排两部分中间程称作次快速排序重复述程直部分记录止
20定义程者函数时候出现调程者函数成分调身称直接递果程者函数P调程者函数QQ调P称间接递消递般栈种数结构
21哈密顿环指条着图GN条边环行路径访问节点次返回开始位置
22前选择节点X[k]未节点X[k]≠X[i](i12…k1)C(X[k1] X[k])≠∞果k1C(X[k] X[1]) ≠∞
23 思路：初生成树T空次加入树邻接边n1条边处理程：首先加入代价条边T根节点T邻接边排序选择边加入新边加入修改新边改变邻接边排序选择条边加入直加入n1条边

二复杂性分析
1 MERGESORT(lowhigh)
if low then mid←(lowhigh)2
MERGESORT(lowmid)
MERGESORT(mid+1high)
MERGE(lowmidhigh)
endif
end MERGESORT
答 1 递方程



设n2k
解递方程：

2 procedure S1(PWMXn)
i←1 a←0
while i≤ n do
if W(i)>M then return endif
a←a+i
i←i+1
repeat
end
解： i←1 s←0 时间：O(1)
while i≤ n do 循环n次
循环体时间 O(1)
总时间
T(n)O(1)+ nO(1) O(n)

3procedure PARTITION(mp)
Integer mpiglobal A(mp1)
v←A(m)i←m
loop
loop i←i+1 until A(i) ≥v repeat
loop p←p1 until A(p) ≤v repeat
if i then call INTERCHANGE(A(i)A(p))
else exit
endif
repeat
A(m) ←A(p)A(p) ←v
End PARTITION
解：查找次数pm+1次

4procedure F1(n)
if n<2 then return(1)
else return(F2(2n11))
endif
end F1
procedure F2(inxy)
if i≤n
then call F2(i+1nyx+y)
endif
return(y)
end F2
解：F2（2n11）时间复杂度：
T(n)O(n2) i≤n时递调F2n2次
n＝1时F1(n)时间 O(1)
n>1时F1(n)时间复杂度F2(2n11)时间复杂度相 O(n)

5procedure MAX(Anj)
xmax←A(1)j←1
for i←2 to n do
if A(i)>xmax then xmax←A(i) j←iendif
repeat
end MAX
解：xmax←A(1)j←1 时间：O(1)
for i←2 to n do 循环n1次
总时间
T(n)O(1)+ (n1)O(1) O(n)

6procedure BINSRCH(Anxj)
integer lowhighmidjn
low←1high←n
while low≤high do
mid←|_(low+high)2_|
case
xx>A(mid)low←mid+1
elsej←mid return
endcase
repeat
j←0
end BINSRCH
解：log2n+1
三算法理解
1写出段图短路动态规划算法求解列实例程求出优值


5
2



8
6
3
1



7
4


边代价：
C(12)3 C(13)5 C(14)2
C(26)8 C(27)4 C(35)5 C(36)4 C(45)2C(46)1
C(58)4 C(68)5 C(78)6
解：Cost(48)0
Cost(37) C(78)+06 D[5]8
Cost(36) C(68)+05 D[6]8
Cost(35) C(58)+04 D[7]8

Cost(24) min{C(46)+ Cost(36) C(45)+ Cost(35)}
min{1+ 5 2+4}6 D[4]6
Cost(23) min{C(36)+ Cost(36) }
min{4+5}9 D[3]5
Cost(22) min{C(26)+ Cost(36) C(27)+ Cost(37)}
min{8+5 4+6}10 D[2]7

Cost(11) min{C(12)+ Cost(22) C(13)+ Cost(23) C(14)+ Cost(24)}
min{3+10 5+92+6} 8
D[1]4
1→4→6→8

2 写出maxmin算法列实例中找数数程
数组 A(4812613519327)
解：写出maxmin算法列实例中找数数程
数组 A()
1 4812613 519327
24812 613 519 327
3 48～61 12～3 19～325～7
4 61～32 3～5
5 61 3

3 快速排序算法列实例排序算法执行程中写出数组A第次分割程
A(657075808555502)
解：第分割元素65
(1) (2) (3) (4) (5) (6) (7) (8) i p
65 70 75 80 85 55 50 2 2 8
65 2 75 80 85 55 50 70 3 7
65 2 50 80 85 55 75 70 4 6
65 2 50 55 85 80 75 70 4 6
55 70 75 80 85 65 50 2










4 排序算法列实例排序写出算法执行程
A(4812613519327)
解： 4812613 519327
4812 613 519 327
1248 361 519 732
3 12 48 61 5 7 1932
35 71219324861

5 写出图着色问题回溯算法判断X[k]否合理程
解：i←0
while i if G[ki]1 and X[k] X[i] then
return false
i←i+1
repeat
if i k then return true

6 图写出图着色算法出种着色方案程
2



3

1



4


解：K←1
X[1] ←1 返回 true
X[2]←1返回false X[2]←X[2]+12 返回 true
X[3]←1 返回false X[3]←X[3]+12 返回falseX[3]←X[3]+13 返回 true
X[4]←1 返回false X[4]←X[4]+12 返回falseX[4]←X[4]+13 返回 true
找解 （1233）

7 写出第7题状态空间树
解：
X[1]1


X[2]2


X[3]33



X[4]33




8写出排序算法列实例排序程
(62935187)
解：调第层次 6293 5187 分成两子问题
调第二层次 62 93 51 87 分成四子问题
调第三层次 6 2 9 3 5 1 8 7 分成八子问题
调第四层次 元素返回层
第三层 2 6 3 9 15 78 返回层
第二层 2 36 9 1578 返回层
第层 1 2 3 5 6 7 89 排序结束返回函数

9写出背包问题贪心算法解决列实例程
P(181241)
W(121083)
M25
解 实例符合P(i)W(i)≥P(i+1)W(i+1)序
CU←25X←0
W[1]< CU x[1]←1 CU←CUW[1]13
W[2]< CU x[2]←1 CU←CUW[2]3
W[3]>CU x[3]←CU W[3]38
实例解：（11380）


11序表{139123241456275778295100}二分查找值82结点时少次较查找成功出程
解：序表{139123241456275778295100}二分查找值82结点时少次较查找成功出程
执行四次找值82数

12prim算法构造出图G棵生成树

1
2
4
3
5
6

dist(12)6dist(25)3dist(56)6dist(64)2dist(41)5
dist(13)1dist(23)5dist(34)5dist(36)4dist(53)6
解：普里姆算法构造出图G棵生成树

1
2
4
3
5
6

dist(12)6dist(25)3dist(56)6dist(64)2dist(41)5
dist(13)1dist(23)5dist(34)5dist(36)4dist(53)6

1
3
1
6
1
3
6
4
1
2
6
4
5
1
2
6
3
4
3
3


13函数说明
int f(int xint y)
{
fx Mod y +1
}
已知a10b4c5 执行kf(f(a+cb)f(bc))k值少写出详细程
解：函数说明
int f(int xint y)
{
fx Mod y +1
}
已知a10b4c5 执行kf(f(a+cb)f(bc))k值少写出详细程

}
K值5

14McCathy函数定义：
x>100时 m(x)x10
x<100时 m(x)m(m(x+11))
编写递函数计算定xm(x)值
解：McCathy函数定义：
x>100时 m(x)x10
x<100时 m(x)m(m(x+11))
编写递函数计算定xm(x)值
int m(int x)
{
int y
if(x>100) return(x100)
else
{
ym(x+11)
return (m(y))
}
}
15 设计算法量A中找出数数元素
解：设计算法量A中找出数数元素
Void maxmin(An)
Vector A
int n
{
int maxmini
maxA[1]minA[1]
for(i2iif(A[i]>max)maxA[i]
else if(A[i]printf(maxdmind＼nmaxmin)
}
四设计算法
1 设n项独立作业{12… n}m台相机器加工处理作业i需处理时间ti约定：项作业台机器处理未完工前准中断处理作业拆分更子作业
机调度问题求出种调度方案n作业短时间m台机器处理完设计算法讨否获优解
解：处理机jS[j] 表示处理机j已作业数P[jk]表示处理机j第k作业序号
1）作业t[1]≥t[2]≥……≥t[n]排序
2）S[1m]清零 j←0 第处理机开始安排
3) for i←1 to n do 安排n作业
j←j mod m +1 选处理机
S[j]←S[j]+1
P[jS[j]]←i
Repeat

2 设n种面值
d1≥d2≥……≥dn钱币需找零钱M选择钱币dk数目Xk满足
d1×Xi＋……dn×XnM
Xi＋……Xn
请选择贪心策略设计贪心算法
解：贪心原：次选择面值硬币
CU←Mi←1X←0 X解量
While CU≠0 do
X[i]←CU div d[i] X[i]第i中硬币数
CU←CUd[i]*X[i]
i←i+1
repeat

3 n物品已知n7 利润P(1051576183)重量W(2357141)背包容积M15物品选择全部装入背包装入背包设计贪心算法讨否获优解
解：定义结构体数组G物品编号利润重量作结构体：例G[k]{1102}
求优解利润重量递减序
{5616} {11025}{618492} {31553} {7313}{25353} {4771}
算法
procedure KNAPSACK(PWMXn)
P(1：n)W(1n)分含
P(i)W(i)≥P(i+1)W(i+1)排序n件物品效益值
重量M背包容量x(1：n)解量
real P(1：n)W(1：n)X(1：n)Mcu
integer in
X←0 解量初始化零
cu←M cu背包剩余容量
for i←1 to n do
if W(i)>cu then exit endif
X(i) ←1
cu←cuW(i)
repeat
end GREEDYKNAPSACK
根算法出解：
X（1111100）获利润52 解
（1111 0 10）获利润54
贪心法定获优解

4 设计求哈密顿环回溯算法
解：Hamiltonian(n)
{k←1 x[k] ←0
While k>0 do
x[k] ← x[k]+1
while B(k)false and x[k]≤n do
x[k] ← x[k]+1 repeat
If x[k]≤n then
if kn then {print x return}
else {k← k+1 x[k]←0} endif
else k← k1
endif
repeat
end
procedure B(k)
{ G[x[k1]x[k] ]≠1 then return false
for i←1 to k1 do
if x[i]x[k] then return falseendif
repeat
return true
}

5．利称性设计算法求n偶数皇问题解
解：利称性设计算法求n偶数皇问题解
procedure NQUEENS1(n)
a←0 计数器清零
X(1)←0k←1 k前行X(k)前列
While k>0 do 行执行语句
1) { X(k)←X(k)+1 移列
While X(k)≤n and not PLACE(k) do
2) X(k)←X(k)十l
if X(k)≤n
then if kn
then
{print(X)a←a+1 找解计数器a加1
if an2 then return 找n2解算法结束
3) else {k←k+1X(k)←0}
4) else k←k－1 回溯
　 }
end NQUEENS
武汉工业学院工商学院2008 –2009学年第 1 学期
算法分析考试试卷（A 卷）

课程名称 算法分析 编号 03080121

题号

二
三
四
五
六
七
八
总分
分









评阅









注：1考生必须填写班级姓名学号
2试题纸 1 页
1列组函数f(n)g(n)确定f(n)O(g(n))简述理（12分）
(1)
(2)
(3)
解：简答：
（1）（2）（3）

2试分治法实现重复元素排列问题：设进行排列元素中元素相试计算排列（13分）
解：解答：
Template
void Perm(Type list[]int kint m)
{
if(k m){
for(int i0i cout<}
else for(int iki if(ok(listki)){
swap(list[k]list[i])
Perm(listk+1m)
swap(list[k]list[i]) ……………………………（8分）
}
}
中ok判重复元素
Template
int ok(Type list[]int kint i)
{
if(i>k)
for(int tkt if(list[t] list[i]) return 0
return 1
}……………………………（13分）


3试分治法序表实现二分搜索算法（12分）
解：解答：
Template
int BinarySearch(Type a[]const Type& xint n)
{假定数组a[]已非递减序排列算法找x返回数组a[]中位置否返回1
int left0rightn1
while(left int middle(left+right)2 ……………………………（4分）
if(x a[middle]) return middle+1
if(x>a[middle]) leftmiddle+1 ……………………………（8分）
else rightmiddle1
}
return 1
}……………………………（12分）

4试动态规划算法实现01闭包问题（15分）
解：解答：
Template
void Knapsack(Type vint wint cint nType **m)
{
Int jMaxmin(w[n]1c)
for(int j0j for(int jw[n]jfor(int in1i>1i){
jMaxmin(w[i]1c)
for(int j0j for(int jw[i]j}
m[1][c]m[2][c]
if(c>w[1]) m[1][c]max(m[1][c]m[2][cw[1]]+v[1]) …………（10分）
}
Template
Void Traceback(Type **mint wint cint nint x)
{
for(int i1i if(m[i][c] m[i+1][c]) x[i]0 …………（12分）
else { x[i]1cw[i]}
x[n](m[n][c])10
}……………………………（15分）


5试贪心算法求解列问题：正整数n分解干互相然数然数积（15分）
解：解答：
void dicomp(int nint a[])
{
k1
if(n<3){ a[1]0return}
if(n<5){ a[k]1a[++k]n1return} ……………………………（5分）
a[1]2n2
while(n>a[k]){
k++
a[k]a[k1]+1
na[k]
}……………………………（10分）
if(n a[k]){ a[k]++n}
for(int i0i}……………………………（15分）

6试动态规划算法实现子矩阵问题：求矩阵A子矩阵元素（15分）
解：解答：
int MaxSum2(int mint nint **a)
{
int sum0
int *bnew int[n+1]
for(int i1i for(int k1k for(int jij for(int k1k int maxMaxSum(nb)
if(max>sum) summax
}
}
return sum ……………………………（10分）
}

int MaxSum(int nint *a)
{
int sum0b0
for(int i1i if(b>0) b+a[i]
else ba[i]
if(b>sum) sumb
}
Return sum ……………………………（15分）
}

7试回溯法解决列整数变换问题：关整数变换定义：定两整数求少变换变换次数变（18分）
解：解答：
void compute()
{
k1
while(search(1n)){
k++
if(k>maxdep) break
init()
}……………………………（6分）
if(found) output()
else cout< }……………………………（9分）

bool search(int depint n)
{
If(dep>k) return false
for(int i0i<2i++){
int n1f(ni)t[dep]i ……………………………（12分）
if(n1 m||search(dep+1n1)){
Foundtrue
Out()
return true
}
return false ……………………………（18分）
}



算法设计分析考试试卷
排序查找常遇问题求完成题：（20分）
（1） 数组A{15291351832127255}快速排序方法排成递减序
（2） 请描述递减数组进行二分搜索基思想出非递算法
（3） 出述算法递算法
（4） 述算法（1）结果搜索元素出搜索程：1831135
答案：（1）第步：15 29 135 18 32 1 27 25 5
第二步：29 135 18 32 27 25 15 1 5 1分
第三步：135 32 29 18 27 25 15 5 1 1分
第四步：135 32 29 27 25 18 15 5 1 1分
（2）基思想：首先搜索元素v数组中间元素进行较果前半部分元素中搜索v搜索成功否半部分数组中搜索v2分
非递算法：
输入：递减数组A[leftright]搜索元素v1分
输出：vA中位置pos者A中消息（1）1分
步骤：3分
int BinarySearch(int A[]int leftint rightint v)
{
int mid
while (left {
midint((left+right)2)
if (vA[mid]) return mid
else if (v>A[mid]) rightmid1
else leftmid+1
}
return 1
}
（3）递算法：
输入：递减数组A[leftright]搜索元素v1分
输出：vA中位置pos者A中消息（1）1分
步骤：3分
int BinarySearch(int A[]int leftint rightint v)
{
int mid
if (left {
midint((left+right)2)
if (vA[mid]) return mid
else if (v>A[mid]) return BinarySearch(Aleftmid1v)
else return BinarySearch(Amid+1rightv)
}
else
return 1
}
（4）搜索18：首先27较18<27半部分搜索次18较搜索返回51分
搜索31：首先27较31>27前半部分搜索次32较31<32半部分搜索29较31>29时元素未找返回12分
搜索135：首先27较135>27前半部分搜索次32较135>32前半部分搜索135较相返回02分

二 图Dijkstra算法求顶点a顶点h短路径（20分）

答案：V1表示已找短路径顶点V2表示V1中某顶点相邻接V1中顶点E1表示加入短路径中边E2V1中顶点相邻接距离短路径1分
步骤 V1 V2 E1 E2
1 {a} {b} {} {ab}
2 {ab} {d} {ab} {bd}
3 {abd} {cf} {abbd} {dcdf}
4 {abdc} {f} {abbd} {df}
5 {abcdf} {e} {abbddcdf} {fe}
6 {abcdef} {g} {abbddcdffe} {eg}
7 {abcdefg} {h} {abbddcdffeeg} {gh}
8 {abcdefgh} {} {abbddedffeeggh} {} 步2分
结果：ah短路径权值181分

三 假设7物品重量价值表示物品均分割背包容量M＝150回溯方法求解背包问题请写出状态空间搜索树（20分）
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
答案：求顶点间短路径Dijkstra算法起始节点a循环h次求起始节点节点短路径终求顶点间短路径2分
三单位效益次排列7物品：FBGDECA序号分记1～7生产状态空间搜索树中节点处限界函数值通方式求：排序1分
状态空间搜索树计算程17分节点1分
a．
b
c．
d
e
f
g
h
i
j
Q1处获该问题优解背包效益170背包中装入物品FBGDA时达效益170重量150结2分
四 已知k123456r15r210r33r412r55r650r76求矩阵链积A1×A2×A3×A4×A5×A6佳求积序（求：出计算步骤）（20分）
答案：动态规划算法进行求解
求解矩阵：矩阵18分

1
2
3
4
5
6
1
0
150
330
405
1655
2010
2

0
360
330
2430
1950
3


0
180
930
1770
4



0
3000
1860
5




0
1500
6





0


1
2
3
4
5
6
1
0
1
2
2
4
2
2

0
2
2
2
2
3


0
3
4
4
4



0
4
4
5




0
5
6





0






佳积序列（A1A2）（（A3A4）（A5A6））执行法2010次结2分

五回答问题：（20分）
（1） 什算法？算法特征？
（2） 什P类问题？什NP类问题？请描述集合覆盖问题似算法基思想
答案：（1）算法解决某类问题系列运算集合2分具穷行行性确定性0者输入1者输出8分
（2）确定图灵机项式实践解判定问题称P类问题2分确定图灵机项式实践解判定问题称P类问题2分
集合覆盖问题似算法采贪心思想：问题次选择F中覆盖未覆盖元素子集S然U中S覆盖元素删S加入C中C似优解6分




中南学考试试卷
2007 2008 学年 学期 时间110分钟 2008年6 月
算法复杂性分析 课程 48 学时 3 学分 考试形式：闭 卷
专业年级：软件0501软件06010602 总分100分占总评成绩70
注：页作答题纸请答案写答题纸
填空题（题15分题1分）
1 算法组穷 规定解决某特定类型问题
2 进行问题计算复杂性分析前首先必须建立求解问题计算模型3基计算模型
3 算法复杂性 度量评价算法优劣重
4 计算机资源重 资源算法复杂性 分
5 f(n) 6×2n+n2f(n)渐进性态f(n) O(    )
6 贪心算法总做出前 选择说贪心算法整体优考虑做出选择某种意义
7 许贪心算法求解问题般具2重性质： 性质 性质
二简答题（题25分题5分）
1 简单描述分治法基思想
2 简述动态规划方法运优化原理
3 谓优子结构性质？
4 简单描述回溯法基思想
5 谓PNPNPC问题
三算法填空（题20分题5分）
1n问题回溯算法
(1)二维数组A[N][N]存储皇位置第i行第j列放皇A[i][j]非0值否值0
(2)分维数组M[N]L[2*N1]R[2*N1]表示竖列左斜线右斜线否放棋子值1否值0
for(j0j if( 1 ) *安全检查*
{ A[i][j]i+1 *放皇*
2
if(iN1) 输出结果
else 3 *试探行*
4 *皇*
5
}
2数塔问题形图示数塔顶部出发结点选择左走右走起走底层求找出条路径路径值
for(rn2r>0r) 底递计算
for(c0 1 c++)
if( t[r+1][c]>t[r+1][c+1]) 2
else 3
3Hanoi算法
Hanoi(nabc)
if （n1） 1
else
{ 2
3
Hanoi(n1b a c)
}
4Dijkstra算法求单源短路径
d[u]su距离 p[u]记录前节点信息
Initsinglesource(Gs)
for each vertex v∈V[G]
do { d[v]∞ 1 }
d[s]0
Relax(uvw)
if d[v]>d[u]+w(uv)
then { d[v]d[u]+w[uv]
2
}
dijkstra(Gws)
1 Initsinglesource(Gs)
2 SΦ
3 QV[G]
4while Q<> Φ
do umin(Q)
SS∪{u}
for each vertex 3
do 4
四算法理解题（题10分）
根优先队列式分支限界法求图中v1点v9点单源短路径请画出求优解解空间树求中间舍弃结点×标记获中间解结点单圆圈○框起优解双圆圈◎框起
五算法理解题（题5分）
设n2k运动员进行循环赛现设计满足求赛日程表：
①选手必须n1名选手赛次
②选手天赛次
③循环赛短时间完成
（1）果n2k循环赛少需进行天
（2）n238时请画出循环赛日程表
六算法设计题（题15分）
分贪心算法动态规划法回溯法设计01背包问题求：说明算法策略写出算法实现步骤分析算法时间
七算法设计题（题10分）
通键盘输入高精度正整数n(n效位数≤240)掉中意s数字剩数字原左右次序组成新正整数编程定n s寻找种方案剩数字组成新数
样例输入
178543
S4
样例输出
13




填空题（题15分题1分）
1．规 系列运算
2 机存取机RAM(Random Access Machine)机存取存储程序机RASP(Random Access Stored Program Machine)图灵机(Turing Machine)
3   算法效率
4  时间 空间时间复杂度 空间复杂度
5．2n 
6．  局部优选择
7 贪心选择 优子结构
二简答题（题25分题5分）
6 分治法基思想规模n问题分解k规模较子问题子问题互相独立原问题相k子问题分求解果子问题规模然够划分k子问题递进行直问题规模足够容易求出解止求出规模问题解合更规模问题解底逐步求出原问题解
7 优化原理数学化语言描述：假设解决某优化问题需次作出n决策D1D2…Dn决策序列优整数k1 < k < n前面k决策样优决策取决前面决策确定前状态决策Dk+1Dk+2…Dn优
8 某问题优解包含着子问题优解种性质称优子结构性质
9 回溯法基思想棵含问题全部解状态空间树进行深度优先搜索解叶子结点搜索程中达结点时判断该结点根子树否含问题解果确定该子树中含问题解放弃该子树搜索退回层父结点继续步深度优先搜索程回溯法中先构造出整棵状态空间树进行搜索搜索程逐步构造出状态空间树边搜索边构造
10 P(Polynomial问题)：项式复杂程度问题
NPNondeterministic Polynomial问题项式复杂程度非确定性问题
NPC(NP Complete)问题种问题解域里面穷举出答案样问题NP里面难问题种问题NPC问题
三算法填空（题20分题5分）
1n问题回溯算法
(1) M[j]&&L[i+j]&&R[ij+N]
(2) M[j]L[i+j]R[ij+N]1
(3) try(i+1MLRA)
(4) A[i][j]0
(5) M[j]L[i+j]R[ij+N]0
2数塔问题
（1）c(2)t[r][c]+t[r+1][c]
（3）t[r][c]+t[r+1][c+1]
3Hanoi算法
（1）move(ac)
（2）Hanoi(n1 a c b)
（3）Move(ac)
4（1）p[v]NIL
（2）p[v]u
(3) v∈adj[u]
（4）Relax(uvw)
四算法理解题（题10分）








1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1

五（1）8天（2分）
（2）n238时循环赛日程表（3分）
六算法设计题（题15分）
（1）贪心算法 O（nlog（n））
Ø 首先计算种物品单位重量价值ViWi然贪心选择策略单位重量价值高物品装入背包种物品全部装入背包背包物品总重量未超C选择单位重量价值次高物品装入背包策略直进行直背包装满止
Ø 具体算法描述：
void Knapsack(int nfloat Mfloat v[]float w[]float x[])
{Sort(nvw)
int i
for (i1ifloat cM
for (i1i{if (w[i]>c) break
x[i]1
cw[i]
}
if (i}
（2）动态规划法 O(nc)
m(ij)背包容量j选择物品ii+1…n时01背包问题优值01背包问题优子结构性质建立计算m(ij)递式

void KnapSack(int v[]int w[]int cint nint m[][11])
{int jMaxmin(w[n]1c)
for (j0jm[n][j]0
for (jw[n]jw[n]*
m[n][j]v[n]
for (in1i>1i)
{ int jMaxmin(w[i]1c)
for (j0j m[i][j]m[i+1][j]
for (jw[i]jw[n]*
m[i][j]max(m[i+1][j]m[i+1][jw[i]]+v[i])
}
m[1][c]m[2][c]
if(c>w[1])
m[1][c]max(m[1][c]m[2][cw[1]]+v[1])
}

（3）回溯法 O(2n)
cw前重量 cp前价值 bestp：前优值
void backtrack(int i)
回溯法  i初值1
{    if(i > n) 达叶结点
{ bestp  cp              return            }   
     if(cw + w[i] < c) 搜索左子树   
         { cw + w[i]
  cp + p[i]              
backtrack(i+1)   
           cw  w[i]
            cp  p[i]   
        }   
       if(Bound(i+1)>bestp)
搜索右子树   
        backtrack(i+1)   
 }   



七算法设计题（题10分）
逼目标选取贪心策略：步总选择剩数数字删高位低位序搜索位数字递增删数字否删第递减区间首字符然回串首述规删数字重复程s次剩数字串便问题解
具体算法：
输入s n
while（ s > 0 ）
{ i1 串首开始找
while (i < length(n)) && (n[i]{i++}
delete(ni1) 删字符串n第i字符
s
}
while (length(n)>1)&& (n[1]0’)
delete(n11) 删串首产生零
输出n


算法分析设计期末复题()
．填空题（空2分30分）
1．算法时间复杂性指算法中 执行次数
2．忽略常数子情况O三符号中 提供算法运行时间界
3．设Dn表示n输入集合t(I)表示输入I时算法运算时间 p(I)表示输入I出现概率算法均情况时间复杂性A(n)
4．分治算法时间复杂性常常满足形式递方程：

中g(n)表示
5 分治算法基步骤包括
6．回溯算法基思想
7．动态规划分治法分解子问题方面点
8．贪心算法中次做出贪心选择 优选择
9．PQ式分支限界法中活结点表中结点界函数值越优先级越
10．选择排序插入排序排序算法中 算法分治算法
11．机算法基特征组输入 运行 结果
12面确定性快速排序算法步骤3前加入机化步骤 机化快速排序算法该机化步骤功
算法 QUICKSORT
输入：n元素数组A[1n]
输出：非降序排列数组A中元素
1 quicksort(1 n)
end QUICKSORT
程 quicksort(A low high)
A[lowhigh]中元素非降序排序
2 if low3 wSPLIT(A low high)
算法SPLITA[low]元A[lowhigh]划分成两部 分返回元新位置
4 quicksort (A low w1)
5 quicksort (A w+1 high)
6． end if
end quicksort
13．面算法基运算 运算该算法时间复杂性阶( )
算法 SPLIT
输入：正整数n数组A[1n]
输出：…
i1
xA[1]
for j2 to n
if A[j] ii+1
if ij then A[i]A[j]
end if
end for
A[i]A[1]
w i
return w A
end SPLIT
二．计算题简答题（题7分21分）
1．O表示函数fg间阶关系分指出列函数中阶低高函数：
(1)　f (n)100 g(n)
(2) f(n)6n+n g(n)3n
(3) f(n) nlogn1 g(n)
(4) f(n) g(n)
(5) f(n) g(n)
2．面递算法中程pro1pro2运算时间分1出该算法时间复杂性T(n)满足递方程求解该递方程估计T(n)阶（表示）
算法 EX1
输入：正整数nn2k
输出：…
ex1(n)
end EX1
程 ex1(n)
if n1 then
pro1(n)
else
pro2(n)
ex1(n2)
end if
return
end ex1
3．Floyd算法求图顶点间短路径长度计算矩阵D0D1D2D3中Dk[i j]表示顶点i顶点j编号k顶点短路径长度
三．算法填空题（34分）
1．（10分）设n整数升序存数组A[1n]中求A[i]i标i 面求解该问题分治算法
算法 SEARCH
输入：正整数n存储n升序排列整数数组A[1n]
输出：A[1n]中A[i]i标i存输出 no solution
ifind ( (1) )
if i>0 then output i
else output no solution
end SEARCH
程 find (low high)
求A[lowhigh] 中A[i]i标返回存返回0
if (2) then return 0
else
mid
if (3) then return mid
else
if A[mid]return find( (4) )
else
return (5)
end if
end if
end if
end find
2．(10分) 面求解矩阵链问题动态规划算法
矩阵链问题：出n矩阵M1 M2 … Mn Mi riri+1阶矩阵i1 2 … n求计算M1M2…Mn需少数量法次数
记 Mi jMiMi+1…Mj i
算法 MATCHAIN
输入：矩阵链长度n n矩阵阶r[1n+1] 中r[1n]n矩阵行数r[n+1]第n矩阵列数
输出：n矩阵链需数量法少次数
for i1 to n C[i i] （1）
　for d1 to n1
for i1 to nd
　　　j (2)
C[i j] ∞
for ki+1 to j
x (3)
if x (4) x
end if
end for
end for
end for
return (5)
end MATCHAIN
3．(14分) 面回溯法求解马周游问题算法
马周游问题：出nxn棋盘已知中国象棋马棋盘某起点位置（x0 y0）求条访问棋盘格点恰次回起点周游路线（设马走日字）
算法 HORSETRAVEL
输入：正整数n马起点位置(x0 y0)1输出：条起点始访问nxn棋盘格点恰次回起点周游路线问题解输出no solution
tag[1n 1n]0
dx[18]{2 1 1 2 2 1 1 2}
dy[18]{1 2 2 1 1 2 2 1}
flagfalse
xx0 yy0 tag[x y]1
mn*n
i1 k[i]0
while (1) and not flag
while k[i]<8 and not flag
k[i] (2)
x1 x+dx[k[i]] y1 y+dy[k[i]]
if ((x1y1)越界and tag[x1 y1]0) or ((x1y1)(x0y0) and im) then
xx1 yy1
tag[x y] (3)
if im then flagtrue
else
i (4)
(5)
end if
end if
end while
ii1
(6)
　 (7)
end while
if flag then outputroute(k) 输出路径
else output no solution　
end HORSETRAVEL
四．算法设计题（15分）
1 旅行者驾车ABAB两间距离sAB两间n加油站已知第i加油站离起点A距离公里0车加满油行驶m公里出发前汽车油箱空应加油AB途加油次数少？出贪心法求解该优化问题贪心选择策略写出求该优化问题优值优解贪心算法分析算法时间复杂性

参考答案：2005计算法设计分析期考试卷(A)标准答案

填空题：
1 元运算
2 O
3
4 规模n问题分解子问题组合相应子问题解需时间
5 分解递组合
6 问题状态空间树作带剪枝DFS搜索（：DFS+剪枝）
7 前者分解出子问题重叠者分解出子问题相互独立（重叠）
8 局部
9 高
10 排序算法
11
12 vrandom (low high) 交换A[low]A[v]值
机选元
13 较
n

二 计算题简答题：
1 阶关系：
(1) f(n) O(g(n))
(2) f(n)(g(n))
(3) f(n)(g(n))
(4) f(n) O(g(n))
(5) f(n)(g(n))
阶低函数：100
阶高函数：
2 该递算法时间复杂性T(n)满足列递方程：

n a1 c2 g(n) d1代入该类递方程解般形式：
T(n)1+1+k
1+ k++1
T(n) ++1
3



三 算法填空题：
1 (1) 1 n (2) low>high (3) A[mid]mid
(4) mid+1 high (5) find(low mid1)
2 (1) 0 (2) i+d (3) C[i k1]+C[k j]+r[i]*r[k]*r[j+1]
(4) C[i j] (5) C[1 n]
3 (1) i>1 (2)k[i]+1 (3) 1
(4) i+1 (5) k[i]0 (6) tag[x y]0
(7) xxdx[k[i]] yydy[k[i]]

四 算法设计题：
1 贪心选择策略：起点加油站起次加满油加油行驶远直油箱中油耗前达远油站止该油站加满油
算法 MINSTOPS
输入：AB两间距离sAB两间加油站数n车加满油行驶公里数m存储加油站离起点A距离数组d[1n]
输出：AB少加油次数k优解x[1k]（x[i]表示第i次加油加油站序号）问题解输出no solution
d[n+1]s 设置虚拟加油站第n+1站
for i1 to n
if d[i+1]d[i]>m then
output no solution return 解返回
end if
end for
k1 x[k]1 第1站加满油
s1m s1汽车前油量行驶点A点距离
i2
while s1if d[i+1]>s1 then 汽车前油量法达第i+1站
kk+1 x[k]i 第i站加满油
s1d[i]+m 刷新s1值
end if
ii+1
end while
output k x[1k]
MINSTOPS

坏情况时间复杂性：Θ(n)



文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档