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

1、第三章蛮力法1. BF算法 课本P37例题，作业P53第1题模式：abcac例如，设主串 s= “ababcabcacbab"模式t= “abcac” 需要6趟 例：主串：ababcabccabcacbabCO BFWft：第第-趟aIIaabII b bNaaXcabbccaabbcccca3b bcca.accbba3bb第三越3baIIabII bcIIcaIIab 耳 ccc3bcacbab第四遇ababTkatabccabcacbab第ababc4abccabcacbab第六趙ababCaIIabII bcIIcc X aabcacbab第七趟3babCab菲acc3bca

2、cbab第丿阖ababcabcXac3bca£bab第加S3babcabccNa3bcacbab第十韻ababcabccabcacbab由此可知，用BF算法一共要进行3+1+詁肚次比较方能匹配岀2. KMP算法 课本P39例题 P53第1题 必须写出next数组的值 例如，设主串 s= “ababcabcacbab"模式 t= “abcac”Next=01112 只需 3 趟例： 主串： ababcabccabcacbab 模式： abcac K、1P算达第一JBababcabccabcacbabII II X a b C第二趙aIIabIIbcIIcaII3第三趙第四趙b

3、 II b baIIabIIbcIIcaII3cIIc由此可知:KMP算法需要3+5+4+1+5=18次比较才能匹配出来。1、选择排序课本P42例题12, 5, 8, 44, 23, 7, 9, 233.1选择排序问题】応用选择排序方法苛一个记亲序列进行升序排列选择排序3"叩5 snri）rrijS4思想址：第I曲排斥在无序F列7 中找到值戢小的记比并和第；亍记 J吐交换作为有序序列的第i牛记处.如图3.6所示.£想法】 3.7 ；f! r 个选择排厲的例子I无用K用方括号括起来J貝体的排序 过申如下：将樂亍记录序列划分対们的丈和无序I心初妬时有序区为空*无序区;V石待排序

4、 的所/门己诫.（2）在无序区找找值晟小的记录將它£无序区的第一个亡录愛换/世符仃序区扩展 个记录同时无用区减少，牛记录，（3）爪断取湮步-腺佗）.底到无序区只剩卜一个记录为止.交换初始序列IJ"37氐呵Ff 牛 1 min无字区G-为无序区的最小记录弟二趙扌IF序结果IS27 6S76491*(鲫融排序培臥13273S1 76651P 1第四趟排*孑:姑果1327JS4916576 1第五翱1伸皓黑13213S4<)6576第越排序姑舉图乱7简单述择川用的过和示例5U.fi简阻选择钏:用的塔本恩想罔解【算法分析】i藝算法的基本语旬是内层循幷体屮的比较iSU（rj&l

5、t;rCiidex：）.K执 行次数为：221 = £1U 咛丄2"曲）r 0 .< PI10-冈此对r任何待排序记录序列选择MF序算法的时同性能都是0（沪儿但是选捋 排序算法记录交换次数最弟为H1次因为外层循坏每执行交换记录的语句站多 只执行一次*从移动尤素的角度讲选择排序算法优于汴彩托他排序算法.2、冒泡排序课本P43例题12, 5, 8, 44, 23, 7, 9, 23.3.2 起泡排序【问题】 应用起泡卅序方法对，个记录序列进行升序誹列，起泡排序（hubhle wrl） 的甚木思恵是：两商比较相邻记录如果反序则疋换直到没仃反序的记录为止.如图3. a 所示.

6、【組法J图给卄ir一个起泡排斥的例f（方暦号括起来的为无斥憾）.4体的排 序过程如卜-：（1）将册个持排序的记录序列划介威有库区利兀序区”初时有序区为空无序區包 括所有待椰斥的记录.（2）对无序X从罚向片依次比牧相邻记晟若反序则龙换从浙使诣值较小的记录向 询就值校大前记录向恬移（像水小的气池*体积大的先浮t来九仁门垂塩执行4）.山列无序区中段有反序的记录.和姑1值序列1 50J5597273K49651mu交搀蔚一趙排序结杲1 n5055273a2965197-_- Ih罕屋 s心b *第二趙排序结杲1 1350273H49 1556597无序区新序区第三掛拌吓第果1 H273N49 1输55

