前言
大家好吖，欢迎来到 YY 滴算法不挂科系列 ，热烈欢迎！ 本章主要内容面向接触过C++的老铁
一.选择题1、衡量一个算法好坏的标准是（ ）。A、运⾏速度快
B、占⽤空间少
C、时间复杂度低
D、代码短
C2、在下列算法中有时找不到问题解的是（ ）。A、蒙特卡罗算法
B、拉斯维加斯算法
C、舍伍德算法
D、数值概率算法
B拉斯维加斯算法有时成功有时失败3.下列随机算法中运行时有时候成功有时候失败的是（）A、数值概率算法
B、舍伍德算法
C、拉斯维加斯算法
D、蒙特卡罗算法
C4.下列哪⼀种算法是随机化算法（ ）A. 贪⼼算法
B. 回溯法
C.动态规划算法
D.舍伍德算法
D5.蒙特卡罗算法是（ ）的⼀种。A、分⽀界限算法
B、概率算法
C、贪⼼算法
D、回溯算法
B利用概率的性质计算近似值的随机算法是（数值概率算法），运行时以一定的概率得到正确解的随机算法是（蒙特卡罗算法）。6.下列哪一种算法不是随机化算法（ ）A. 蒙特卡罗算法
B. 拉斯维加斯算法
C.动态规划算法
D.舍伍德算法
C7.设f(N),g(N)是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时有上界g(N),记作f(N)=O(g(N)),即f(N)的阶( )g(N)的阶.A.不⾼于
B.不低于
C.等价于
D.逼近
A对比在这里插入图片描述8. 算法是由若干条指令组成的有穷序列，而且满足以下性质（ ）（1） 输⼊：有0个或多个输入（2） 输出：至少有⼀个输出（3） 确定性：指令清晰，无歧义（4） 有限性：指令执行次数有限，而且执行时间有限A .(1)(2)(3)
B.(1)(2)(4)
C.(1)(3)(4)
D.(1)(2)(3)(4)
D9. 函数32n+10nlogn的渐进表达式是( )A. 2n
B. 32n
C. nlogn
D. 10nlogn
B10.下面关于NP问题说法正确的是（ ）A NP问题都是不可能解决的问题
B P类问题包含在NP类问题中
C NP完全问题是P类问题的⼦集
D NP类问题包含在P类问题中
B11.回溯法的效率不依赖于下列哪些因素（ ）A.满⾜显约束的值的个数
B. 计算约束函数的时间
C. 计算限界函数的时间
D. 确定解空间的时间
D12.下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）A.递归函数
B.剪枝函数
C.随机数函数
D.搜索函数
B13. 回溯法解旅行售货员问题时的解空间树是（ ）。A、⼦集树
B、排列树
C、深度优先⽣成树
D、⼴度优先⽣成树
B14.回溯法在解空间树T上的搜索方式是( ).A.深度优先
B.⼴度优先
C.最⼩耗费优先
D.活结点优先
A15.回溯算法和分支限界法的问题的解空间树不会是( ).A.有序树
B.⼦集树
C.排列树
D.⽆序树
D16.0/1背包问题的回溯算法所需的计算时间为（ ）A、O(n*2n)
B、O（nlogn）
C、O（2的n次方）
D、O（n）
A17. 实现最大字段和利用的算法是（ ）。A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
B18.下列算法中通常以自底向上的方式求解最优解的是（ ）。A、备忘录法
B、动态规划法
C、贪⼼法
D、回溯法
B19.下列不是动态规划算法基本步骤的是（ ）。A、找出最优解的性质
B、构造最优解
C、算出最优解
D、定义最优解
A20.最长公共子序列算法利用的算法是（ ）。A、分⽀界限法
B、动态规划法
C、贪⼼法
D、回溯法
B21. 矩阵连乘问题的算法可由（ ）设计实现。A、分⽀界限算法
B、动态规划算法
C、贪⼼算法
D、回溯算法
B22.备忘录方法是哪种算法的变形。（ ）A、分治法
B、动态规划法
C、贪⼼法
D、回溯法
B23.下列是动态规划算法基本要素的是（ ）A、定义最优解
B、构造最优解
C、算出最优解
D、⼦问题重叠性质
D24. ⼀个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ ）。A、重叠⼦问题
B、最优⼦结构性质
C、贪⼼选择性质
D、定义最优解
B25.用动态规划算法解决最大字段和问题，其时间复杂性为( ).A.logn
B.n
C.n2
D.nlogn
B26.以下不可以使用分治法求解的是（ ）。A、棋盘覆盖问题
B、选择问题
C、归并排序
D、0/1背包问题
D01背包问题中的子问题并非完全独立27.实现合并排序利用的算法是（ ）。A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
A28.实现大整数的乘法是利用的算法（ ）。A、贪⼼法
B、动态规划法
C、分治策略
D、回溯法
C29.实现循环赛日程表利用的算法是（ ）。A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
A30.实现棋盘覆盖算法利用的算法是（ ）。A、分治法
B、动态规划法
C、贪⼼法
D、回溯法
A31.二分搜索算法是利用（ ）实现的算法。A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
A32.Strassen矩阵乘法是利用（ ）实现的算法。A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
A33.合并排序算法是利用（ ）实现的算法。A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
A34.使用分治法求解不需要满足的条件是（ ）。A、⼦问题必须是⼀样的
B、⼦问题不能够重复
C、⼦问题的解可以合并
D、原问题和⼦问题使⽤相同的⽅法解
A35.下面问题（ ）不能使用贪心法解决。A、单源最短路径问题
B、N皇后问题
C、最⼩花费⽣成树问题
D、背包问题
BN皇后问题无法使用贪心法有效求解。这是因为贪心法通常依据某种启发式策略，每一步都选择在当前看来最优或最好的选择，而不考虑全局最优解。然而，N皇后问题的关键在于找到一个满足条件的配置，其中N个皇后能够互不攻击地放置在N×N的棋盘上。这个问题要求同时考虑所有皇后的位置，而不仅仅是当前正在放置的皇后。36.下列算法中不能解决0/1背包问题的是（ ）A、贪⼼法
B、动态规划
C、回溯法
D、分⽀限界法
A贪心法通常要求每一步都做出在当前看来最优的选择，并期望这些局部最优选择能够累积成全局最优解。然而，在01背包问题中，选择某个物品是否放入背包不仅取决于该物品本身的价值和重量，还受到其他物品以及背包剩余容量的影响37. （ ）是贪心算法与动态规划算法的共同点。A、重叠⼦问题
B、构造最优解
C、贪⼼选择性质
D、最优⼦结构性质
D38．贪心算法与动态规划算法的主要区别是（ ）。A、最优⼦结构
B、贪⼼选择性质
C、构造最优解
D、定义最优解
B39、解决活动安排问题，最好⽤（ ）算法A.分治
B.贪⼼
C.动态规划
D.穷举
B40．采⽤贪⼼算法的最优装载问题的主要计算量在于将集装箱依其重量从⼩到⼤排序，故算法的时间复杂度为 ( ) 。A、O（n2n）
B、O（nlogn）
C、O（2n）
D、O（n）
B41.背包问题的贪心算法所需的计算时间为（ ）A、O（n×2的n次方）
B、O（nlogn）
C、O（2的n次方）
D、O（n）
B42.哈弗曼编码的贪心算法所需的计算时间为（ ）。A、O（n*2n）
B、O（nlogn）
C、O（2的n次方）
D、O（n）
B43.背包问题的贪心算法所需的计算时间为（ ）。A、O（n*2n）
B、O（nlogn）
C、O（2n）
D、O（n）
B44.回溯算法和分支限界法的问题的解空间树不会是( ).A.有序树
B.⼦集树
C.排列树
D.⽆序树
D45.广度优先是（ ）的一种搜索方式。A、分⽀界限法
B、动态规划法
C、贪⼼法
D、回溯法
A46.下面不是分支界限法搜索方式的是（ ）。A、⼴度优先
B、最⼩耗费优先
C、最⼤效益优先
D、深度优先
D47.最大效益优先是（ ）的一种搜索方式。A、分⽀界限法
B、动态规划法
C、贪⼼法
D、回溯法
A48.优先队列式分⽀限界法选取扩展结点的原则是（ ）。A、先进先出
B、后进先出
C、结点的优先级
D、随机
C49. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ ）。A、最⼩堆
B、最⼤堆
C、栈
D、数组
A50.分支限界法解最大团问题时，活结点表的组织形式是（ ）。A 、最⼩堆
B 、最⼤堆
C 、栈
D、数组
B51.从活结点表中选择下⼀个扩展结点的不同⽅式将导致不同的分⽀限界法,以下除( )之外都是最常⻅的⽅式.A.队列式分⽀限界法
B.优先队列式分⽀限界法
C.栈式分⽀限界法
D.FIFO分⽀限界法
C52.在对问题的解空间树进⾏搜索的⽅法中,⼀个活结点最多有⼀次机会成为活结点的是( ).A.回溯法
B.分⽀限界法
C.回溯法和分⽀限界法
D.回溯法求解⼦集树问题
B53、回溯算法和分⽀限界法的问题的解空间树不会是( ).A.有序树
B.⼦集树
C.排列树
D.⽆序树
D二.填空题1.算法的复杂性有（）复杂性和（）复杂性之分。时间空间2.程序是（）用某种程序设计语言的具体实现。算法3.算法的“确定性”指的是组成算法的每条（）是清晰的，无歧义的。指令4.矩阵连乘问题的算法可由设计实现。动态规划5.拉斯维加斯算法找到的解⼀定是（）。正确解6.算法是指解决问题的（）或 （）。一种方法一个过程7.从分治法的⼀般设计模式可以看出，用它设计出的程序⼀般是（）。递归算法8.问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。最优子结构性质9.以深度优先方式系统搜索问题解的算法称为（） 。回溯算法10.数值概率算法常用于（）的求解。数值问题11.计算⼀个算法时间复杂度通常可以计算（） 、 （） 、或计算步。循环次数基本操作的频率12.利用概率的性质计算近似值的随机算法是（），运行时以一定的概率得到正确解的随机算法是（）。数值概率算法蒙特卡罗算法13.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是（），需要排序的是（） ，（） 。动态规划回溯法分支界限法14.使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是（），只使用约束条件进⾏裁剪的是（）。0/1背包问题N皇后问题15.（）是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择性质注：贪心算法与动态规划算法的重要特征是——最优⼦结构性质16.矩阵连乘问题的算法可由（）设计实现。动态规划17.贪心算法的基本要素是（）和（）性质 。贪心选择性质最优子结构性质18.动态规划算法的两个基本要素是（）性质和 （） 性质。最优字结构重叠子问题19.算法是由若干条指令组成的有穷序列，且要满足（）、 （） 、（）和 （） 四条性质。输入输出确定性有界性20.大整数乘积算法是用（）来设计的。分治法21.以广度优先或以最小耗费方式搜索问题解的算法称为（）。分支界限法25.舍伍德算法总能求得问题的（） 。一个解26.快速排序算法是基于（）的⼀种排序算法。分治策略27. 动态规划算法的基本思想是将待求解问题分解成若干（） ，先求解（） ，然后从这些 （）的解得到原问题的解。子问题子问题子问题28.回溯法是一种既带有（）又带有（）的搜索算法。系统性跳跃性30．分支限界法是一种既带有 （） 又带有 （） 的搜索算法。系统性跳跃性31.分支限界法主要有（） 分支限界法和 （）分支限界法。队列式优先级队列式32.回溯法搜索解空间树时，常用的两种剪枝函数为（）和（） 。约束函数限界函数33.任何可用计算机求解的问题所需的时间都与其（）有关。规模34.快速排序算法的性能取决于（）。划分的对称性35. Prim算法利用（）策略求解 （）问题，其时间复杂度是 （）。贪心最小生成树o（n的2次方）36. 图的m着色问题可用（）法求解，其解空间树中叶子结点个数是 （），解空间树中每个内结点的孩子数是（）。回溯法m的n次方m三.算法填空1.背包问题的贪⼼算法代码语言：javascript代码运行次数：0运行复制void Knapsack(int n, float M, float v[], float w[], float x[])
{
Sort(n, v, w);
int i;
for (i = 1; i <= n; i++)
x[i] = 0;
float c = M;
for (i = 1; i <= n; i++)
{
if (w[i] > c)
break;
x[i] = 1;
c -= w[i];
}
if (i <= n)
x[i] = c / w[i];
}2.最⼤⼦段和: 动态规划算法int MaxSum(int n, int a[])
{
int sum=0, b=0； //sum存储当前最⼤的b[j], b存储b[j]
for(int j=1； j<=n； j++) {
if (b>0) b+= a[j] ；
else b=a[i]; ； //⼀旦某个区段和为负，则从下⼀个位置累和
if(b>sum) sum=b;
}
return sum；
}
3.快速排序代码语言：javascript代码运行次数：0运行复制template
void QuickSort(Type a[], int p, int r)
{
if (p < r) {
int q = Partition(a, p, r);
QuickSort(a, p, q - 1); // 对左半段排序
QuickSort(a, q + 1, r); // 对右半段排序
}
}4.排列问题代码语言：javascript代码运行次数：0运行复制#include
#include
template
void perm(Type list[], int k, int m)
{
// 产生 [list[k:m]] 的所有排列
if (k == m)
{
// 只剩下一个元素，打印排列
for (int i = 0; i <= m; ++i)
std::cout << list[i];
std::cout << std::endl;
}
else
{
// 还有多个元素待排列，递归产生排列
for (int i = k; i <= m; ++i)
{
std::swap(list[k], list[i]); // 交换 list[k] 和 list[i]
perm(list, k + 1, m); // 递归调用 perm 函数
std::swap(list[k], list[i]); // 恢复 list[k] 和 list[i] 的原始顺序（回溯）
}
}
}
int main()
{
// 示例数组
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
// 生成并打印所有排列
perm(arr, 0, n - 1);
return 0;
}5.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出⼀特定元素x。据此容易设计出⼆分搜索算法：代码语言：javascript代码运行次数：0运行复制template
int BinarySearch(Type a[], const Type& x, int l, int r)
{
while (l <= r)
{
// 计算中间索引，注意使用整数除法
// 为了避免 (l + r) 可能的整数溢出，使用 l + (r - l) / 2
int m = l + (r - l) / 2;
if (x == a[m])
{
return m; // 找到元素，返回索引
}
else if (x < a[m])
{
r = m - 1; // 元素在左半部分，更新右边界
}
else
{
l = m + 1; // 元素在右半部分，更新左边界
}
}
return -1; // 未找到元素，返回 -1
}6、合并排序描述如下：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,i,right);//合并到数组b Copy(a,b, left,right ); //复制到数组a } } 7、以下是计算xm的值的过程int power ( x, m ) { //计算xm 的值并返回。 y=( 1 );i=m; While(i- - >0) y=y*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-节点（虽然也可能存在其他的⽅ 法）： 先进先出（F I F O） 即从活节点表中取出节点的顺序与加⼊节点的顺序相 同，因此活 节点表的性质与队列相同。（优先队列）最⼩耗费或最⼤收益法在这种模式中，每个节点都有⼀个对应 的耗费或收益。如果查找 ⼀个具有最⼩耗费的解，则活节点表可⽤最⼩堆来建 ⽴，下⼀个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、Ω、Θ分别提供了算法运⾏时间的什么界？ 答： 如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不⾼于g(N)的阶。 若存在两个正常数C和⾃然数N0，使得当N ≥ N0时有|f(N)|≥C|g(N)|，记为 f(N)=Ω(g(N))。这时我们说f(N)的阶不低于g(N)的阶。 如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)| 则记作 f(N)= (g,(N)) O、Ω、Θ分别提供了算法运⾏时间的上界、下界、平均 27. 概率算法很多算法的每⼀个计算步骤都是固定的，⽽概率算法允许算法在执 ⾏的过程中随机选择下⼀个计算步骤。许多情况下，当算法在执⾏过程中⾯临 ⼀个选择时，随机性选择常⽐最优选择省时。因此概率算法可在很⼤程度上降 低算法的复杂度。 28.概率算法的⼀个基本特征是对所求解问题的同⼀实例⽤同⼀概率算法求解两次可能得到完全不同的 效果。这两次求解问题所需的时间甚⾄所得到的结果可能会有相当⼤的差别。 29．概率算法⼤致分为四类:数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas） 算法和舍伍德（Sherwood）算法。 30.数值概率算法常⽤于数值问题的求解。这类算法所得到的往往是近似解。⽽且近似解的 精度随计算时间的增加不断提⾼。在许多情况下，要计算出问题的精确解是不 可能或没有必要的，因此⽤数值概率算法可得到相当满意的解。 31.蒙特卡罗算法⽤于求问题的准确解。对于许多问题来说，近似解毫⽆意义。例如，⼀个判 定问题其解为“是”或“否”，⼆者必居其⼀，不存在任何近似解答。⼜如，我们 要求⼀个整数的因⼦时所给出的解答必须是准确的，⼀个整数的近似因⼦没有 任何意义。⽤蒙特卡罗算法能求得问题的⼀个解，但这个解未必是正确的。求 得正确解的概率依赖于算法所⽤的时间。算法所⽤的时间越多，得到正确解的 概率就越⾼。蒙特卡罗算法的主要缺点就在于此。⼀般情况下，⽆法有效判断 得到的解是否肯定正确。 32.拉斯维加斯算法不会得到不正确的解，⼀旦⽤拉斯维加斯算法找到⼀个解，那么这个解肯定 是正确的。但是有时候⽤拉斯维加斯算法可能找不到解。与蒙特卡罗算法类 似。拉斯维加斯算法得到正确解的概率随着它⽤的计算时间的增加⽽提⾼。对 于所求解问题的任⼀实例，⽤同⼀拉斯维加斯算法反复对该实例求解⾜够多 次，可使求解失效的概率任意⼩。 33.舍伍德算法总能求得问题的⼀个解，且所求得的解总是正确的。当⼀个确定性算法在最 坏情况下的计算复杂性与其在平均情况下的计算复杂性有较⼤差别时，可以在 这个确定算法中引⼊随机性将它改造成⼀个舍伍德算法，消除或减少问题的好 坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况⾏为，⽽是设 法消除这种最坏⾏为与特定实例之间的关联性。 Θ舍伍德算法 sherwood algorithm 舍伍德算法 ⼀类概率算法的代称。此类算法总能给出所求问题的正确的解。… 当解决某⼀问题的确定性算法的平均情形复杂性⽐最坏情形复杂性低得多时， 通过引⼊随机性来试图减少甚⾄消除“好”、“坏”实体之间这种时间上的差别， 以期望较⼩的运⾏时间。例 …