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


算法分析设计期末复题

选择题
1 算法必须具备输入输出（ D ）等4特性
A．行性安全性 B．确定性易读性
C．穷性安全性 D．穷性确定性
2 算法分析中记号O表示（ B ）记号Ω表示（ A ）
A渐进界 B渐进界
C非紧界 D紧渐进界
3 假设某算法输入规模n时计算时间T(n)3*2^n某台计算机实现完成概算法时间t秒现台计算机运行速度第台64倍台新机器算法t秒解输入规模问题？（ B ）解题方法：3*2^n*643*2^x
A．n+8 B．n+6
C．n+7 D．n+5
4 设问题规模N时某递算法时间复杂度记T(N)已知T(1)1T(N)2T(N2)+N2O表示时间复杂度（ C ）
A．O(logN) B．O(N)
C．O(NlogN) D．O(N²logN)
5 直接间接调身算法称（ B ）
A．贪心算法 B．递算法
C．迭代算法 D．回溯法
6 Fibonacci数列中第4第11数分（ D ）
A．589 B．389
C．5144 D．3144
7 8顶点凸边形三角剖分中恰（ B ）
A．6条弦7三角形 B．5条弦6三角形
C．6条弦6三角形 D．5条弦5三角形
8 问题动态规划算法贪心算法求解关键特征问题（ B ）
A．重叠子问题 B．优子结构性质
C．贪心选择性质 D．定义优解
9 列问题贪心法求解（ C ）
A．哈夫曼编码问题 B．单源短路径问题
C．团问题 D．生成树问题
10 列算法中通常底方式求解优解（ B ）
A．备忘录法 B．动态规划法
C．贪心法 D．回溯法
11 列算法中解决01背包问题（ A ）
A．贪心法 B．动态规划
C．回溯法 D．分支限界法
12 列问题贪心算法求解（ D ）
A．LCS问题 B．批处理作业问题
C．01背包问题 D．哈夫曼编码问题
13 回溯法求解优装载问题时选物品m种该问题解空间树结点数（ ）
A．m B．2m+1
C．2m+11 D．2m
14 二分搜索算法利（ A  ）实现算法
A．分治策略   B．动态规划法  
C．贪心法    D．回溯法
15 列动态规划算法基步骤（ B  ）P44
A．找出优解性质  B．构造优解 
C．算出优解(应该优值)  D．定义优解
16 面问题（ B ）贪心法解决
A．单源短路径问题 B．N皇问题
C．花费生成树问题 D．背包问题
17 二分搜索算法n序元素表中搜索特定元素情况坏情况搜索时间复杂性分（ A ）P17
A．O(1)O(logn) B．O(n)O(logn)
C．O(1)O(nlogn) D．O(n)O(nlogn)
18 优先队列式分支限界法选取扩展结点原（ C  ）P162
A．先进先出 B．进先出
C．结点优先级 D．机
19 面分支界限法搜索方式（ D ）P161
A．广度优先 B．耗费优先
C．效益优先 D．深度优先
20 分支限界法解团问题时活结点表组织形式（ B ）
A．堆 B．堆
C．栈 D．数组
21 列关计算机算法描述正确（ C ）P1
A．算法指解决问题种方法程
B．算法干指令穷序列
C 算法必须输入输出
D．算法编程思想
22 列关凸边形优三角剖分问题描述正确（ A ）
A．n+1矩阵连完全加括号n点凸边形三角剖分应
B．n顶点凸边形三角剖分中恰n3条弦
C．该问题动态规划法求解
D．n顶点凸边形三角剖分中恰n2三角形
23 动态规划法求解问题基步骤包括（ C ）P44
A．递定义优值
B．分析优解性质刻画结构特征
C．根计算优值时信息构造优解 (省)
D．底方式计算出优值
24 分治法解决问题应具关键特征（ C ）P16
A．该问题规模缩定程度容易解决
B．该问题分解干规模较相问题
C．利该问题分解出子问题解合该问题解
D．该问题分解出子问题相互独立
25 列关回溯法描述正确（ D ）P114
A．回溯法称试探法
B．回溯法通解题法称
C．回溯法种避免必搜索穷举式搜索法
D．回溯法解空间作深度优先搜索时递方法实现
26 常见两种分支限界法（ D ）P161
A 广度优先分支限界法深度优先分支限界法
B 队列式（FIFO）分支限界法堆栈式分支限界法
C 排列树法子集树法
D 队列式（FIFO）分支限界法优先队列式分支限界法