7、fi5971程/鱼/-1已饪位于«终恒遁第四精推序结果13273K495055取5町in 3.a起也排庁的坏以恩恩圈耕1¥1 ：< 9 捏泡排岸过程示例【算法实现】注盘到*隹=趙起泡排序过稈屮.血果冇多14己录交换到城终位就.则 卜一趟起泡排序将不处理这些记录；另外-在一趙屆迥排序过程中-绷果没仃记录相空挽. 则抡叩序列已经f序.算医将终II：" 4泡排序算底请参见£1.1讥【算法少析】鉴忆2.1. 4节.3、TSP 课本P47例题如*对于图3, 13所示无向带权图表给出了川ig力法求解TSP问题的过徨”序号1路径低度是否«短1ti -h

8、C -dr18否2J "b *d T a11是3rbd a234bl F <! *bLI是5a-b -c bfl6；-d *c- *hf ；!la表3,4 蛮力読求解丁SF问题的过程【算法】 蛮力法求解TW'问题与求解盼密顿冋路何题类似*不同的仅是将同路经过 的功上的权值郴加得到和应的路彳冬1毛度JL体算法诸L£：吿【行设汁.【算法井析】蛮力也求解丁百卩问题必须依次考察顶点集的|i斤有金排列.从屮找Jl-r 路彳总氏度短的简单1“1路*冈此.以时间卜界足口5!几4、7-11问题：课本 P54习题3第15题美国有个连锁店叫7-11这个连镇店IU前是每天7点开门，

9、晚上11点关门不过现在是全天24<1、时营业.有一天,有个人来到这个施锁店,买了 4件商品 营业员拿起计算器敲了一下说:总共是$7.11 顾客开玩笑说：所以你们商店就叫7 ?营业员没有理她.说：当然不是,我是把它们的价恪柜乘之后得到的.顾客说：招乘?你应谏把他招加才对口营业员说，我弄错了.接着又算了一遍结果让两个人吃惊的是：计算结果也是$7.11 设计蛮力算法找出四件物品的价格各是什么?#includeviostream.h> void main()int a,b,c,d;for(a=1;av=711;a+)for(b=1;bv=711;b+)for(c=1;c<=711;c

10、+)d=711-a-b-c;if(a*b*c*d=711000000) coutvva/100.0vv't'vvb/100.0vv't'vvc/100.0vv't'vvd/100.0vvendl;return;5、百元买百鸡问题：课本P34例题3.1.2 一个简单的例子百元买百吗问題【问题】 已知公牌止只鞫:彳尤! 小鸡I元二口*川100尤践迟100貝側* 间公鸡、母码、小科各劳少只？【怨法】 设公禺鸡和小鸡的牛数分别为一F*和J则冇如卜方程组成立：j .r T .V -t - = 100口U X i + 3 X V + s ion 0 <

11、 ,j < 2()0 £ V M 330< £ ； inn第3章蛮力法 35则仃尤买白'鸡同题转换为求方樫组的解.应用蜚力法求方程组的解只能依次试探变呈 二和兰的们.验证心片和=的某个扌寺迫值足杳能飾便方程组成立。【算袪】 设变竝工龙小公砌的牛数7表71母鸡的个数=左吓小鸡的个数.注恵到 方用组可能有g个解*需要输出所柑满足乘件的解"设变址tPiml表料上斜的亍数算法川 伪代码描述如下。算J. 1 Z百元淇厅鸡问題喻人：无输出；公屿.时:芒$1)1小鸡的个数L韧蜡化斛的0数1叩=0;L洁环i址发从左)巫&执行下述操柞.氏1術环变赧丫从0

