华南理工大学广州学院算法设计与分析期末考试复习

复习考试题型：选择题（算法类型、时间复杂度，共15题，30分）简答题（设计思想，共2题，12分）应用题（解题步骤、搜索空间树等，共4题，48分）编程题（上机实验题，作业题等，共1题，10分）复习2023/9/1复习Page32023/9/1Page3算法的几种描述方法（重点掌握伪代码和C++语言，会使用伪代码写算法）；理解大O符号的含义；算法的几个重要特性：输入、输出、有穷性、确定性、可行性。第一章、第二章⑴自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想

注意事项：避免写成自然段算法的几种描述方法（重点掌握伪代码和C++语言，会使用伪代码写算法）；⑵流程图

优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次⑶程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：尽量将算法写成子函数⑷伪代码——算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解理解大O符号的含义；时间复杂度算法的五大特性：2023/9/1第1章算法设计基础Page9输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。算法的有穷性意味着不是所有的计算机程序都是算法.确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现（每步可执行）。2023/9/1复习Page102023/9/1Page10蛮力法的基本思想（重要！）:蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;关键——依次处理所有元素。第三章蛮力法2023/9/1复习Page112023/9/1Page11熟记哪些问题使用了蛮力法进行解决：顺序查找、串匹配（KMP,BM,BF），选择排序，冒泡排序，生成排列对象，生成子集，0/1背包，任务分配，哈密顿回路，TSP，最近对问题，凸包问题，7-11问题，百钱买百鸡问题；并熟记这些问题的时间复杂度；第三章蛮力法2023/9/1复习Page122023/9/1Page12其中：BF：依次扫描，对比，O(n+m)；KMP：依次扫描，对比（虽然这个“依次”已经是按照一定的规律，效率较高），O(n+m)，注意：对于KMP算法，必须求出next数组；选择排序：扫描整个序列，找到整个序列的最小记录和序列中的第一个记录交换位置，再扫第二小，依此类推…，O(n2)；第三章蛮力法2023/9/1复习Page132023/9/1Page13其中：冒泡排序：扫描整个序列，在扫描过程中两两比较相邻记录，如果反序则交换，直到n-1趟扫描后，即排好序，O(n2)

；TSP：把所有可能的回路都找出来，就可以得到最短路径，O(n!)；7-11：把所有可能都计算一遍，就能得到正确的解；百钱买百鸡：把所有可能都计算一遍，就能得到正确的解。第三章蛮力法2023/9/1复习Page142023/9/1Page14冒泡排序、选择排序、TSP问题的设计思想和伪代码（可能出简答题）7-11问题、百钱买百鸡问题的代码实现（猜测是编程题）第三章蛮力法冒泡排序设计思想选择排序设计思想TSP问题设计思想

TSP问题：旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。8abdc23571序号路径路径长度是否最短1a→b→c→d→a18

否2a→b→d→c→a11

是3a→c→b→d→a23

否4a→c→d→b→a11

是5a→d→b→c→a23

否6a→d→c→b→a18

否

注意到，在图中有3对不同的路径，对每对路径来说，不同的只是路径的方向，因此，可以将这个数量减半，则可能的解有(n-1)!/2个。这是一个非常大的数，随着n的增长，TSP问题的可能解也在迅速地增长。用蛮力法求解TSP问题，其时间复杂性为O(n!)，只能解决问题规模很小的实例。一个简单的例子——百元买百鸡问题已知公鸡5元一只，母鸡3元一只，小鸡1元三只，用100元钱买100只鸡，问公鸡、母鸡、小鸡各多少只？voidchicken(){intx,y,z;for(x=0;x<=20;x++){for(y=0;y<=33;y++){z=100-x-y; if((z%3==0)&&(5*x+3*y+z/3==100)){cout<<"公鸡:"<<x<<"母鸡:"<<y<<"小鸡:"<<z<<endl;}}}}（编程，代码要记牢）7-11问题（编程，代码要记牢）设计蛮力算法找出四件物品的价格各是什么？

#include<iostream.h>voidmain(){ inta,b,c,d; for(a=1;a<=711;a++){ for(b=1;b<=711;b++){ for(c=1;c<=711;c++){ d=711-a-b-c; if(a*b*c*d==711){ cout<<a/100.0<<'\t'<<b/100.0<<'\t'<<c/100.0<<'\t'<<d/100.0<<endl; return; } } } }2023/9/1复习Page222023/9/1Page22分治法的基本思想（重要！自底向上，理解+应用）：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。步骤：（1）划分

（2）求解子问题

（3）合并第四章分治法2023/9/1复习Page232023/9/1Page23分治法的基本思想（自底向上，理解+应用）：第四章分治法

子问题1的规模是n/2

子问题1的解

子问题2的解

