算法設(shè)計(jì)與分析期末總復(fù)習(xí)VIP

1、復(fù)習(xí)一、簡(jiǎn)答題（每小題5分，選答2題，共10分）1. 什么是算法？試說(shuō)明算法設(shè)計(jì)分析過(guò)程的一般框架和主要步驟。2. 簡(jiǎn)述非遞歸算法時(shí)間效率分析的通用方案。3. 簡(jiǎn)述遞歸算法時(shí)間效率的通用方案。4. 簡(jiǎn)述蠻力法、分治法、減治法，變治法、時(shí)空權(quán)衡、動(dòng)態(tài)規(guī)劃、貪婪技術(shù)、迭代改進(jìn)八種算法設(shè)計(jì)技術(shù)中至少三種技術(shù)基本思想或原理。二、分析題（每小題10分，共20分）1. 考慮下面的算法。P52算法 Mystery(n) /輸入：非負(fù)整數(shù)nS=0for i ß 1 to n doS ß S + i*iReturn Sa. 該算法求的是什么？b. 它的基本操作是什么？c. 該基本操作執(zhí)行了多

2、少次？d. 該算法的效率類型是什么？2. 考慮下面的遞歸算法。P52算法 Secret(A0.n-1) /輸入：包含n個(gè)實(shí)數(shù)的數(shù)組A0.n-1minval ß A0; maxval ß A0for i ß1 to n-1 doif Ai < minvalminval ß AiifAi > maxvalmaxval ß Aireturn maxval minvala. 該算法求的是什么？b. 它的基本操作是什么？c. 該基本操作執(zhí)行了多少次？d. 該算法的效率類型是什么？3. 考慮下面的遞歸算法P59算法 Q(n) /輸入：正整數(shù)if

3、 n=1 return 1else return Q(n-1) + 2*n -1a. 建立該函數(shù)值的遞推關(guān)系并求解，以確定該算法計(jì)算的是什么；b. 建立該算法所做的乘法運(yùn)算次數(shù)的遞推關(guān)系并求解；c. 建立該算法所做的加減運(yùn)算次數(shù)的遞推關(guān)系并求解。三、算法設(shè)計(jì)題（每小題10分，共20分）1. 應(yīng)用快速排序?qū)π蛄蠩，X，A，M，P，L，E按照字母順序排序。并畫出相應(yīng)的遞歸調(diào)用樹。(4章分治法)P1022. 對(duì)于下面的有向圖，應(yīng)用基于DFS的算法來(lái)解拓?fù)渑判騿?wèn)題。(5章減治法)P133.3. 用自底向上算法為列表1, 8, 6, 5, 3, 7, 4進(jìn)行堆排序。(6章變治法)P1754. 應(yīng)用Hor

4、spool算法在下面的文本中查找模式BARBER：BSS_KNER_BARBER (7章時(shí)空權(quán)衡)P201四、計(jì)算題（每小題10分，共20分）1. 對(duì)于輸入30, 20, 56, 75, 31, 19和散列函數(shù)h(K)=K mod 11(7章時(shí)空權(quán)衡)P207a. 構(gòu)造它們的開散列表；b. 求在本表中成功查找的最大鍵值比較次數(shù)；c. 求在本表中成功查找的平均鍵值比較次數(shù)。2. 對(duì)由下面鄰居矩陣定義的有向圖，應(yīng)用Warshall算法求它的傳遞閉包。(8章動(dòng)態(tài)規(guī)劃)P2223. 對(duì)于下面具有權(quán)重矩陣的有向圖，求解完全最短路徑問(wèn)題。(8章動(dòng)態(tài)規(guī)劃)P2234. 應(yīng)用Prim算法或Kruskal算法求下列圖的最小生成樹。(9章貪婪技術(shù))P245五、綜合題（每小題15分，共30分）1. 假設(shè)文本中字符及其出現(xiàn)概率如下表所示(9章貪婪技術(shù))P253字符ABCD-出現(xiàn)概率0.40.10.20.150.15a. 利用上表的數(shù)據(jù)構(gòu)造一套哈夫曼編碼；b. 用a中的編碼對(duì)文本ABACABAD進(jìn)行編碼；c.2. 用單純形法解下列線性規(guī)劃問(wèn)題(10章迭代改進(jìn))P249最大化： 3x+5y約束： x