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

理解大O符号的含义；时间复杂度 冒泡排序 设计思想 选择排序 设计思想 TSP问题 设计思想 7-11问题（编程，代码要记牢） 设计蛮力算法找出四件物品的价格各是什么？ #includeiostream.h void main() { int a,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){ couta/100.0\tb/100.0\tc/100.0\td/100.0endl; return; } } } } 归并排序 设计思想 快速排序 设计思想 最大子段和问题 设计思想 折半查找问题 设计思想 在有序表中，取中间记录作为比较对象， 若给定值与中间记录的关键码相等，则查找成功； 若给定值小于中间记录的关键码，则在中间记录的左半区继 续查找； 若给定值大于中间记录的关键码，则在中间记录的右半区继 续查找。不断重复上述过程，直到查找成功，或所查找的区 域无记录，查找失败。 选择下列数字序列中的第3小的元素 12, 5, 8, 44, 23, 7, 9, 2 背包问题（可能出简答题） 设计思想 有三种看似合理的贪心策略： （1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。 （2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。 （3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。 3.用回溯法解决m颜色图着色问题，画出有哪些信誉好的足球投注网站空间图；（可能出应用题）图的m着色问题描述为：给定无向连通图G=(V, E)和正整数m，判断能否用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。 4.画出用回溯法求解8皇后或4皇后问题的有哪些信誉好的足球投注网站过程（课本P161）（可能出应用题） 八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。 分支限界法求解0/1背包问题（可能出应用题） 以第一个记录作为轴值，对待排序序列进行划分的过程为： （1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间； （2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若i＜j，则将基准记录与j指向的记录进行交换； （3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若i＜j，则将基准记录与i指向的记录交换； （4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。 复习 减治法的基本思想（理解+应用）： 原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。 熟记哪些问题使用了减治法进行解决：折半查找，二叉树查找，插入排序，堆排序，选择问题，淘汰赛冠军问题，假币问题（8枚硬币不知道假币轻重）；并熟记这些问题的时间复杂度： 第五章 减治法 * 复习 Page * * Page * 其中： 折半查找：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找，O(log2n)。 插入排序：依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到全部记录都排好序，O(n2) 第五章 减治法 * 复习 Page * * Page * 其中： 选择问题：考虑快速排序中的划分过程，选定一个轴值将序列ri ～ rj进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则： （1）若k=s，则rs就是第k小元素； （2）若ks，则第k小元素一定在轴值前半区中； （3）若ks，则第