子问题2的规模是n/2

原问题的解

原问题的规模是n2023/9/1复习Page242023/9/1Page24熟记哪些问题使用了分治法进行解决：归并排序，快速排序，最大子段和，棋盘覆盖，循环赛日程安排，最近对问题，凸包问题；并熟记这些问题的时间复杂度：第四章分治法2023/9/1复习Page252023/9/1Page25其中：归并排序：划分成等长子序列

分别对两子序列归并排序

将排完的有序子序列合并成一个有序序列，O(nlog2n)；快速排序：用一个轴值划分成两个子序列

分别对两个子序列递归地快速排序，O(nlog2n)；最大子段和：划分成等长子序列

针对3种情况分别处理求子序列最大子段和

合并3种情况下的最大子段和，O(nlog2n)。第四章分治法2023/9/1复习Page262023/9/1Page26归并排序、快速排序、最大子段和问题的设计思想和伪代码；（可能出简答题）用快速排序和归并排序算法对数字序列排序。第四章分治法归并排序设计思想

二路归并排序的分治策略是：（1）划分：将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；（3）合并：将这两个有序子序列合并成一个有序序列。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性为O(n)。

r1……rn/2

rn/2＋1……rn

划分r‘1<……<r’n/2r’n/2＋1<……<r’n

递归处理r''1<……<r''n/2<r''n/2＋1<……<r''n

合并解

r1……rn/2

rn/2＋1……rn

划分r‘1<……<r’n/2r’n/2＋1<……<r’n

递归处理r''1<……<r''n/2<r''n/2＋1<……<r''n

合并解

快速排序设计思想以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；（2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若i＜j，则将基准记录与j指向的记录进行交换；（3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若i＜j，则将基准记录与i指向的记录交换；（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。最大子段和问题设计思想复习减治法的基本思想（理解+应用）：原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。熟记哪些问题使用了减治法进行解决：折半查找，二叉树查找，插入排序，堆排序，选择问题，淘汰赛冠军问题，假币问题（8枚硬币不知道假币轻重）；并熟记这些问题的时间复杂度：第五章减治法2023/9/1复习Page332023/9/1Page33其中：折半查找：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找，O(log2n)。插入排序：依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到全部记录都排好序，O(n2)第五章减治法2023/9/1复习Page342023/9/1Page34其中：选择问题：考虑快速排序中的划分过程，选定一个轴值将序列ri

～rj进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则：（1）若k=s，则rs就是第k小元素；（2）若k<s，则第k小元素一定在轴值前半区中；（3）若k>s，则第k小元素一定在轴值后半区中；第五章减治法2023/9/1复习Page352023/9/1Page35其中：假币问题（8枚硬币不知道假币轻重）：从八枚硬币中任取六枚a，b，c，d，e，f，在天平两端各放三枚进行比较。假设a，b，c三枚放在天平的一端，d，e，f三枚放在天平的另一端，可能出现三种比较结果（再根据三种比较结果进行分析）⑴a＋b＋c>d＋e＋f⑵a＋b＋c＝d＋e＋f⑶a＋b＋c<d＋e＋f第五章减治法2023/9/1复习Page362023/9/1Page36折半查找问题的设计思想和伪代码（可能出简答题）给一个数字序列，要求采用折半查找，找某个数，写出求解的过程。第五章减治法折半查找问题设计思想在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

[r1………rmid-1]rmid[rmid+1………rn]（mid=(1+n)/2）如果k<rmid查找这里如果k>rmid查找这里

k2023/9/1第5章减治法Page38例：查找值为14的记录的过程：

0123456789101112137141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14查找成功！选择下列数字序列中的第3小的元素12,5,8,44,23,7,9,22023/9/1复习Page402023/9/1Page40动态规划法的基本思想（重要！自底向上，理解+应用）：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。第六章动态规划法2023/9/1复习Page412023/9/1Page41动态规划法的求解过程：分成相互重叠的子问题；求解子问题，填表；自底向上计算出原问题的解。第六章动态规划法2023/9/1复习Page422023/9/1Page42熟记哪些问题使用了动态规划法进行解决：TSP，多段图的最短路径问题，0/1背包，最长公共子序列问题，最优二叉查找树，近似串匹配问题；并熟记这些问题的时间复杂度：多段图的最短路径问题：O(n+m)0/1背包问题：O(n×C)第六章动态规划法2023/9/1第6章动态规划法Page432120345678949387684756866537

一个多段图用动态规划法解决多段图的最短路径问题，写出求解过程（可能出应用题）第六章动态规划法2023/9/1第6章动态规划法Page45

根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。

实例：有5个物品，其重量分别是{2,2,6,5,4}，价值分别为{6,3,5,4,6}，背包的容量为10。

012345678910