二 填空题
1 f(n)3n2+10渐性态f(n) O( n2 )
g(n)10log3n渐性态g(n) O(  n  )
2 算法应具正确性 读性 健壮性 高效率低存储量需求等特性
3 算法时间复杂性函数表示 CF(NIA) 分析算法复杂性目较 求解意问题两算法效率 效率
4 构成递式两基素 递边界条件 递定义
5 单源短路径问题 分支限界法 贪心算法 求解
6 分治法实现快速排序算法时情况时间复杂性 O(nlogn) 坏情况时间复杂性 O(n^2) 该算法需时间 运行时间 划分 两方面素关P26
7 01背包问题解空间树 完全二叉 树n问题解空间树 排列 树
8 常见分支限界法队列式（FIFO）分支限界法优先队列式分支限界法
9 回溯法搜索解空间树时常两种剪枝函数 约束函数 剪枝函数
10 分支限界法解团问题时活结点表组织形式 堆 分支限界法解单源短路径问题时活结点表组织形式 堆
三 算法填空题
1 递求解Hanoi塔问题阶问题
例1 阶函数n P12
阶非递方式定义：
试写出阶乖递式算法
递式： 边界条件
递方程
递算法：
int factorial (int n)
{ if (n0) return 1 递出口
return n * factorial (n1) 递调
}
例2递技术求解Hanoi塔问题Hanoi塔递算法P15
中Hanoi (int n int a int c int b)表示塔座An盘子移塔座C塔座B辅助Move(ac)表示塔座a编号n圆盘移塔座c


