下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
算法設(shè)計與分析A復(fù)習(xí)題一、單選題(每小題2分,共計20分。)1.與算法英文單詞algorithm具有相同來源的單詞是(D)。AlogarithmBalgirosCarithmosDalgebra2.從排序過程是否完全在內(nèi)存中顯示,排序問題可以分為(B)。A穩(wěn)定排序與不穩(wěn)定排序B內(nèi)排序與外排序C直接排序與間接排序D主排序與輔助排序3.下列(D)不是衡量算法的標準。A時間效率B空間效率C問題難度D適應(yīng)能力4.對于根樹,出度為零的節(jié)點為(C)。A0節(jié)點B根節(jié)點C葉節(jié)點D分支節(jié)點5.對完全二叉樹自頂向下,從左向右給節(jié)點編號,節(jié)點編號為10的父節(jié)點編號為(C)。A0B2C4D6二、簡答題(每空8分,共計24分。)1.1.是么是算法,算法與程序有什么區(qū)別?算法是一系列解決問題的清晰指令,也就是說,能夠?qū)σ欢ǚ弦?guī)范的輸入,在有限時間內(nèi)獲得所要求的輸出。程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。程序可以不滿足算法的有限性。2.2.貪婪技術(shù)的基本思想是什么?它有哪些應(yīng)用(給出2種)?貪婪算法是在每一步中,“貪婪”地選擇最佳操作,并希望通過一系列局部的最優(yōu)選擇,能產(chǎn)生一個整個問題的最優(yōu)解。比如找零問題中總是按面額從大到小的順序找錢幣;背包包問題中總是按價值/重量比從大到小的順序裝物品。三、算法設(shè)計題(每題14分,共計56分。)1.給出一個求兩個數(shù)的最大公約數(shù)的算法。(1)如果n=0,返回m的值作為結(jié)果,同時過程結(jié)束;否則,轉(zhuǎn)(2)(4分)(2)用n去除m,將余數(shù)賦給r。(5分)(3)將n的值賦給m,將r的值賦給n,返回(1)。(5分)說明:求最大公約數(shù)還有其他算法,可參照該方法評分。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)為了減少線路條數(shù),可對該算法作何改進?(4分)從(1)可以看到,6條線路可分成3對,每對只是方向不同。我們可以通過定義一條線路方向,使線路條數(shù)減半。3對數(shù)據(jù)表{26,99,20,45,15,29,65,35,20,72}用冒泡法進行排序,給出排序過程(寫出每一趟的結(jié)果)。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分)《算法設(shè)計與分析》B復(fù)習(xí)題一、單選題(每小題2分,共計20分。)1.與算法英文單詞algorithm具有相同來源的單詞是(D)。A.logarithmB.algirosC.arithmosD.algebra2.根據(jù)執(zhí)行算法的計算機指令體系結(jié)構(gòu),算法可以分為(B)。A.精確算法與近似算法B.串行算法語并行算法C.穩(wěn)定算法與不穩(wěn)定算法D.32位算法與64位算法3.具有10個節(jié)點的完全二叉樹的高度是(C)。A.6B.5C.3D.24.下列函數(shù)關(guān)系隨著輸入量增大增加最快的是(D)。A.log2nB.n2C.2nD.n!5.下列程序段的S執(zhí)行的次數(shù)為(D)。fori←0ton-1do forj←0toi-1dos//某種基本操作n2B.n2/2C.n*(n+1)D.n(n+1)/2二、簡答題(每空8分,共計24分。)1.1.分而治之的基本思想是什么?它有哪些應(yīng)用(給出2種)?分治法的基本思想是:(1將問題的實例劃分為同一個問題的幾個較小的實例(2分)(2)對這些較小的實例求解(2分)(3)合并較小的問題,得到原問題的解(2分)應(yīng)用:折半查找、合并排序、快速排序、大整數(shù)乘法、凸包問題等。(任給2種即可,每種1分)2.2.Prim算法和Kruskal算法的共同點和區(qū)別是什么?Prim算法和Kruskal算法都是利用貪心算法求最小生成樹的算法。(4分,貪心和求最小生成樹各2分)Prim算法是從還未加入的頂點中選擇與生成樹中的頂點構(gòu)成邊,并且邊的權(quán)值最小的頂點。(2分)Kruskal算法是從未選擇的邊中選擇不構(gòu)成回路的邊加入到生成樹中。(2分)三、算法設(shè)計題(每題14分,共計56分。)1.1.給出一個求兩個數(shù)的最大公約數(shù)的算法。(1)如果n=0,返回m的值作為結(jié)果,同時過程結(jié)束;否則,轉(zhuǎn)(2)(4分)(2)用n去除m,將余數(shù)賦給r。(5分)(3)將n的值賦給m,將r的值賦給n,返回(1)。(5分)說明:求最大公約數(shù)還有其他算法,可參照該方法評分。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分)最優(yōu)的選擇是{3,4},價值是65.(6分)33.對數(shù)據(jù)表{37,89,20,46,17,26,67,33,10,82}用插入排序進行排序,給出排序過程(寫出每一趟的結(jié)果)26|9920451529653520722699|2045152965352072202699|4515296535207220264599|1529653520721520264599|2965352072152026294599|6535207215202629456599|3520721520262935456599|2072152020262935456599|7215202026293545657299|(1-9每步1分,第10步5分)4.4.對于下圖,用Dijkstra算法求解以a為起點的單源最短路徑。給出求解過程。
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 安徽省青陽縣一中2025屆高三第二次聯(lián)考數(shù)學(xué)試卷含解析
- 2025屆浙江省嘉興市重點名校高三第一次模擬考試語文試卷含解析
- 2025屆江西省南昌市10所省重點高三第二次診斷性檢測語文試卷含解析
- 黔南市重點中學(xué)2025屆高考考前提分英語仿真卷含解析
- 四川省成都航天中學(xué)2025屆高三下第一次測試語文試題含解析
- 2025屆葫蘆島市重點中學(xué)高三適應(yīng)性調(diào)研考試英語試題含解析
- 《信息學(xué)奧賽概述》課件
- 陜西省西安交大附中2025屆高考沖刺押題(最后一卷)英語試卷含解析
- 浙江省溫州九校2025屆高三考前熱身語文試卷含解析
- 河北省樂亭二中2025屆高三(最后沖刺)語文試卷含解析
- 數(shù)控車床出廠檢驗表(共5頁)
- 教育科研中問題即課題、過程即研究、結(jié)果即成果的理解
- 基于隱性資產(chǎn)的企業(yè)價值管理研究
- 清華大學(xué)全面素質(zhì)教育與拔尖創(chuàng)新人才培養(yǎng)PPT課件
- 線路板pcb專業(yè)英語詞匯(制造、測試、缺陷名等)
- 二期工程通水驗收報告(定稿)
- 電氣防火與防爆
- 《汽車電子商務(wù)》課程教案
- MSDS32除油粉
- 《網(wǎng)頁設(shè)計與制作項目教程(HTML+CSS+Bootstrap) 》題庫練習(xí)題復(fù)習(xí)題習(xí)題測試題帶答案
- 光伏工程質(zhì)量通病防治措施
評論
0/150
提交評論