选择题
1二分搜索算法利（ A ）实现算法
A分治策略 B动态规划法 C贪心法 D回溯法
2列动态规划算法基步骤（ A ）
A找出优解性质 B构造优解 C算出优解 D定义优解
3效益优先（ A ）搜索方式
A分支界限法 B动态规划法 C贪心法 D回溯法
4 回溯法解旅行售货员问题时解空间树（ B ）
A子集树 B排列树 C深度优先生成树 D广度优先生成树
5．列算法中通常底方式求解优解（ B ）
A备忘录法B动态规划法 C贪心法 D回溯法
6衡量算法坏标准（C ）
A 运行速度快 B 占空间少 C 时间复杂度低 D 代码短
7分治法求解（D ）
A 棋盘覆盖问题 B 选择问题 C 排序 D 01背包问题
8 实现循环赛日程表利算法（ A ）
A分治策略 B动态规划法 C贪心法 D回溯法
9．面分支界限法搜索方式（ D ）
A广度优先 B耗费优先 C效益优先 D深度优先
10．列算法中通常深度优先方式系统搜索问题解（ D ）
A备忘录法 B动态规划法 C贪心法 D回溯法
11备忘录方法种算法变形（ B ）
A分治法 B动态规划法 C贪心法 D回溯法
12．哈弗曼编码贪心算法需计算时间（ B ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
13．分支限界法解团问题时活结点表组织形式（ B ）
A堆 B堆 C栈 D数组
14．长公子序列算法利算法（ B ）
A分支界限法 B动态规划法 C贪心法 D回溯法
15．实现棋盘覆盖算法利算法（ A ）
A分治法 B动态规划法 C贪心法 D回溯法
16面贪心算法基素（ C ）
A重叠子问题 B构造优解 C贪心选择性质 D定义优解
17回溯法效率赖列素（ D ）
A 满足显约束值数 B 计算约束函数时间
C 计算限界函数时间 D 确定解空间时间
18面种函数回溯法中避免效搜索采取策略（ B ）
A．递函数 B剪枝函数 C机数函数 D搜索函数
19面关NP问题说法正确（B ）
A NP问题解决问题
B P类问题包含NP类问题中
C NP完全问题P类问题子集
D NP类问题包含P类问题中
20蒙特卡罗算法（ B ）种
A分支界限算法 B概率算法 C贪心算法D回溯算法
21（ D ）贪心算法动态规划算法点
A重叠子问题 B构造优解 C贪心选择性质D优子结构性质
22 矩阵连问题算法（ B）设计实现
A分支界限算法 B动态规划算法 C贪心算法 D回溯算法
23 分支限界法解旅行售货员问题时活结点表组织形式（ A ）
A堆 B堆 C栈 D数组
24Strassen矩阵法利（ A ）实现算法
A分治策略 B动态规划法 C贪心法 D回溯法
25分治法求解需满足条件（A ）
A 子问题必须样
B 子问题够重复
C 子问题解合
D 原问题子问题相方法解
26面问题（B ）贪心法解决
A 单源短路径问题 B N皇问题
C 花费生成树问题 D 背包问题
27列算法中解决01背包问题（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
28回溯法搜索状态空间树（C ）序
A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历
29．实现合排序利算法（ A ）
A分治策略 B动态规划法 C贪心法 D回溯法
30．列动态规划算法基素（D ）
A定义优解 B构造优解 C算出优解 D子问题重叠性质
31．列算法中通常底方式求解优解（ B ）
A分治法 B动态规划法 C贪心法 D回溯法
32．采广度优先策略搜索算法（ A ）
A分支界限法 B动态规划法 C贪心法 D回溯法
33合排序算法利（A ）实现算法
A分治策略 B动态规划法 C贪心法 D回溯法
34背包问题贪心算法需计算时间（ B ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
35．实现整数法利算法（C ）
A贪心法 B动态规划法 C分治策略 D回溯法
36．01背包问题回溯算法需计算时间（ A ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
37．采效益优先搜索方式算法（ A ）
A分支界限法 B动态规划法 C贪心法 D回溯法
38．贪心算法动态规划算法区（ B ）
A优子结构 B贪心选择性质 C构造优解 D定义优解
39 实现子段利算法（ B ）
A分治策略 B动态规划法 C贪心法 D回溯法
40优先队列式分支限界法选取扩展结点原（ C ）
A先进先出 B进先出 C结点优先级 D机
41背包问题贪心算法需计算时间（ B ）
AO（n2n）BO（nlogn） CO（2n） DO（n）
42广度优先（ A ）搜索方式
A分支界限法 B动态规划法 C贪心法 D回溯法
43列种算法机化算法（ D ）
A 贪心算法B 回溯法C动态规划算法D舍伍德算法
44 问题动态规划算法贪心算法求解关键特征问题（B ）
A重叠子问题 B优子结构性质 C贪心选择性质 D定义优解
45．采贪心算法优装载问题计算量集装箱重量排序算法时间复杂度 (B )
AO（n2n）BO（nlogn） CO（2n） DO（n）
46 深度优先方式系统搜索问题解算法称( D )
A分支界限算法B概率算法 C贪心算法 D回溯算法
47 实现长公子序列利算法（ B ）
A分治策略B动态规划法 C贪心法 D回溯法
48算法干条指令组成穷序列满足性质（ D）
（1） 输入：0输入
（2） 输出：少输出
（3） 确定性：指令清晰歧义
（4） 限性：指令执行次数限执行时间限
A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)
48函数32n+10nlogn渐进表达式( B )
A 2n B 32n C nlogn D 10nlogn
49整数法算法( A )算法
A分治 B贪心C动态规划 D穷举
50动态规划算法解决字段问题时间复杂性( B )
Alogn Bn Cn2 Dnlogn
51解决活动安排问题（B ）算法
A分治 B贪心C动态规划 D穷举
52设f(N)g(N)定义正数集正函数果存正常数C然数N0N≥N0时f(N)≤Cg(N)称函数f(N)N充分时界g(N)记作
f(N)∈○(g(N))f(N)阶( A )g(N)阶
A高 B低C等价 D逼
53回溯法解空间树T搜索方式( A )
A深度优先 B广度优先 C耗费优先 D活结点优先
54回溯算法分支限界法问题解空间树会(D)
A序树 B子集树C排列树 D序树
55问题解空间树进行搜索方法中活结点次机会成活结点( B )
A回溯法 B分支限界法C回溯法分支限界法 D回溯法求解子集树问题
56活结点表中选择扩展结点方式导致分支限界法( C )外常见方式
A队列式分支限界法 B优先队列式分支限界法
C栈式分支限界法 DFIFO分支限界法
二 填空题
1算法复杂性 时间 复杂性 空间 复杂性分
2程序 算法 某种程序设计语言具体实现
3算法确定性指组成算法条 指令 清晰歧义
4矩阵连问题算法 动态规划 设计实现
5算法指解决问题 种方法 程
6分治法般设计模式出设计出程序般 递算法
7问题 优子结构性质 该问题动态规划算法贪心算法求解关键特征
8深度优先方式系统搜索问题解算法称 回溯法
9数值概率算法常 数值问题 求解
10计算算法时间复杂度通常计算 循环次数 基操作频率 计算步
11利概率性质计算似值机算法__数值概率算法运行时定概率正确解机算法__蒙特卡罗算法__
12解决01背包问题动态规划回溯法分支限界法中需排序 动态规划 需排序 回溯法 分支限界法
13回溯法进行状态空间树裁剪分支时般两标准：约束条件目标函数界N皇问题01背包问题正两种类型中时约束条件目标函数界进行裁剪 01背包问题 约束条件进行裁剪 N皇问题
14 贪心选择性质 贪心算法行第基素贪心算法动态规划算法区
15矩阵连问题算法 动态规划 设计实现
16贪心算法基素 贪心选择 性质 优子结构 性质
17 动态规划算法基思想求解问题分解成干子问题先求解 子问题 然 子问题 解原问题解
18算法干条指令组成穷序列满足输入 输出 确定性 限性 四条性质
19整数积算法 分治法 设计
20广度优先耗费方式搜索问题解算法称 分支限界法
21 贪心选择性质 贪心算法行第基素贪心算法动态规划算法区
22快速排序算法基 分治策略 种排序算法
23动态规划算法两基素优子结构性质重叠子问题 性质
24回溯法种带 系统性带 跳跃性搜索算法
25分支限界法队列式（FIFO）分支限界法 优先队列式分支限界法
26．分支限界法种带 系统性带 跳跃性 搜索算法
27．回溯法搜索解空间树时常两种剪枝函数约束函数 限界函数
28计算机求解问题需时间 规模 关
29快速排序算法性取决 划分称性
30 Prim算法利贪心策略求解生成树问题时间复杂度 O(n2)
31 图m着色问题 回溯法求解解空间树中叶子结点数 mn 解空间树中结点孩子数 m
三算法填空
1背包问题贪心算法
void Knapsack(int nfloat Mfloat v[]float w[]float x[])
{
Sort(nvw)
int i
for (i1i float cM
for (i1i if (w[i]>c) break
x[i]1
c w[i]
}
if (i}
2子段 动态规划算法
int MaxSum(int n int a[])
{
int sum0 b0 sum存储前b[j] b存储b[j]
for(int j1 j if (b>0) b+ a[j]
else ba[i] 旦某区段负位置累
if(b>sum) sumb
}
return sum
}
3快速排序
template
void QuickSort (Type a[] int p int r)
{
if (p int qPartition(apr)
QuickSort (apq1) 左半段排序
QuickSort (aq+1r) 右半段排序
}
}
4排列问题
Template
void perm(Type list[] int k int m )
{ 产生[list[km]排列
if(km)
{ 剩元素
for (int i0i cout< }
else 元素排列递产生排列
for (int ik i {
swap(list[k]list[i])
perm(listk+1m)
swap(list[k]list[i])
}
}
5定已升序排序n元素a[0n1]现n元素中找出特定元素x
容易设计出二分搜索算法：
template
int BinarySearch(Type a[] const Type& x int l int r)
{
while (l int m ((l+r)2)
if (x a[m]) return m
if (x < a[m]) r m1 else l m+1
}
return 1
}
6合排序描述：
template
void Mergesort(Type a[ ] int left int right)
{
if (leftint i( left+right)2
Mergesort(a left i )
Mergesort(a i+1 right)
Merge(ab leftiright)合数组b
Copy(ab leftright ) 复制数组a
}
}
7计算xm值程
int power ( x m )
{计算xm值返回
y( 1 )im
While(i >0)
yy*x
(return y)
}
四问答题
1计算机求解问题步骤：
1问题分析2数学模型建立3算法设计选择4算法指标5算法分析6算法实现7程序调试8结果整理文档编制
2 算法定义：
算法指解决问题时某种机械步骤定问题结果处理程
3算法三素
（1）操作（2）控制结构（3）数结构
4 算法具5属性：
穷性：算法必须总执行穷步结束步穷时间完成
确定性：算法中条指令必须确切含义存二义性入口出口
行性：算法行算法描述操作通已实现基运算执行限次实现
输入：算法零输入输入取某特定象集合
输出：算法输出输出输入着某特定关系量
5 算法设计质量指标：
正确性：算法应满足具体问题需求
读性：算法应该读利读者程序理解
健壮性：算法应具容错处理输入非法数时算法应作出反应产生莫名妙输出结果
效率存储量需求：效率指算法执行时间存储量需求指算法执行程中需存储空间般两者问题规模关
常采算法迭代法分治法贪婪法动态规划法回溯法分支限界法
6 迭代法
称辗转法种断变量旧值递推出新值解决问题方法
7利迭代算法解决问题需做三方面工作：
1)确定迭代模型迭代算法解决问题中少存直接间接断旧值递推出新值变量变量迭代变量
2)建立迭代关系式谓迭代关系式指变量前值推出值公式（关系）迭代关系式建立解决迭代问题关键通常递推倒推方法完成
3)迭代程进行控制什时候结束迭代程？编写迭代程序必须考虑问题迭代程休止重复执行迭代程控制通常分两种情况：种需迭代次数确定值计算出种需迭代次数法确定前种情况构建固定次数循环实现迭代程控制种情况需进步分析出结束迭代程条件
8分治法基思想：
规模n问题分解k规模较子问题子问题互相独立原问题相递解子问题然子问题解合原问题解
9分治法解决问题般具特征：
（1）该问题规模缩定程度容易解决
（2）该问题分解干规模较相问题该问题具优子结构性质
（3）利该问题分解出子问题解合该问题解
（4）该问题分解出子问题相互独立子问题间包含公子问题
10分治法基步骤
分治法层递三步骤：
（1）分解：原问题分解干规模较相互独立原问题形式相子问题
（2）解决：子问题规模较容易解决直接解否递解子问题
（3）合：子问题解合原问题解
11 动态规划基思想
前文介绍动态规划理前文说具明显阶段划分状态转移方程动态规划称标准动态规划种标准动态规划研究阶段决策问题时推导出具严格数学形式适合理分析实际应中许问题阶段划分明显时果刻意划分阶段法反麻烦般说该问题划分成规模更子问题原问题优解中包含子问题优解（满足优子化原理）考虑动态规划解决
动态规划实质分治思想解决冗余动态规划种问题实例分解更相似子问题存储子问题解避免计算重复子问题解决优化问题算法策略
知动态规划法分治法贪心法类似问题实例纳更相似子问题通求解子问题产生全局优解
贪心法前选择赖已作出选择赖做出选择子问题贪心法顶步步作出贪心选择
分治法中子问题独立（包含公子问题）旦递求出子问题解便子问题解合成问题解
足处：果前选择赖子问题解时难通局部贪心策略达全局优解果子问题独立分治法做许必工作重复解公子问题
解决述问题办法利动态规划该方法应优化问题类问题会种解解值动态规划找出中优（）值解存干取优值解话取中求解程中该方法通求解局部子问题解达全局优解分治法贪心法动态规划允许子问题独立（子问题包含公子问题）允许通身子问题解作出选择该方法子问题解次结果保存起避免次碰时重复计算
动态规划法针问题显著特征应子问题树中子问题呈现量重复动态规划法关键重复出现子问题第次遇时加求解答案保存起遇时直接引必重新求解
12动态规划算法基步骤
设计标准动态规划算法通常步骤进行：
（1）划分阶段：问题时间空间特征问题分干阶段注意干阶段定序者排序（性）否问题法动态规划求解
（2）选择状态：问题发展阶段时处种客观情况状态表示出然状态选择满足效性
（3）确定决策写出状态转移方程：两步放起决策状态转移着天然联系状态转移根阶段状态决策导出阶段状态果确定决策状态转移方程写出事实常常反做根相邻两段状态间关系确定决策
（4）写出规划方程（包括边界条件）：动态规划基方程规划方程通形式化表达式
般说阶段状态决策状态转移确定步较简单动态规划难点理设计旦设计完成实现部分会非常简单根动态规划基方程直接递计算优值般改递推计算实际应中常显式面步骤设计动态规划步骤进行：
（1）分析优解性质刻划结构特征
（2）递定义优值
（3）底方式顶记忆化方法（备忘录法）计算出优值
（4）根计算优值时信息构造优解
步骤（1）～（3）动态规划算法基步骤需求出优值情形步骤（4）省略需求出问题优解必须执行步骤（4）时步骤（3）中计算优值时通常需记录更信息便步骤（4）中根记录信息快速构造出优解
总结：动态规划实际优化问题指原问题实例等价优化问题较实例底求解实例求解存放起存放结果准备数递相递断调子程序求解顶调求解
13 分治法动态规划法相点：
求解问题分解成干子问题先求解子问题然子问题解原问题解
两者点：适合动态规划法求解问题分解子问题互相独立分治法求解问题分解子问题互相独立
14 回溯法
回溯法称试探法该方法首先暂时放弃关问题规模限制问题候选解某种序逐枚举检验发现前候选解解时选择候选解前候选解满足问题规模求外满足求时继续扩前候选解规模继续试探果前候选解满足包括问题规模求时该候选解问题解回溯法中放弃前候选解寻找候选解程称回溯扩前候选解规模继续试探程称前试探
15 分支限界法：
种求解组合优化问题排非解搜索算法类似回溯法分枝定界法搜索解空间时常树形结构组织解空间然回溯法回溯算法深度优先方法搜索树结构分枝定界般宽度优先耗费方法搜索树容易较回溯法分枝定界法异相言分枝定界算法解空间回溯法存容量限时回溯法成功性更
算法思想：分枝限界（branch and bound）种系统搜索解空间方法回溯法区E节点扩充方式活节点仅次机会变成E节点节点变E节点时生成该节点移动步达新节点生成节点中抛弃导出（优）行解节点余节点加入活节点表然表中选择节点作E节点活节点表中取出选择节点进行扩充直找解活动表空扩充程结束
两种常方法选择E节点（然存方法）：
1) 先进先出（F I F O） 活节点表中取出节点序加入节点序相活
节点表性质队列相
2) （优先队列）耗费收益法种模式中节点应耗费收益果查找 具耗费解活节点表堆建立E节点具耗费 活节点果希搜索具收益解堆构造活节点表 E节点具收益活节点
16 分支限界法回溯法相点：种问题解空间树T中搜索问题解算法
点：（1）求解目标
（2）搜索方式
（3）扩展结点扩展方式
（4）存储空间求
17 分治法解决问题般具特征：
（1）该问题规模缩定程度容易解决
（2）该问题分解干规模较相问题该问题具优子结构性质
（3）利该问题分解出子问题解合该问题解
（4）原问题分解出子问题相互独立子问题间包含公子问题
18 分支限界法设计算法步骤：
(1)针问题定义问题解空间（解进行编码）
(2)确定易搜索解空间结构（树图组织解）
(3)广度优先耗费（收益）优先方式搜索解空间搜索程中剪枝函数避免效搜索
19 常见两种分支限界法算法框架：
（1）队列式(FIFO)分支限界法：队列先进先出（FIFO）原选取节点扩展节点
（2）优先队列式分支限界法：优先队列中规定优先级选取优先级高节点成前扩展节点
20 回溯法中常见两类典型解空间树子集树排列树
问题n元素集合S中找出满足某种性质子集时相应解空间树称子集树类子集树通常2n叶结点遍历子集树需O(2n)计算时间
问题确定n元素满足某种性质排列时相应解空间树称排列树类排列树通常n叶结点遍历排列树需O(n)计算时间
21 分支限界法搜索策略：
扩展结点处先生成子结点（分支）然前活结点表中选择扩展结点效选择扩展结点加速搜索进程活结点处计算函数值（限界）根函数值前活结点表中选择利结点作扩展结点搜索着解空间优解分支推进便快找出优解
22 请叙述动态规划算法贪心算法异
点：
需优子结构性质
求优化问题
点：
动态规划：步作选择—赖子问题解
贪心方法：步作选择—赖子问题解
动态规划方法条件：子问题重叠性质
贪心方法条件：优子结构性质贪心选择性质
动态规划：底求解
贪心方法： 顶求解
贪心法时动态规划方法适
动态规划方法时贪心法适
23 请说明动态规划方法什需优子结构性质
答：
优子结构性质指问题优解包含子问题优解
动态规划方法底计算子问题优解先计算子问题优解然利子问题优解构造问题优解需优子结构
24 请说明：
(1)优先队列什数结构实现？
(2)优先队列插入算法基思想？
(3)优先队列插入算法时间复杂度？
答：（1）堆
（2）根堆中元素x插入堆末尾
然元素x关键字双亲关键字较
元素x关键字双亲关键字
元素x双亲交换然元素x新双亲关键字相直元素x关键字双亲关键字元素x根止
（3）O( log n)
25 衡量算法时间效率方法两种？请叙述
答：事前分析法事分析法两种
事分析法：先算法程序设计语言实现然度量程序运行时间
事前分析法：算法时间效率问题规模函数假着问题规模n增长算法执行时间增长率函数f(n)增长率相记作：
T(n)○(f(n))
称T(n)算法渐进时间复杂度简称时间复杂度
26 算法复杂性分析中OΩΘ三记号意义什？忽略常数子情况OΩΘ分提供算法运行时间什界？
答：
果存两正常数cN0N≥N0|f(N)|≤C|g(N)|记作：f(N) O(g(N))时说f(N)阶高g(N)阶
存两正常数C然数N0N ≥ N0时|f(N)|≥C|g(N)|记f(N)Ω(g(N))时说f(N)阶低g(N)阶
果存正常数c1c2n0n≥n0c1|g(N)| ≤|f(N)| ≤ c2|g(N)|
记作 f(N) (g(N))
OΩΘ分提供算法运行时间界界均
五算法设计分析题
1．动态规划策略求解长公子序列问题：
（1）出计算优值递方程
（2）定两序列X{BCDA}Y{ABCB}请采动态规划策略求出长公子序列求出程
答：
(1)
(2)
Ｙ Ａ Ｂ Ｃ Ｂ
Ｘ 0 0 0 0
Ｂ 0 0 1 1 1
Ｃ 0 0 1 2 2
Ｄ 0 0 1 2 2
Ａ 0 1 1 2 2 长公子序列：｛ＢＣ｝
2．列组函数f (n) g (n)确定f (n) O (g (n)) f (n) Ω(g (n))f(n) θ(g(n))简说明理
(1) f(n)2n g(n)n
(2) f(n) g (n)log n2
(3) f(n)100 g(n)log100
(4) f(n)n3 g(n) 3n
(5) f(n)3n g(n)2n
答：
(1) f(n) O(g(n)) g(n)阶f(n)阶高
(2) f(n) Ω(g(n)) g(n)阶f(n)阶低
(3) f(n) θ(g(n)) g(n)f(n)阶
(4) f(n) O(g(n)) g(n)阶f(n)阶高
(5) f(n) Ω(g(n)) g(n)阶f(n)阶低
3．图示连通网络G克鲁斯卡尔(Kruskal)算法求G生成树T请写出算法执行程中次加入T边集TE中边说明该算法贪心策略算法基思想简分析算法时间复杂度
1
2
3
4
5
6
18
11
17
15
19
21
26
6
7
9
答：
TE{(34) (23)(15)（46）（45）}
贪心策略次连接两连通分量边中选权值边
基思想：首先图中顶点放生成树中然次连接两连通分量边中选权值边放入生成树中直生成树中n1条边
时间复杂度：O(eloge)
4 请分治策略设计递排序算法分析时间复杂性（求：分出divideconquercombine三阶段花时间基础列出递方程套公式法求出解渐进阶）
答 ： Template
void MergeSort (Type a[ ] int left int right)
{ if (left { int i（left+right）2
MergeSort（a left i）
MergeSort（a i+1 right）
Merge(a b left right)
Copy(a b left right)
}
}
Divide 阶段时间复杂性： O(1)
Conquer阶段时间复杂性： 2T(n)
Combine阶段时间复杂性： Θ(n)
套公式法：a2 b2 nlog ba n f(n)n f(n)nlog ba 阶
∴T(n) Θ(nlogn)
5设n2k运动员进行循环赛现设计满足求赛日程表
选手必须n1名选手赛次选手天赛次
循环赛短时间完成
(1)（4分）循环赛少需进行( n1 )天
(2)（6分）n238时请画出循环赛日程表
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
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
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
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 2 3 4 5 6 7
7考虑序列A[1n]中找元素问题分治算法描述：果n≤2 直接求解否序列等分成两子序列A[1n2]A[n2+1n]分找出两子序列元素x1y1 x2y2然求出A[1n]元素xmax{x1x2}元素ymin{y1y2}请出该算法计算时间T(n)满足递方程解方程确定算法时间复杂度假定n2k（k 正整数）
答：
算法时间复杂度满足递方程：
T(n)2T(n2)+2（n>2）T(2)1
n2 k（k 正整数）
T(n) T(2 k) 2T(2 k1)+2 22T(2 k2)+ 22+2
2k1T(2)+ 2k2++23+22+2
2k1++23+22+2T(n)Q(n)
8 考虑动态规划方法求解列问题：
01背包数表求：够放入背包价值物品集合
物品
i
重量 wi
价值 vi
承重量 W
1
w12
v112
W5
2
w21
v210
3
w33
v320
4
w42
v415
设： V(i j) —— 前 i 物品中够装入承重量 j 背包中总价值请递推式填写完整：
V(0 j) 0（0物品）V(i 0) 0（承重量0）
V(i j) V(i1 j) 第 i 物品装入 j < wi （超重）
V(i j) max { } j > wi （超重）
i优子集中 i优子集中
底：行列填写表
V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0
2
0
3
0
4
0
答： V(0 j) 0（0物品）V(i 0) 0（承重量0）
V(i j) V(i1 j) 第 i 物品装入 j < wi （超重）
V(i j) max { vi + V(i1jwj) V(i1 j) } j > wi （超重）
i优子集中 i优子集中
V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0
0
12
12
12
12
2
0
10
12
22
22
22
3
0
10
12
22
30
32
4
0
10
15
25
30
37
9请画出回溯法解4皇问题解空间树搜索空间树：
解空间树：
回溯法搜索空间树：
10考虑分支限界解01背包问题
定n种物品背包物品i重量wi价值vi背包容量C问应选择装入背包物品装入背包中物品总价值
示例：n3 C30 w{16 15 15} v{45 25 25}
求：1问题解空间树
2约束条件
2剪枝？
解：
问题解空间树：
约束条件：
剪枝？：
设r前尚未考虑剩余物品价值总Cv前价值bestv前优价值
r＋Cv≤bestv时剪右子树
11请画出回溯法解n301背包问题解空间树三物品重量{20 15 10}价值{20 30 25}背包容量25时搜索空间树
答：
解空间树：
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
2
3
4
5
7
8
11
12
14
15
3
10
6
9
搜索空间树：
1
行解
价值20
价值55
价值30
价值25
价值0
1
1
1
1
0
0
0
0
0
0
1
1
2
8
11
12
14
15
13
10
6
9
算法设计分析复（2015）
考试题型范围
1单选题判断题填空题简答题分析题计算题
2含52似串匹配735
第1章 算法设计分析基础
1 算法概念特征程序区
2 问题问题求解问题求解程（理解问题设计方案实现方案回顾复查）系统生命周期（分析设计编码维护）
3 算法问题求解程（设计表示确认分析）
4 算法特性（正确性简明性效率优性）
5 影响运行时间素（3点）
6 算法复杂度时间复杂度空间复杂度坏均时间复杂度
7 渐进表示法：O记号Ω记号θ记号
8 算法时间复杂度分类：项式时间算法指数时间算法
O(1)O(2n)9 解非递算法时间复杂性分析
点：非递算法时间复杂性分析关键建立代表算法运行时间求表达式然渐进符号表示求表达式
非递算法分析般步骤：
（1） 决定（）参数作算法问题规模度量
（2） 找出算法基语句
（3） 检查基语句执行次数否赖问题规模
（4） 建立基语句执行次数求表达式
（5） 渐进符号表示求表达式
10 常见重问题类型
排序问题查找问题图问题组合问题问题数值问题问题
11 常基数结构
线性结构：栈队列数组
非线性：树图
12 常算法设计方法
数值计算方法：迭代法插值法差分法纳法递推法减半递推技术递法
非数值计算方法：列举法分治法贪心法动态规划法回溯法分支限界法
13 递递算法递设计结构纳证明
第2章 递法
1 递算法特性执行程
2 递推关系—分析算法复杂度
3 计算递推式三种方法：换方法迭代方法方法
4 掌握扩展递技术通分治递推式
扩展递技术：
通分支递式：
第3章 分治法
1设计思想：求解原问题划分成k较规模子问题k子问题分求解果子问题规模然够子问题划分k规模更子问题分解直问题规模足够容易求出解止子问题解合更规模问题解底逐步求出原问题解
2步骤：（1）划分（2）求解子问题（3）合
3分治法代表算法时间复杂度：
排序问题（排序快速排序）O(nlogn)折半查找 O(logn)选择问题O(n)子段O(n3)棋盘覆盖问题O(4k)
第4章 贪心法
1行解优解优量度标准行解判断函数
2设计思想
贪心法解决问题策略目光短浅根前已信息做出局部优选择旦做出选择什结果选择会改变
3贪心法关键决定贪心策略
4贪心法两基素：优子结构性质贪心选择性质
5贪心法解决问题（求优解）：
背包问题活动安排问题机调度问题单源短路径代价生成树两种贪心算法：prim算法kruskal算法
第5章 动态规划法
1设计思想：求解问题分解成干相互重叠子问题子问题应决策程阶段子问题解求解次填入表中需次求解子问题时通查表获该子问题解次求解
2步骤：
（1）刻画优解结构特性
（2）递定义优解值
（3）底方式计算优解
（4）根计算信息构造优解
3两素：优子结构性质子问题重叠性质
4动态规划法解决问题（求优解）：段图问题θ（n+e）结点间短路径O（n3）长公子序列优二叉搜索树O（n3）01背包问题O（2n）流水作业调度O(nlogn)
第6章 回溯法
1 设计思想：解空间树根结点出发深度优先策略遍历解空间树搜索树中结点时先判断该结点应部分解否满足约束条件者否超出目标函数界判断该结点否包含问题（优）解果肯定包含跳该结点根子树搜索谓剪枝（Pruning）否进入该结点根子树继续深度优先策略搜索直搜索叶子结点问题解
2 显约束隐约束解状态约束函数剪枝函数等
3步骤：
（1）针问题定义问题解空间
（2）确定易搜索解空间结构
（3）深度优先方式搜索解空间搜索程中利剪枝函数避免效搜索
解中确定优解
4回溯法解决问题（求解解优解）：
属组合问题排列问题中求优解问题回溯法解决例：八皇问题（4皇问题）01背包问题子集合数图着色问题TSP问题深度优先搜索
第7章 分支限界法
1设计思想：
1）首先确定合理限界函数根限界函数确定目标函数界[down up] 确定限界函数
2）然广度优先策略遍历问题解空间树分支结点次搜索该结点孩子结点分估算孩子结点限界函数取值
3）果某孩子结点限界函数取值超出目标函数界丢弃否加入处理结点表（简称表PT）中
4）次表PT中选取限界函数值极值结点成前扩展结点
5）重复述程直找搜索叶子结点果叶子结点限界函数值极值问题优解否找极值结点重复扩展搜索
2步骤：
确定解空间树
确定限界函数
广度优先搜索解空间树计算限界函数值填入PT表
PT表中寻找极值继续扩展结点直找限界函数值极值叶子结点
3分支限界法解决问题（求优解）：
带时限作业排序TSP问题批处理作业调度问题01背包问题
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
选择题
1二分搜索算法利（ A ）实现算法
A分治策略 B动态规划法 C贪心法 D回溯法
2列动态规划算法基步骤（ A ）
A找出优解性质 B构造优解 C算出优解 D定义优解
3效益优先（ A ）搜索方式
A分支界限法 B动态规划法 C贪心法 D回溯法
4 回溯法解旅行售货员问题时解空间树（ B ）
A子集树 B排列树 C深度优先生成树 D广度优先生成树
5．列算法中通常底方式求解优解（ B ）
A备忘录法B动态规划法 C贪心法 D回溯法
6衡量算法坏标准（C ）
A 运行速度快 B 占空间少 C 时间复杂度低 D 代码短
7分治法求解（D ）
A 棋盘覆盖问题 B 选择问题 C 排序 D 01背包问题
8 实现循环赛日程表利算法（ A ）
A分治策略 B动态规划法 C贪心法 D回溯法
9．面分支界限法搜索方式（ D ）
A广度优先 B耗费优先 C效益优先 D深度优先
10．列算法中通常深度优先方式系统搜索问题解（ D ）
A备忘录法 B动态规划法 C贪心法 D回溯法
11备忘录方法种算法变形（ B ）
A分治法 B动态规划法 C贪心法 D回溯法
12．哈弗曼编码贪心算法需计算时间（ B ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
13．分支限界法解团问题时活结点表组织形式（ B ）
A堆 B堆 C栈 D数组
14．长公子序列算法利算法（ B ）
A分支界限法 B动态规划法 C贪心法 D回溯法
15．实现棋盘覆盖算法利算法（ A ）
A分治法 B动态规划法 C贪心法 D回溯法
16面贪心算法基素（ C ）
A重叠子问题 B构造优解 C贪心选择性质 D定义优解
17回溯法效率赖列素（ D ）
A 满足显约束值数 B 计算约束函数时间
C 计算限界函数时间 D 确定解空间时间
18面种函数回溯法中避免效搜索采取策略（ B ）
A．递函数 B剪枝函数 C机数函数 D搜索函数
19面关NP问题说法正确（B ）
A NP问题解决问题
B P类问题包含NP类问题中
C NP完全问题P类问题子集
D NP类问题包含P类问题中
20蒙特卡罗算法（ B ）种
A分支界限算法 B概率算法 C贪心算法D回溯算法
21（ D ）贪心算法动态规划算法点
A重叠子问题 B构造优解 C贪心选择性质D优子结构性质
22 矩阵连问题算法（ B）设计实现
A分支界限算法 B动态规划算法 C贪心算法 D回溯算法
23 分支限界法解旅行售货员问题时活结点表组织形式（ A ）
A堆 B堆 C栈 D数组
24Strassen矩阵法利（ A ）实现算法
A分治策略 B动态规划法 C贪心法 D回溯法
25分治法求解需满足条件（A ）
A 子问题必须样
B 子问题够重复
C 子问题解合
D 原问题子问题相方法解
26面问题（B ）贪心法解决
A 单源短路径问题 B N皇问题
C 花费生成树问题 D 背包问题
27列算法中解决01背包问题（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
28回溯法搜索状态空间树（C ）序
A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历
29．实现合排序利算法（ A ）
A分治策略 B动态规划法 C贪心法 D回溯法
30．列动态规划算法基素（D ）
A定义优解 B构造优解 C算出优解 D子问题重叠性质
31．列算法中通常底方式求解优解（ B ）
A分治法 B动态规划法 C贪心法 D回溯法
32．采广度优先策略搜索算法（ A ）
A分支界限法 B动态规划法 C贪心法 D回溯法
33合排序算法利（A ）实现算法
A分治策略 B动态规划法 C贪心法 D回溯法
34背包问题贪心算法需计算时间（ B ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
35．实现整数法利算法（C ）
A贪心法 B动态规划法 C分治策略 D回溯法
36．01背包问题回溯算法需计算时间（ A ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
37．采效益优先搜索方式算法（ A ）
A分支界限法 B动态规划法 C贪心法 D回溯法
38．贪心算法动态规划算法区（ B ）
A优子结构 B贪心选择性质 C构造优解 D定义优解
39 实现子段利算法（ B ）
A分治策略 B动态规划法 C贪心法 D回溯法
40优先队列式分支限界法选取扩展结点原（ C ）
A先进先出 B进先出 C结点优先级 D机
41背包问题贪心算法需计算时间（ B ）
AO（n2n）BO（nlogn） CO（2n） DO（n）
42广度优先（ A ）搜索方式
A分支界限法 B动态规划法 C贪心法 D回溯法
43列种算法机化算法（ D ）
A 贪心算法B 回溯法C动态规划算法D舍伍德算法
44 问题动态规划算法贪心算法求解关键特征问题（B ）
A重叠子问题 B优子结构性质 C贪心选择性质 D定义优解
45．采贪心算法优装载问题计算量集装箱重量排序算法时间复杂度 (B )
AO（n2n）BO（nlogn） CO（2n） DO（n）
46 深度优先方式系统搜索问题解算法称( D )
A分支界限算法B概率算法 C贪心算法 D回溯算法
47 实现长公子序列利算法（ B ）
A分治策略B动态规划法 C贪心法 D回溯法
48算法干条指令组成穷序列满足性质（ D）
（1） 输入：0输入
（2） 输出：少输出
（3） 确定性：指令清晰歧义
（4） 限性：指令执行次数限执行时间限
A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)
48函数32n+10nlogn渐进表达式( B )
A 2n B 32n C nlogn D 10nlogn
49整数法算法( A )算法
A分治 B贪心C动态规划 D穷举
50动态规划算法解决字段问题时间复杂性( B )
Alogn Bn Cn2 Dnlogn
51解决活动安排问题（B ）算法
A分治 B贪心C动态规划 D穷举
52设f(N)g(N)定义正数集正函数果存正常数C然数N0N≥N0时f(N)≤Cg(N)称函数f(N)N充分时界g(N)记作
f(N)∈○(g(N))f(N)阶( A )g(N)阶
A高 B低C等价 D逼
53回溯法解空间树T搜索方式( A )
A深度优先 B广度优先 C耗费优先 D活结点优先
54回溯算法分支限界法问题解空间树会(D)
A序树 B子集树C排列树 D序树
55问题解空间树进行搜索方法中活结点次机会成活结点( B )
A回溯法 B分支限界法C回溯法分支限界法 D回溯法求解子集树问题
56活结点表中选择扩展结点方式导致分支限界法( C )外常见方式
A队列式分支限界法 B优先队列式分支限界法
C栈式分支限界法 DFIFO分支限界法
二 填空题
1算法复杂性 时间 复杂性 空间 复杂性分
2程序 算法 某种程序设计语言具体实现
3算法确定性指组成算法条 指令 清晰歧义
4矩阵连问题算法 动态规划 设计实现
5算法指解决问题 种方法 程
6分治法般设计模式出设计出程序般 递算法
7问题 优子结构性质 该问题动态规划算法贪心算法求解关键特征
8深度优先方式系统搜索问题解算法称 回溯法
9数值概率算法常 数值问题 求解
10计算算法时间复杂度通常计算 循环次数 基操作频率 计算步
11利概率性质计算似值机算法__数值概率算法运行时定概率正确解机算法__蒙特卡罗算法__
12解决01背包问题动态规划回溯法分支限界法中需排序 动态规划 需排序 回溯法 分支限界法
13回溯法进行状态空间树裁剪分支时般两标准：约束条件目标函数界N皇问题01背包问题正两种类型中时约束条件目标函数界进行裁剪 01背包问题 约束条件进行裁剪 N皇问题
14 贪心选择性质 贪心算法行第基素贪心算法动态规划算法区
15矩阵连问题算法 动态规划 设计实现
16贪心算法基素 贪心选择 性质 优子结构 性质
17 动态规划算法基思想求解问题分解成干子问题先求解 子问题 然 子问题 解原问题解
18算法干条指令组成穷序列满足输入 输出 确定性 限性 四条性质
19整数积算法 分治法 设计
20广度优先耗费方式搜索问题解算法称 分支限界法
21 贪心选择性质 贪心算法行第基素贪心算法动态规划算法区
22快速排序算法基 分治策略 种排序算法
23动态规划算法两基素优子结构性质重叠子问题 性质
24回溯法种带 系统性带 跳跃性搜索算法
25分支限界法队列式（FIFO）分支限界法 优先队列式分支限界法
26．分支限界法种带 系统性带 跳跃性 搜索算法
27．回溯法搜索解空间树时常两种剪枝函数约束函数 限界函数
28计算机求解问题需时间 规模 关
29快速排序算法性取决 划分称性
30 Prim算法利贪心策略求解生成树问题时间复杂度 O(n2)
31 图m着色问题 回溯法求解解空间树中叶子结点数 mn 解空间树中结点孩子数 m
三算法填空
1背包问题贪心算法
void Knapsack(int nfloat Mfloat v[]float w[]float x[])
{
Sort(nvw)
int i
for (i1i
for (i1i
x[i]1
c w[i]
}
if (i
2子段 动态规划算法
int MaxSum(int n int a[])
{
int sum0 b0 sum存储前b[j] b存储b[j]
for(int j1 j
else ba[i] 旦某区段负位置累
if(b>sum) sumb
}
return sum
}
3快速排序
template
void QuickSort (Type a[] int p int r)
{
if (p
QuickSort (apq1) 左半段排序
QuickSort (aq+1r) 右半段排序
}
}
4排列问题
Template
void perm(Type list[] int k int m )
{ 产生[list[km]排列
if(km)
{ 剩元素
for (int i0i
else 元素排列递产生排列
for (int ik i
swap(list[k]list[i])
perm(listk+1m)
swap(list[k]list[i])
}
}
5定已升序排序n元素a[0n1]现n元素中找出特定元素x
容易设计出二分搜索算法：
template
int BinarySearch(Type a[] const Type& x int l int r)
{
while (l
if (x a[m]) return m
if (x < a[m]) r m1 else l m+1
}
return 1
}
6合排序描述：
template
void Mergesort(Type a[ ] int left int right)
{
if (left
Mergesort(a left i )
Mergesort(a i+1 right)
Merge(ab leftiright)合数组b
Copy(ab leftright ) 复制数组a
}
}
7计算xm值程
int power ( x m )
{计算xm值返回
y( 1 )im
While(i >0)
yy*x
(return y)
}
四问答题
1计算机求解问题步骤：
1问题分析2数学模型建立3算法设计选择4算法指标5算法分析6算法实现7程序调试8结果整理文档编制
2 算法定义：
算法指解决问题时某种机械步骤定问题结果处理程
3算法三素
（1）操作（2）控制结构（3）数结构
4 算法具5属性：
穷性：算法必须总执行穷步结束步穷时间完成
确定性：算法中条指令必须确切含义存二义性入口出口
行性：算法行算法描述操作通已实现基运算执行限次实现
输入：算法零输入输入取某特定象集合
输出：算法输出输出输入着某特定关系量
5 算法设计质量指标：
正确性：算法应满足具体问题需求
读性：算法应该读利读者程序理解
健壮性：算法应具容错处理输入非法数时算法应作出反应产生莫名妙输出结果
效率存储量需求：效率指算法执行时间存储量需求指算法执行程中需存储空间般两者问题规模关
常采算法迭代法分治法贪婪法动态规划法回溯法分支限界法
6 迭代法
称辗转法种断变量旧值递推出新值解决问题方法
7利迭代算法解决问题需做三方面工作：
1)确定迭代模型迭代算法解决问题中少存直接间接断旧值递推出新值变量变量迭代变量
2)建立迭代关系式谓迭代关系式指变量前值推出值公式（关系）迭代关系式建立解决迭代问题关键通常递推倒推方法完成
3)迭代程进行控制什时候结束迭代程？编写迭代程序必须考虑问题迭代程休止重复执行迭代程控制通常分两种情况：种需迭代次数确定值计算出种需迭代次数法确定前种情况构建固定次数循环实现迭代程控制种情况需进步分析出结束迭代程条件
8分治法基思想：
规模n问题分解k规模较子问题子问题互相独立原问题相递解子问题然子问题解合原问题解
9分治法解决问题般具特征：
（1）该问题规模缩定程度容易解决
（2）该问题分解干规模较相问题该问题具优子结构性质
（3）利该问题分解出子问题解合该问题解
（4）该问题分解出子问题相互独立子问题间包含公子问题
10分治法基步骤
分治法层递三步骤：
（1）分解：原问题分解干规模较相互独立原问题形式相子问题
（2）解决：子问题规模较容易解决直接解否递解子问题
（3）合：子问题解合原问题解
11 动态规划基思想
前文介绍动态规划理前文说具明显阶段划分状态转移方程动态规划称标准动态规划种标准动态规划研究阶段决策问题时推导出具严格数学形式适合理分析实际应中许问题阶段划分明显时果刻意划分阶段法反麻烦般说该问题划分成规模更子问题原问题优解中包含子问题优解（满足优子化原理）考虑动态规划解决
动态规划实质分治思想解决冗余动态规划种问题实例分解更相似子问题存储子问题解避免计算重复子问题解决优化问题算法策略
知动态规划法分治法贪心法类似问题实例纳更相似子问题通求解子问题产生全局优解
贪心法前选择赖已作出选择赖做出选择子问题贪心法顶步步作出贪心选择
分治法中子问题独立（包含公子问题）旦递求出子问题解便子问题解合成问题解
足处：果前选择赖子问题解时难通局部贪心策略达全局优解果子问题独立分治法做许必工作重复解公子问题
解决述问题办法利动态规划该方法应优化问题类问题会种解解值动态规划找出中优（）值解存干取优值解话取中求解程中该方法通求解局部子问题解达全局优解分治法贪心法动态规划允许子问题独立（子问题包含公子问题）允许通身子问题解作出选择该方法子问题解次结果保存起避免次碰时重复计算
动态规划法针问题显著特征应子问题树中子问题呈现量重复动态规划法关键重复出现子问题第次遇时加求解答案保存起遇时直接引必重新求解
12动态规划算法基步骤
设计标准动态规划算法通常步骤进行：
（1）划分阶段：问题时间空间特征问题分干阶段注意干阶段定序者排序（性）否问题法动态规划求解
（2）选择状态：问题发展阶段时处种客观情况状态表示出然状态选择满足效性
（3）确定决策写出状态转移方程：两步放起决策状态转移着天然联系状态转移根阶段状态决策导出阶段状态果确定决策状态转移方程写出事实常常反做根相邻两段状态间关系确定决策
（4）写出规划方程（包括边界条件）：动态规划基方程规划方程通形式化表达式
般说阶段状态决策状态转移确定步较简单动态规划难点理设计旦设计完成实现部分会非常简单根动态规划基方程直接递计算优值般改递推计算实际应中常显式面步骤设计动态规划步骤进行：
（1）分析优解性质刻划结构特征
（2）递定义优值
（3）底方式顶记忆化方法（备忘录法）计算出优值
（4）根计算优值时信息构造优解
步骤（1）～（3）动态规划算法基步骤需求出优值情形步骤（4）省略需求出问题优解必须执行步骤（4）时步骤（3）中计算优值时通常需记录更信息便步骤（4）中根记录信息快速构造出优解
总结：动态规划实际优化问题指原问题实例等价优化问题较实例底求解实例求解存放起存放结果准备数递相递断调子程序求解顶调求解
13 分治法动态规划法相点：
求解问题分解成干子问题先求解子问题然子问题解原问题解
两者点：适合动态规划法求解问题分解子问题互相独立分治法求解问题分解子问题互相独立
14 回溯法
回溯法称试探法该方法首先暂时放弃关问题规模限制问题候选解某种序逐枚举检验发现前候选解解时选择候选解前候选解满足问题规模求外满足求时继续扩前候选解规模继续试探果前候选解满足包括问题规模求时该候选解问题解回溯法中放弃前候选解寻找候选解程称回溯扩前候选解规模继续试探程称前试探
15 分支限界法：
种求解组合优化问题排非解搜索算法类似回溯法分枝定界法搜索解空间时常树形结构组织解空间然回溯法回溯算法深度优先方法搜索树结构分枝定界般宽度优先耗费方法搜索树容易较回溯法分枝定界法异相言分枝定界算法解空间回溯法存容量限时回溯法成功性更
算法思想：分枝限界（branch and bound）种系统搜索解空间方法回溯法区E节点扩充方式活节点仅次机会变成E节点节点变E节点时生成该节点移动步达新节点生成节点中抛弃导出（优）行解节点余节点加入活节点表然表中选择节点作E节点活节点表中取出选择节点进行扩充直找解活动表空扩充程结束
两种常方法选择E节点（然存方法）：
1) 先进先出（F I F O） 活节点表中取出节点序加入节点序相活
节点表性质队列相
2) （优先队列）耗费收益法种模式中节点应耗费收益果查找 具耗费解活节点表堆建立E节点具耗费 活节点果希搜索具收益解堆构造活节点表 E节点具收益活节点
16 分支限界法回溯法相点：种问题解空间树T中搜索问题解算法
点：（1）求解目标
（2）搜索方式
（3）扩展结点扩展方式
（4）存储空间求
17 分治法解决问题般具特征：
（1）该问题规模缩定程度容易解决
（2）该问题分解干规模较相问题该问题具优子结构性质
（3）利该问题分解出子问题解合该问题解
（4）原问题分解出子问题相互独立子问题间包含公子问题
18 分支限界法设计算法步骤：
(1)针问题定义问题解空间（解进行编码）
(2)确定易搜索解空间结构（树图组织解）
(3)广度优先耗费（收益）优先方式搜索解空间搜索程中剪枝函数避免效搜索
19 常见两种分支限界法算法框架：
（1）队列式(FIFO)分支限界法：队列先进先出（FIFO）原选取节点扩展节点
（2）优先队列式分支限界法：优先队列中规定优先级选取优先级高节点成前扩展节点
20 回溯法中常见两类典型解空间树子集树排列树
问题n元素集合S中找出满足某种性质子集时相应解空间树称子集树类子集树通常2n叶结点遍历子集树需O(2n)计算时间
问题确定n元素满足某种性质排列时相应解空间树称排列树类排列树通常n叶结点遍历排列树需O(n)计算时间
21 分支限界法搜索策略：
扩展结点处先生成子结点（分支）然前活结点表中选择扩展结点效选择扩展结点加速搜索进程活结点处计算函数值（限界）根函数值前活结点表中选择利结点作扩展结点搜索着解空间优解分支推进便快找出优解
22 请叙述动态规划算法贪心算法异
点：
需优子结构性质
求优化问题
点：
动态规划：步作选择—赖子问题解
贪心方法：步作选择—赖子问题解
动态规划方法条件：子问题重叠性质
贪心方法条件：优子结构性质贪心选择性质
动态规划：底求解
贪心方法： 顶求解
贪心法时动态规划方法适
动态规划方法时贪心法适
23 请说明动态规划方法什需优子结构性质
答：
优子结构性质指问题优解包含子问题优解
动态规划方法底计算子问题优解先计算子问题优解然利子问题优解构造问题优解需优子结构
24 请说明：
(1)优先队列什数结构实现？
(2)优先队列插入算法基思想？
(3)优先队列插入算法时间复杂度？
答：（1）堆
（2）根堆中元素x插入堆末尾
然元素x关键字双亲关键字较
元素x关键字双亲关键字
元素x双亲交换然元素x新双亲关键字相直元素x关键字双亲关键字元素x根止
（3）O( log n)
25 衡量算法时间效率方法两种？请叙述
答：事前分析法事分析法两种
事分析法：先算法程序设计语言实现然度量程序运行时间
事前分析法：算法时间效率问题规模函数假着问题规模n增长算法执行时间增长率函数f(n)增长率相记作：
T(n)○(f(n))
称T(n)算法渐进时间复杂度简称时间复杂度
26 算法复杂性分析中OΩΘ三记号意义什？忽略常数子情况OΩΘ分提供算法运行时间什界？
答：
果存两正常数cN0N≥N0|f(N)|≤C|g(N)|记作：f(N) O(g(N))时说f(N)阶高g(N)阶
存两正常数C然数N0N ≥ N0时|f(N)|≥C|g(N)|记f(N)Ω(g(N))时说f(N)阶低g(N)阶
果存正常数c1c2n0n≥n0c1|g(N)| ≤|f(N)| ≤ c2|g(N)|
记作 f(N) (g(N))
OΩΘ分提供算法运行时间界界均
五算法设计分析题
1．动态规划策略求解长公子序列问题：
（1）出计算优值递方程
（2）定两序列X{BCDA}Y{ABCB}请采动态规划策略求出长公子序列求出程
答：
(1)
(2)
Ｙ Ａ Ｂ Ｃ Ｂ
Ｘ 0 0 0 0
Ｂ 0 0 1 1 1
Ｃ 0 0 1 2 2
Ｄ 0 0 1 2 2
Ａ 0 1 1 2 2 长公子序列：｛ＢＣ｝
2．列组函数f (n) g (n)确定f (n) O (g (n)) f (n) Ω(g (n))f(n) θ(g(n))简说明理
(1) f(n)2n g(n)n
(2) f(n) g (n)log n2
(3) f(n)100 g(n)log100
(4) f(n)n3 g(n) 3n
(5) f(n)3n g(n)2n
答：
(1) f(n) O(g(n)) g(n)阶f(n)阶高
(2) f(n) Ω(g(n)) g(n)阶f(n)阶低
(3) f(n) θ(g(n)) g(n)f(n)阶
(4) f(n) O(g(n)) g(n)阶f(n)阶高
(5) f(n) Ω(g(n)) g(n)阶f(n)阶低
3．图示连通网络G克鲁斯卡尔(Kruskal)算法求G生成树T请写出算法执行程中次加入T边集TE中边说明该算法贪心策略算法基思想简分析算法时间复杂度
1
2
3
4
5
6
18
11
17
15
19
21
26
6
7
9
答：
TE{(34) (23)(15)（46）（45）}
贪心策略次连接两连通分量边中选权值边
基思想：首先图中顶点放生成树中然次连接两连通分量边中选权值边放入生成树中直生成树中n1条边
时间复杂度：O(eloge)
4 请分治策略设计递排序算法分析时间复杂性（求：分出divideconquercombine三阶段花时间基础列出递方程套公式法求出解渐进阶）
答 ： Template
void MergeSort (Type a[ ] int left int right)
{ if (left
MergeSort（a left i）
MergeSort（a i+1 right）
Merge(a b left right)
Copy(a b left right)
}
}
Divide 阶段时间复杂性： O(1)
Conquer阶段时间复杂性： 2T(n)
Combine阶段时间复杂性： Θ(n)
套公式法：a2 b2 nlog ba n f(n)n f(n)nlog ba 阶
∴T(n) Θ(nlogn)
5设n2k运动员进行循环赛现设计满足求赛日程表
选手必须n1名选手赛次选手天赛次
循环赛短时间完成
(1)（4分）循环赛少需进行( n1 )天
(2)（6分）n238时请画出循环赛日程表
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
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
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
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 2 3 4 5 6 7
7考虑序列A[1n]中找元素问题分治算法描述：果n≤2 直接求解否序列等分成两子序列A[1n2]A[n2+1n]分找出两子序列元素x1y1 x2y2然求出A[1n]元素xmax{x1x2}元素ymin{y1y2}请出该算法计算时间T(n)满足递方程解方程确定算法时间复杂度假定n2k（k 正整数）
答：
算法时间复杂度满足递方程：
T(n)2T(n2)+2（n>2）T(2)1
n2 k（k 正整数）
T(n) T(2 k) 2T(2 k1)+2 22T(2 k2)+ 22+2
2k1T(2)+ 2k2++23+22+2
2k1++23+22+2T(n)Q(n)
8 考虑动态规划方法求解列问题：
01背包数表求：够放入背包价值物品集合
物品
i
重量 wi
价值 vi
承重量 W
1
w12
v112
W5
2
w21
v210
3
w33
v320
4
w42
v415
设： V(i j) —— 前 i 物品中够装入承重量 j 背包中总价值请递推式填写完整：
V(0 j) 0（0物品）V(i 0) 0（承重量0）
V(i j) V(i1 j) 第 i 物品装入 j < wi （超重）
V(i j) max { } j > wi （超重）
i优子集中 i优子集中
底：行列填写表
V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0
2
0
3
0
4
0
答： V(0 j) 0（0物品）V(i 0) 0（承重量0）
V(i j) V(i1 j) 第 i 物品装入 j < wi （超重）
V(i j) max { vi + V(i1jwj) V(i1 j) } j > wi （超重）
i优子集中 i优子集中
V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0
0
12
12
12
12
2
0
10
12
22
22
22
3
0
10
12
22
30
32
4
0
10
15
25
30
37
9请画出回溯法解4皇问题解空间树搜索空间树：
解空间树：
回溯法搜索空间树：
10考虑分支限界解01背包问题
定n种物品背包物品i重量wi价值vi背包容量C问应选择装入背包物品装入背包中物品总价值
示例：n3 C30 w{16 15 15} v{45 25 25}
求：1问题解空间树
2约束条件
2剪枝？
解：
问题解空间树：
约束条件：
剪枝？：
设r前尚未考虑剩余物品价值总Cv前价值bestv前优价值
r＋Cv≤bestv时剪右子树
11请画出回溯法解n301背包问题解空间树三物品重量{20 15 10}价值{20 30 25}背包容量25时搜索空间树
答：
解空间树：
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
2
3
4
5
7
8
11
12
14
15
3
10
6
9
搜索空间树：
1
行解
价值20
价值55
价值30
价值25
价值0
1
1
1
1
0
0
0
0
0
0
1
1
2
8
11
12
14
15
13
10
6
9
算法设计分析复（2015）
考试题型范围
1单选题判断题填空题简答题分析题计算题
2含52似串匹配735
第1章 算法设计分析基础
1 算法概念特征程序区
2 问题问题求解问题求解程（理解问题设计方案实现方案回顾复查）系统生命周期（分析设计编码维护）
3 算法问题求解程（设计表示确认分析）
4 算法特性（正确性简明性效率优性）
5 影响运行时间素（3点）
6 算法复杂度时间复杂度空间复杂度坏均时间复杂度
7 渐进表示法：O记号Ω记号θ记号
8 算法时间复杂度分类：项式时间算法指数时间算法
O(1)
点：非递算法时间复杂性分析关键建立代表算法运行时间求表达式然渐进符号表示求表达式
非递算法分析般步骤：
（1） 决定（）参数作算法问题规模度量
（2） 找出算法基语句
（3） 检查基语句执行次数否赖问题规模
（4） 建立基语句执行次数求表达式
（5） 渐进符号表示求表达式
10 常见重问题类型
排序问题查找问题图问题组合问题问题数值问题问题
11 常基数结构
线性结构：栈队列数组
非线性：树图
12 常算法设计方法
数值计算方法：迭代法插值法差分法纳法递推法减半递推技术递法
非数值计算方法：列举法分治法贪心法动态规划法回溯法分支限界法
13 递递算法递设计结构纳证明
第2章 递法
1 递算法特性执行程
2 递推关系—分析算法复杂度
3 计算递推式三种方法：换方法迭代方法方法
4 掌握扩展递技术通分治递推式
扩展递技术：
通分支递式：
第3章 分治法
1设计思想：求解原问题划分成k较规模子问题k子问题分求解果子问题规模然够子问题划分k规模更子问题分解直问题规模足够容易求出解止子问题解合更规模问题解底逐步求出原问题解
2步骤：（1）划分（2）求解子问题（3）合
3分治法代表算法时间复杂度：
排序问题（排序快速排序）O(nlogn)折半查找 O(logn)选择问题O(n)子段O(n3)棋盘覆盖问题O(4k)
第4章 贪心法
1行解优解优量度标准行解判断函数
2设计思想
贪心法解决问题策略目光短浅根前已信息做出局部优选择旦做出选择什结果选择会改变
3贪心法关键决定贪心策略
4贪心法两基素：优子结构性质贪心选择性质
5贪心法解决问题（求优解）：
背包问题活动安排问题机调度问题单源短路径代价生成树两种贪心算法：prim算法kruskal算法
第5章 动态规划法
1设计思想：求解问题分解成干相互重叠子问题子问题应决策程阶段子问题解求解次填入表中需次求解子问题时通查表获该子问题解次求解
2步骤：
（1）刻画优解结构特性
（2）递定义优解值
（3）底方式计算优解
（4）根计算信息构造优解
3两素：优子结构性质子问题重叠性质
4动态规划法解决问题（求优解）：段图问题θ（n+e）结点间短路径O（n3）长公子序列优二叉搜索树O（n3）01背包问题O（2n）流水作业调度O(nlogn)
第6章 回溯法
1 设计思想：解空间树根结点出发深度优先策略遍历解空间树搜索树中结点时先判断该结点应部分解否满足约束条件者否超出目标函数界判断该结点否包含问题（优）解果肯定包含跳该结点根子树搜索谓剪枝（Pruning）否进入该结点根子树继续深度优先策略搜索直搜索叶子结点问题解
2 显约束隐约束解状态约束函数剪枝函数等
3步骤：
（1）针问题定义问题解空间
（2）确定易搜索解空间结构
（3）深度优先方式搜索解空间搜索程中利剪枝函数避免效搜索
解中确定优解
4回溯法解决问题（求解解优解）：
属组合问题排列问题中求优解问题回溯法解决例：八皇问题（4皇问题）01背包问题子集合数图着色问题TSP问题深度优先搜索
第7章 分支限界法
1设计思想：
1）首先确定合理限界函数根限界函数确定目标函数界[down up] 确定限界函数
2）然广度优先策略遍历问题解空间树分支结点次搜索该结点孩子结点分估算孩子结点限界函数取值
3）果某孩子结点限界函数取值超出目标函数界丢弃否加入处理结点表（简称表PT）中
4）次表PT中选取限界函数值极值结点成前扩展结点
5）重复述程直找搜索叶子结点果叶子结点限界函数值极值问题优解否找极值结点重复扩展搜索
2步骤：
确定解空间树
确定限界函数
广度优先搜索解空间树计算限界函数值填入PT表
PT表中寻找极值继续扩展结点直找限界函数值极值叶子结点
3分支限界法解决问题（求优解）：
带时限作业排序TSP问题批处理作业调度问题01背包问题
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档