2014华广算法设计与分析期末考试复习题目.docVIP

第三章 蛮力法 1.BF算法 课本P37例题，作业P53 第1题 例如，设主串s=“ababcabcacbab”，模式t=“abcac” 需要6趟 例：主串：ababcabccabcacbab 模式：abcac 2.KMP算法 课本P39例题 P53 第1题 必须写出next数组的值 例如，设主串s=“ababcabcacbab”，模式t=“abcac” Next=01112 只需3趟 例：主串：ababcabccabcacbab 模式：abcac 由此可知：KMP算法需要3+5+4+1+5=18次比较才能匹配出来。 选择排序 课本P42例题 12, 5, 8, 44, 23, 7, 9, 2 冒泡排序 课本P43例题 12, 5, 8, 44, 23, 7, 9, 2 TSP 课本P47例题 7-11问题：课本P54习题3第15题 设计蛮力算法找出四件物品的价格各是什么？ #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==711000000){ couta/100.0\tb/100.0\tc/100.0\td/100.0endl; return; } } } } 百元买百鸡问题：课本P34例题 第四章 分治法 1、归并排序 课本P59例题 12, 5, 8, 44, 23, 7, 9, 2 归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 第五章 减治法 1、折半查找 课本P80例题 写出找记录14的过程 7 14 18 21 23 29 31 35 38 42 46 49 52 2、选择问题 课本P84例题 选择下列数字序列中的第3小的元素 12, 5, 8, 44, 23, 7, 9, 2 第六章 动态规划法 1、多段图最短路径问题 课本P102例题 伪代码： 2、0/1背包问题 课本P114例题 有5个物品，其重量分别是{2, 2, 6, 5, 4}，价值分别为{6, 3, 5, 4, 6}，背包的容量为10。 第七章 贪心法 1、背包问题 课本P138例题，P146习题七第1题 第八章 回溯法 1、图着色问题 课本P155例题，P169 习题8第1题 P169 习题8第1题 对图8.9所示的无向图，使用回溯法求解三着色问题，并画出有哪些信誉好的足球投注网站的解空间树。 2、4皇后问题 课本P161 有哪些信誉好的足球投注网站过程 第九章 分支限界法 1、任务分配问题 课本P182例题，P204 习题9第2题 2、0/1背包问题 课本P180例题，P204习题9第3题