算法設計與分析A復習題一、單選題（每小題2分，共計20分。）1．與算法英文單詞algorithm具有相同來源的單詞是（D）。AlogarithmBalgirosCarithmosDalgebra2．從排序過程是否完全在內存中顯示，排序問題可以分為（B）。A穩定排序與不穩定排序B內排序與外排序C直接排序與間接排序D主排序與輔助排序3．下列（D）不是衡量算法的標準。A時間效率B空間效率C問題難度D適應能力4．對于根樹，出度為零的節點為（C）。A0節點B根節點C葉節點D分支節點5．對完全二叉樹自頂向下，從左向右給節點編號，節點編號為１0的父節點編號為（C）。A0B2C4D6二、簡答題（每空8分，共計24分。）1.1．是么是算法，算法與程序有什么區別？算法是一系列解決問題的清晰指令，也就是說，能夠對一定符合規范的輸入，在有限時間內獲得所要求的輸出。程序是算法用某種程序設計語言的具體實現。程序可以不滿足算法的有限性。2.2．貪婪技術的基本思想是什么？它有哪些應用（給出2種）？貪婪算法是在每一步中，“貪婪”地選擇最佳操作，并希望通過一系列局部的最優選擇，能產生一個整個問題的最優解。比如找零問題中總是按面額從大到小的順序找錢幣；背包包問題中總是按價值/重量比從大到小的順序裝物品。三、算法設計題（每題14分，共計56分。）1.給出一個求兩個數的最大公約數的算法。（1）如果n=0，返回m的值作為結果，同時過程結束；否則，轉（2）（4分）（2）用n去除m,將余數賦給r。（5分）（3）將n的值賦給m，將r的值賦給n，返回（1）。（5分）說明：求最大公約數還有其他算法，可參照該方法評分。2.2．（1）用蠻力法求解下圖的最短哈密頓回路。（10分）共有6條路徑（2分），分別為：①a-b-d-c-a長度為：2+3+1+5=11最短哈密頓回路（2分）②a-b-c-d-a長度為：2+8+1+7=18（1分）③a-c-b-d-a長度為：5+8+3+7=23（1分）④a-c-d-b-a長度為：5+1+3+2=11最短哈密頓回路（2分）⑤a-d-b-c-a長度為：7+3+8+5=23（1分）⑥a-d-c-b-a長度為：7+1+8+2=18（1分）（2）為了減少線路條數，可對該算法作何改進？（4分）從（1）可以看到，6條線路可分成3對，每對只是方向不同。我們可以通過定義一條線路方向，使線路條數減半。3對數據表{26，99，20，45，15，29，65，35，20，72}用冒泡法進行排序，給出排序過程（寫出每一趟的結果）。262045152965352072992026152945352065729920152629352045657299152026292035456572991520262029354565729915202026293545657299152020262935456572991520202629354565729915202026293545657299（1-8每步1分，第9步6分）4．對于下圖，用Dijkstra算法求解以a為起點的單源最短路徑。給出求解過程。①從a到b的距離最短，為3。即a-b的最短路徑為a-b，長度為3。（2分）②剩下的路徑中，從a到d的距離最短，為3+2=5。即a-d的最短路徑為a-b-d，長度為5。（4分）③剩下的路徑中，從a到c的距離最短，為3+4=7。即a-c的最短路徑為a-b-c，長度為7。（4分）④剩下的路徑中，從a到e的距離最短，為3+2+4=9。即a-e的最短路徑為a-b-d-e，長度為9。（4分）《算法設計與分析》B復習題一、單選題（每小題2分，共計20分。）1.與算法英文單詞algorithm具有相同來源的單詞是（D）。A.logarithmB.algirosC.arithmosD.algebra2.根據執行算法的計算機指令體系結構，算法可以分為（B）。A.精確算法與近似算法B.串行算法語并行算法C.穩定算法與不穩定算法D.32位算法與64位算法3.具有10個節點的完全二叉樹的高度是（C）。A.6B.5C.3D.24.下列函數關系隨著輸入量增大增加最快的是（D）。Ａ.log2nB.n2C.2nD.n!5.下列程序段的S執行的次數為(D)。fori←0ton-1do forj←0toi-1dos//某種基本操作n2B.n2/2C.n*(n+1)D.n(n+1)/2二、簡答題（每空8分，共計24分。）1.1.分而治之的基本思想是什么？它有哪些應用（給出2種）？分治法的基本思想是：（1將問題的實例劃分為同一個問題的幾個較小的實例（2分）（2）對這些較小的實例求解（2分）（3）合并較小的問題，得到原問題的解（2分）應用：折半查找、合并排序、快速排序、大整數乘法、凸包問題等。（任給2種即可，每種1分）2.2.Prim算法和Kruskal算法的共同點和區別是什么？Prim算法和Kruskal算法都是利用貪心算法求最小生成樹的算法。（4分，貪心和求最小生成樹各2分）Prim算法是從還未加入的頂點中選擇與生成樹中的頂點構成邊，并且邊的權值最小的頂點。（2分）Kruskal算法是從未選擇的邊中選擇不構成回路的邊加入到生成樹中。（2分）三、算法設計題（每題14分，共計56分。）1.1.給出一個求兩個數的最大公約數的算法。（1）如果n=0，返回m的值作為結果，同時過程結束；否則，轉（2）（4分）（2）用n去除m,將余數賦給r。（5分）（3）將n的值賦給m，將r的值賦給n，返回（1）。（5分）說明：求最大公約數還有其他算法，可參照該方法評分。2.2.用蠻力法求解下列背包問題。物品重量價值1742231234404525背包的承重量等于10子集總重量價值Φ00{1}742{2}312{3}440{4}525{1,2}1054{1,3}11不可行{1,4}12不可行{2,3}752{2,4}837{3,4}965{1,2,3}14不可行{1,2,4}15不可行{1,3,4}16不可行{2,3,4}12不可行{1,2,3,4}19不可行（每行0.5分）最優的選擇是{3,4}，價值是65.（6分）33.對數據表{37，89，20，46，17，26，67，33，10，82}用插入排序進行排序，給出排序過程（寫出每一趟的結果）26|9920451529653520722699|2045152965352072202699|4515296535207220264599|1529653520721520264599|2965352072152026294599|6535207215202629456599|3520721520262935456599|2072152020262935456599|7215202026293545657299|（1-9每步1分，第10步5分）4．4.對于下圖，用Dijkstra算法求解以a為起點的單源最短路徑。給出求解過程。