0w1=2v1=61w2=2v2=32w3=6v3=53w4=5v4=44w5=4v5=65000000000000000006666666660669999999066999911111406699910111314066991212151515x5=1x4=0x3=0x2=1x1=1用动态规划法解决0/1背包问题，写出求解过程。（可能出应用题）物品容量2023/9/1复习Page462023/9/1Page46贪心法的基本思想（重要！局部最优，理解+应用）：贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。第七章贪心法2023/9/1复习Page472023/9/1Page47熟记哪些问题使用了贪心法进行解决：TSP，图着色问题，最小生成树问题（Prim算法、Kruskal算法），背包问题，活动安排问题，多机调度问题，哈弗曼编码；并熟记这些问题的时间复杂度：第七章贪心法2023/9/1复习Page482023/9/1Page48其中：背包问题：每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，O(nlog2n)。注意：背包问题要求装满整个背包，最后一个物体若装不下一个整体，可以装其中的一部分。第七章贪心法2023/9/1复习Page492023/9/1Page49背包问题的贪心算法设计思想和伪代码；给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?4.用贪心法解决背包问题，写出求解过程（第7章作业：先按单位价值重量比排序，再依次放置物品，最后求出总价值，写出）（可能出应用题）第七章贪心法背包问题（可能出简答题）设计思想有三种看似合理的贪心策略：（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。2023/9/1第7章贪心法Page51

12050背包180190200(a)三个物品及背包(b)贪心策略1(c)贪心策略2(d)贪心策略350301020203020/30201010/203010例如，有3个物品，其重量分别是{20,30,10}，价值分别为{60,120,50}，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。2023/9/1复习Page532023/9/1Page53回溯法的基本思想（深度优先搜索，理解+应用）：从根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。第八章回溯法2023/9/1复习Page542023/9/1Page54熟记哪些问题使用了回溯法进行解决：图m着色问题，哈密顿回路问题，八皇后问题（4皇后问题），批处理作业调度问题；第八章回溯法3.用回溯法解决m颜色图着色问题，画出搜索空间图；

（可能出应用题）

图的m着色问题描述为：给定无向连通图G=(V,E)和正整数m，判断能否用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。

D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a)一个无向图(b)回溯法搜索空间图8.8回溯法求解图着色问题示例4.画出用回溯法求解8皇后或4皇后问题的搜索过程（课本P161）

（可能出应用题）

八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。回溯法求解4皇后问题的搜索过程2023/9/1复习Page572023/9/1Page57分支限界法的基本思想：首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]；按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值；如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点；重复上述过程，直到找到最优解。第九章分支限界法2023/9/1复习Page582023/9/1Page58分支限界法的基本思想：

⑥当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；

⑦否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。第九章分支限界法2023/9/1复习Page592023/9/1Page59熟记哪些问题使用了分支限界法进行解决：TSP，多段图的最短路径问题，任务分配问题，批处理作业调度问题，0/1背包；并熟记这些问题的时间复杂度；用分支限界法解决任务分配问题，画出搜索空间。（可能出应用题）用分支限界法解决0/1背包问题，画出搜索空间。（可能出应用题）第九章分支限界法2023/9/1第9章分支限界法Page60任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图9.10所示是一个任务分配的成本矩阵。

C＝9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d图9.10任务分配问题的成本矩阵任务分配问题（可能出应用题）

2023/9/1第9章分支限界法Page61求最优分配成本的上界和下界考虑任意一个可行解，例如：矩阵中的对角线是一个合法的选择，表示将任务1分配给人员a、任务2分配给人员b、任务3分配给人员c、任务4分配给人员d，其成本是9+4+1+4=18；或者应用贪心法求得一个近似解：将任务2分配给人员a、任务3分配给人员b、任务1分配给人员c、任务4分配给人员d，其成本是2+3+5+4=14。显然，14是一个更好的上界。为了获得下界，考虑人员a执行所有任务的最小代价是2，人员b执行所有任务的最小代价是3，人员c执行所有任务的最小代价是1，人员d执行所有任务的最小代价是4。因此，将每一行的最小元素加起来就得到解的下界，其成本是2+3+1+4=10。需要强调的是，这个解并不是一个合法的选择（3和1来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是[10,14]之间的某个值。2023/9/1第9章分支限界法Page62图9.11分支限界法求解任务分配问题示例(×表示该结点被丢弃，结点上方的数组表示搜索顺序)4→alb=16104×startlb=101→alb=172→alb=103→alb=151→blb=133→blb=104→blb=141→clb=144→clb=174→clb=203→clb=134→dlb=1323567891213111××××搜索空间分支限界法求解0/1背包问题（可能出应用题）

例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)1440102742635255431242023/9/1第9章分支限界法Page64

应