void hanoi (int n int a int c int b)
{
if (n > 0)
{
hanoi(n1 a b c)
move(ac)
hanoi(n1 b c a)
}
}
2 分治法求解快速排序问题
快速排序算法 P25 作业课件第2章（2）42页50页
template
void QuickSort (Type a[] int p int r)
{
if (p int qPartition(apr)
QuickSort (apq1)
QuickSort (aq+1r)
}
}
Partition函数具体实现
template
int Partition (Type a[] int p int r)
{
int i p j r + 1
Type xa[p]
< x元素交换左边区域
> x元素交换右边区域
while (true) {
while (a[++i] while (a[ j] >x)
if (i > j) break
Swap(a[i] a[j])
}
a[p] a[j]
a[j] x
return j
}
3 贪心算法求解优装载问题
优装载问题 P95 课件第4章(2)第38页
template
void Loading(int x[] Type w[] Type c int n)
{
int *t new int [n+1]
Sort(w t n)
for (int i 1 i < n i++) x[i] 0
for (int j 1 j < n && w[t[j]] < c j++)
{x[t[i]] 1 c w[t[j]]}
}
4 回溯法求解01背包批处理作业调度 团问题会画解空间树
例1：回溯法求解01背包 P133课件第5章(2)第2438页
template
class Knap
{
private
Typep Bound(int i) 计算界
void Backtrack(int i)
Typew c 背包容量
int n 物品数
Typew *w 物品重量数组
Typep *p 物品价值数组
Typew cw 前重量
Typep cp 前价值
Typep bestp 前优价值
}

void KnapBacktrack(int i)
{ if(i>n) { bestpcp return }
if(cw+w[i] { cw+w[i]
cp+p[i]
Backtrack(i+1)
cww[i]
cpp[i] }
if(Bound(i+1)>bestp) 进入右子树
Backtrack(i+1)
}

Typep KnapBound(int i)
{
Typew cleftccw 剩余背包容量
Typep bcp b前价值
次装入单位重量价值高整物品
while(i { cleftw[i] b+p[i] i++ }
if(i b+p[i]*cleftw[i]
return b 返回界
}

class Object 物品类
{
friend int Knapsack(int *int *intint)
public
int operator <(Object a) const
{
return (d>ad)
}
int ID 物品编号
float d 单位重量价值
}

Typep Knapsack( Typep p[]Typew w[]Typew cint n)
{ Typep Knapsack初始化
Typew W0 总重量
Typep P0 总价值
Object* Qnew Object[n] 创建物品数组标0开始
for(int i1i { Q[i1]IDi
Q[i1]d10*p[i]w[i]
P+p[i] W+w[i]
}
if(W return P
if(W return P
QuickSort(Q0n1) 物品单位重量价值非增排序
Knap K
Kpnew Typep[n+1]
Kwnew Typew[n+1]
for(int i1i { Kp[i]p[Q[i1]ID] Kw[i]w[Q[i1]ID] }
Kcp0 Kcw0 Kcc
Knn Kbestp0 KBacktrack(1)
delete[] Q delete[] Kw
delete[] Kp return Kbestp
}
例2：批处理作业调度 课件第5章(2)P25问题描述课P125127
解空间：排列树
算法描述：
class Flowshop
{
static int [][] m 作业需处理时间
[] x 前作业调度
[] bestx 前优作业调度
[] f2 机器2完成处理时间
f1 机器1完成处理时间
f 完成时间
bestf 前优完成时间
n 作业数
static void Backtrack(int i)
{
if (i > n)
{ for (int j 1 j < n j++) bestx[j] x[j] bestf f }
else
for (int j i j < n j++) {
f1+m[x[j]][1]第j作业第台机器需时间
f2[i]((f2[i1]>f1)f2[i1]f1)+m[x[j]][2]
f+f2[i]
if (f < bestf) 约束函数
{ Swap(x[i] x[j]) Backtrack(i+1) Swap(x[i] x[j]) }
f1 m[x[j]][1]
f f2[i]
}
}


例3：团问题会画解空间树
class Clique
{
friend int MaxClique(int **int []int)
public
void Print() 输出优解
private
void Backtrack(int i)
int **a 图G邻接矩阵标1开始
int n 图G顶点数
int *x 前解
int *bestx 前优解
int cn 前团顶点数
int bestn 前团顶点数
}
void CliqueBacktrack(int i)
{ if(i>n)
{ for(int j1j判断第i顶点否已选顶点边相连
int OK1
for(int j1j if(x[j]&&a[i][j]0) i前团中顶点边相连
{ OK0 break } 前团中顶点边相连中止
if(OK) 进入左子树
{ x[i]1 cn++ Backtrack(i+1) x[i]0 cn }
if(cn+ni>bestn) 右子树中找更团进入右子树
{ x[i]0 Backtrack(i+1) }
}
计算时间：O(n2n)

四 简答题
1 请简述动态规划算法解题基步骤P44
动态规划设计分4步骤：
(1)找出优解性质刻划结构特征
(2)递定义优值
(3)底方式计算出优值
(4)根计算优值时信息构造优解
2 简述动态规划方法分治法异P44
相点：动态规划算法分治法类似基思想求解问题分解成干子问题然子问题解原问题解
点：分治法子问题互相独立原问题相分治法适合动态规划求解问题分解子问题互相独立子问题包含公子子问题
3 试较Prim算法Kruskal算法异105P107
相点：Prim(普里姆)算法Kruskal(克鲁斯卡尔)算法作应贪心算法构造生成树例子利生成树性质
点：
Prim(普里姆)算法：程中选取边恰构成G棵生成树TT中包含Gn1条边形成回路
Kruskal(克鲁斯卡尔)算法：构造生成树常算法该算法通扩充连通子集进行贪心选择通选择具权边集合进行贪心选择选择时进行连通操作便形成生成树
4 请简述分支限界法搜索策略P161 课件第6章(1)第6页
(1)分支限界法广度优先耗费（效益）优先方式搜索问题解空间树
(2)活结点次机会成扩展结点
(3)活结点旦成扩展结点次性产生子结点
(4)子结点中导致行解导致非优解子结点舍弃余子结点加入活结点表中
(5)活结点表中取 结点 成前扩展结点重复述结点扩展程程直持续找需解活结点表空时止
5 试较分支限界法回溯法异P161 课件第6章(1)第5页
点：
(1)求解目标：回溯法求解目标找出解空间树中满足约束条件解分支限界法求解目标找出满足约束条件解满足约束条件解中找出某种意义优解
(2)搜索方式：回溯法深度优先方式搜索解空间树分支限界法广度优先耗费优先方式搜索解空间树
五 算法应题
1 动态规划求解凸边形优三角剖分问题
三角剖分结构相关问题P61
(1)语法树完全加括号方式
表达式完全加括号方式相应棵完全二叉树称表达式语法树
例完全加括号矩阵连积((A1(A2A3))(A4(A5A6)))相应语法树图 (a)示

(2)语法树凸边形三角剖分
凸边形P{v0v1…vn1}三角剖分语法树表示
图：根结点边v0v 6(选)边语法树叶子节点 v0v 6三角形v0v3v 6条边

2三角剖分矩阵连P61
(1)般说凸边形三角剖分n1叶节点语法树存应关系
(2)N矩阵连完全加括号n叶节点语法树存应关系
(3)n矩阵连完全加括号n+1节点凸边形三角剖分存应关系

(4)矩阵连积中A1 A2 …An中矩阵Ai应凸(n+1)边形中条边vi1vi三角剖分中条弦vivji(5)矩阵连积优计算次序问题凸边形优三角剖分问题特殊情况

课题（第3章结**）
矩阵链
P{101005503020604550}请构造优完全加括号方式列出相应语法树优三角剖分图








2 贪心算法求解活动安排问题生成树问题哈夫曼编码问题
贪心算法求解活动安排问题
例：设安排11活动开始时间结束时间结束时间非减序排列：

生成树问题 P103P105


哈夫曼编码问题前缀码二叉树表示法
例子：
图a固定长度编码应树(叶子高度致)
图b变长度编码应树(叶子高度致)


3 回溯法求解01背包问题优装载问题
回溯法求01背包问题P133
实例n5M50
N
1
2
3
4
5
W
15
5
25
27
30
P
30
12
44
46
50
PW
2
24
176
170
167
(1)令bestp0物体序号价值体积排序结果（21345）
N
2
1
3
4
5
W
5
15
25
27
30
P
12
30
44
46
50
PW
24
2
176
170
167
(2) 根排序部分解(1110)估计前部分解价值b86+(5045)*167943 b >bestp
(3) 继续搜索生成结点F行解(11100)价值86更新bestp86(图第3步)


第3步 第5步 第8步
(4) 回溯：E回溯左孩子D生成相应右孩子G部分解( 1101 )时b931 b>bestp生成右子树（第4步第5步基础没HI图形）
(5) 继续生成结点HI行解( 11010 )价值88更新bestp88(图第5步)
(6) 回溯H生成J部分解( 1100 )估计部分解b92>88（第6步第8步基础没KL图形）
(7) 继续生成结点K行解( 1100 1 )价值92更新bestp92（第7步第8步基础没L图形）
(8) K左孩子生成应右孩子L行解( 11000) (图第8步)
(9) 回溯结点L回溯结点B生成结点M部分解 (10) 估计部分解b90<92回溯（第9步第10步基础没N图形）
(10) 继续回溯生成结点N部分解(0)时b74+10*(4627) 9103<92回溯时已回根结点结束优解( 1100 1 )价值92 (图第10步)

练
n8 M110
W( 1 11212333434555 )
P(1121313343535565 )
回溯法求01背包问题优解

优装载问题 P119 课件第P37 P54页
假定n 4w [ 8 6 2 3 ]c1 c2 12
试根改进优装载算法找出优装载量相应优装载方案
求：
a) 列出问题解空间
b) 构造解空间树
c) 根递回溯算法求出优解优值

六 算法设计题
贪心算法求解
题型：
开会问题：
某公司会议全公司唯会议室够现出段时期会议时间表求适删会议剩余会议时间互突求删会议数少
解题算法
template
void GS (int n Type s[] Type f[] bool A[])
{
A[1]false
int j1
int sum0
for (int i2i {
if (s[i]>f[j]) { A[i]false ji }
else {A[i]true sum++}
}
}
题型二：
试贪心算法求解列问题：正整数n分解干互相然数然数积写出该算法先n较例子否中找出规律：

算法分析：
u 猜想n拆成量数积？（拆出数中2）
u 数数n减23…i直nu 时ni相等先i+1时n1
u 时n>0均匀分前面项
u 贪心策略n停拆分开数拆
解题算法


题型三：
田忌赛马：果3匹马变成n匹齐王然马优劣序出赛田忌意序选择赛马出赛赢局田忌200两银子输局田忌输掉200两银子已知国王田忌马奔跑速度马奔跑速度均相现已两马分快慢排序请设计算法帮助田忌赢银子
解题思路：
u 先两组马速度排序
u 果田忌(A)快马齐王(B)快马快直接赢
u 果A快马B慢A慢马拼B快马
u 果A慢马B慢马快直接拼掉
u 果A慢马B慢马慢A慢马拼B快马
u 果AB快慢马速度相A慢马拼B快马
算法分析


文档香网(httpswwwxiangdangnet)户传

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