12、：3：5嗽奴执口卜述操作：2. 1. I z= 100 i y ；2. L £mi果 5 * X n * y z/3 71 J' IW.K'J coucii I :输H： xHl z 的值：H】.d y十+i£. 2 X ；s.如柴rwim等ro +则输岀无解信息；【算法分析】 算法乩两层嵌套的循环纽成可以将判等操件:e * % + ：弓* y +打g等F 100>f1：为基本语甸* Jt执行次数为£1X34 = 714,int X, y, z;int tount=0;for (X- 0; x< -20; x+ + )for (y= 0

13、; y< = 33; y+ + >"f*啊个数y的范用是0到33【算法实现】 注fi到小工乌J元三H*则小鸡的牛数应滾是3的倍数.因此.在判断总 价是否满足方穆时要先判斷工是否是3的倍数。rz法用+谣育描述如下；void Chicken (J/x,y和z仆别小爵的牛敕"解的亍&和始化为0"公牛融X的范国是0到20z=100-X- y;if (乞电 m= = 0) &t (5 * Jt+3* y+2/3= IQO) J"渦毘方榨x+ y+ z= 100"满见总价£ 100 jccount+ + ;打解的个数加

14、Iaut"“欝鸭：叫5“ "皓码j叫vy" H小鸡：if (count= = 0cout<< "'问越无解<endl;第四章分治法1归并排序 课本P59例题12, 5, 8, 44, 23, 7, 9, 2归并排序（Merge sort ,台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Con quer ）的一个非常典型的应用。2、快速排序课本P61例题必须画出轴值是谁12, 5, 8, 44, 23, 7, 9, 24.2.2 快達排字為sort)门豐:貲Mlm皿卄仙片序排

15、列快速排序用皿的什淆嚴略灿i卜.皿国L h hlhI 1 r, r.|-J i、»rJ:1均冷'' I 血汁 5- r_ h,11划计：选応卜1心星杵勺轴们轴们打 雕屛将幣f- ff列削分为曲r F lip列厂和 r.g *轴值釦m &划分的过用屮确I疋川I I 前-个f序列屮的记诫均小或尊r他伯帚.,f片:列小的记>A均丸尸戒尊p轴<11 求解何題;分別讨划介G的卸 十子库刿即打处扌甲心存并；山于对子乍列,和匚F"的捋用肚就St屯进彳J的.所L合并不需要 执仃仃何操作"1913i=b 次划分结束1 1913V画卅Jhl 11

16、3535505(>2W1W站HI偵庁列两 13 35 it6195028bfi侧门描n到rLil .23叵1335619b5028N13?5502Kati左侧打描.直到ri)>23W13356丽50284山与dH交换LP口6 35502S右侧扫描.直到ri|<231913雷6 35502K4* 7 一次划分的过程示例17轴们勺U和将口 4 ff r r- J f河创仆y，悶?I f怕M ；1対ht 理.国 r妇电引1松时制J '.1.1 7J il1 !<；S林SOJ w2.Mp如1 ”E1*HI”1351 WftIdNP上Xsofn2.1bsot川1町1屮”川

17、i快世川厅的徂仃讨IV第五章减治法1、折半查找 课本P80例题 写出找记录14的过程71418212329313538424649521| LIIII-:*rpL. . -'Ill ii.ifF'liJ ?!1_：. -|<| ,hy1111 hf .' Imil II：pk丄M '川训mid 山卜.一吩|一丨、汀,r成朴舄y卜门冷比 N1二引 null ；. !|_2 I釘小 :S1 Vk i'弋，：血皿【«朱分析1折半ft找的ae可用«定*来#述«宦谢中的每个蜡点对n有芳字 和卩的 牛记录结点的ffi为该记录在有洋

18、呼列中的ftiL图乳4»出了見盯H i務：匸 的斟逬稠2、选择问题课本P84例题选择下列数字序列中的第3小的元素12, 5, 8, 44, 23, 7, 9, 2右芝兀M 均级何若2.则叫在左半区0B 5.6 i*L三i第六章动态规划法1多段图最短路径问题课本P102例题ms十*-> h4ffrf innHKH,.応馬X君段阳酥爭禹“M耐Si*4<)-wl) W'-*4(«-*2)IWI的子何L札rfCOf l)+cu <fCO,2)+cw)*«ifnl4+ft , _, tirf(Okl)+斑 MCS玄)+曰*<(0.3中#

19、65;；' 昭&2+?,3+4=7GYF芝W!t0,2>+c« JCO,3) +毎pJSi时叫3+rh*l<W£t*S 幽子问有；护5讥2(0+如皿5，$+啊觀切八二詬 «min8+5.7+8,10+6*埠1>心心*厂:； 期FaaK'A用 ?; SI t«d) 雙为16.伪代码：fK%远叫*ZtJ 孟細酣 肚:; *：, . 2弋宀*強-电 沁打林七上：'；：件:;iS副尉越*心"<:.:芦辿W魅W曲磁莊曲:爭左您 沖 谈寒ex"巒骨 忠;百舷UKB 3飞卞卫聂第須亨鶯T跖尬E

