算法分析设计期末复题()
选择题
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
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
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)
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)
二 填空题
1 面程序段需计算时间( )
int MaxSum(int n int *a int &besti int &bestj)
{
int sum0
for(int i1i
for(int jij
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 Knap
{ 计算界
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 j1j
return true
}
13 旅行售货员问题解空间树(排列树)
6
7
三 解答题
1 机器调度问题
问题描述:现n件务限台机器务机器处理件务开始时间si完成时间fisi
画出工作应机器分配情况
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)(i
10 第K行皇分前k1行皇较否相容果相容返回false测试完毕返回true
11 子问题规模时必须继续分治法反复分治必然递
12 坏情况时间复杂性决定算法优劣坏情况时间复杂性较均时间复杂性游操作性
13 T(n)某算法时间复杂性函数f(n)简单函数存正整数NoCn〉NoT(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
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