20、m护丁厂250显5”门工 gft创阿八 诵IgjiUTT pgftSMs 点 milKX 僧.L 1盘 "剣的耐r人ax警边<s, j>E<*n下述握作，1.1 1 costj=mjncosttiJ+eEiQ) ；1-1*2 patyj>tt«>»CU+<Ci3j3*4*tt ii L2 汁+,監*«»«长度 costCn-13；,PM：舄P鰹;:坟踣辱的珂2、0/1背包问题 课本P114例题有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。

21、»» eul*需 M w#>目忙例蛆1*右'物胡It.iP战仆别上价值分别为逋止皿*6儿育包的容 为山3态规划注求解八'疔包M起的过fV俎I图A. 17所示.I!休过程如F OH , J T 和-.1 tM ； 1. >H, 7H Jru1 ;、片h7 1IIIII馴叫0 ”+ -1I1N1 -IIh*n五1l-r- FniHhihI丿M讨14- 1 ' h- 1卜 11h L1 p0riflJ>jMl J1ri' 6hJ4 |O.L1 1 “.lljifNflJw 1?卄何的止解JUT門 t，. I0flIIh i h&#

22、39;J I:+ I I I . Hn ' M10r.fju14'4JA, af,伸第七章贪心法1背包问题课本P138例题，P146习题七第1题【问】胡花”卜鞫厲和r详W沟的疔也.物品的雨tt堆ir其价值为卞，會 包问Sz"冲h.m S响认掙装，也的扬胡使得装人背包中物晶的总时 醫；Mi ;f伽阴5仙畑将黒种物胡的 M装人葩与.fi獅聖.H和M卄别射. I ，价仇分别为''b J 2门"山祥过”， "-访 邱？-il略卩/厅和們物品相松得的价何汕用二"听示10 202(130.1 ；oUiwm信法】设背包容托为,护、，中问

23、题的解存放存数细:'?品.物品阪笊放住tttHMrf冲.价伉&化 »心川5心法求解卄包桃的算法如厂算法7. 7：贪心法求解背包问題-警驚容肚口如叶畑'物品价值畑出：数组xg匸驚驚蔦用厚心按单付WWW如呗2. 将数组xl.n初始化为<).3. i：()*4. 14.24.3A亠X4. 循环ff到( wi>C)将第i个物品放入背包：応订：1：(' Cwi；I -7-PU6习题71、求如下背包问题的最优解：有7个物品，价值P=(l0,5.15,7,6,183)重量 w=(23.5,7,t4J),背包容量 V=15|(1)按单位重量排序，V数组和利

24、数组分别如下,1=1234567V6101815357W1245137(2) X数组如下，(C为背包的剩余容量，(0同为总价值)i=123456S111112/3C14128320total61634495255.3第八章回溯法1、图着色问题课本P155例题，P169习题8第1题97?存；辭2J - L十宀亠八' ：* 广:£:*»；记低.尸壬E苛WI4() 一个无向H、无向BB'6) 谒匸»8"永n»法虻L：回«法成(图着色问悝揄人：ffl G-< V. E) .E种颜色输岀：n个頂点的涂色悄况血“5-1”将f

25、t组mbrj初始化为门；2. k = y；3. whik ( k '> I'I)乩i依次萼察毎._种颇色.若励点k的着赳Lj苴他顶点的fi色发牛冲突，割转步# : J： 吿则搜索F亠十颜邑；若顶点已全部昇色则输出数绍匚血5一返冋匸S. 3若顶一虫k足育住料色*则k k亠丨.和*9 A处理下一个頂虫：3. 1育则E% 5顶点h的秆色惰况k k h转劈® 3冋瀰：P169习题8第1题对图8.9所示的无向图，使用回溯法求解三着色问题，并画出搜索的解空间树。4图& 9 第I题图2、4皇后问题课本P161搜索过程srn<|SZS- hr,t3QQ(h)eM法求四ftjeRx第九章分支限界法1、任务分配问题课本P182例题，P204习题9第2题楼 任务