算法分析與設(shè)計(jì)基礎(chǔ)知識(shí)習(xí)題_第1頁(yè)
算法分析與設(shè)計(jì)基礎(chǔ)知識(shí)習(xí)題_第2頁(yè)
算法分析與設(shè)計(jì)基礎(chǔ)知識(shí)習(xí)題_第3頁(yè)
算法分析與設(shè)計(jì)基礎(chǔ)知識(shí)習(xí)題_第4頁(yè)
算法分析與設(shè)計(jì)基礎(chǔ)知識(shí)習(xí)題_第5頁(yè)
已閱讀5頁(yè),還剩4頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、算法分析與設(shè)計(jì)基礎(chǔ)知識(shí)一、 選擇題1、 二分搜索算法是利用( A  )實(shí)現(xiàn)的算法。A、分治策略   B、動(dòng)態(tài)規(guī)劃法   C、貪心法    D、回溯法2. 下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是(  A   )。A、找出最優(yōu)解的性質(zhì)    B、構(gòu)造最優(yōu)解   C、算出最優(yōu)解   D、定義最優(yōu)解3. 回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹(shù)是( A  )。A、子集樹(shù) B、排列樹(shù)C、深度優(yōu)先生成樹(shù) D、廣

2、度優(yōu)先生成樹(shù)4. 衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是( C )。A、運(yùn)行速度快 B、占用空間少 C、 時(shí)間復(fù)雜度低 D、代碼短5. 以下不可以使用分治法求解的是( D )。A、棋盤(pán)覆蓋問(wèn)題 B、 選擇問(wèn)題 C、歸并排序 D、 0/1背包問(wèn)題6. 動(dòng)態(tài)規(guī)劃算法的基本要素為( C )A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì) D. 預(yù)排序與遞歸調(diào)用7. 以下關(guān)于漸進(jìn)記號(hào)的性質(zhì)是正確的有:( A )A.fn=gn,gn=hnfn=hnB. fn=Ogn,gn=Ohnhn=OfnC. Ofn+O(gn)=O(minfn,gn)D. fn=Ogngn=O(f

3、n)8. 能采用貪心算法求最優(yōu)解的問(wèn)題,一般具有的重要性質(zhì)為:(A)A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì) D. 預(yù)排序與遞歸調(diào)用9. 回溯法在問(wèn)題的解空間樹(shù)中,按( D )策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。A 廣度優(yōu)先 B. 活結(jié)點(diǎn)優(yōu)先 C.擴(kuò)展結(jié)點(diǎn)優(yōu)先 D. 深度優(yōu)先10. 分支限界法在問(wèn)題的解空間樹(shù)中,按(A)策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。 A 廣度優(yōu)先 B. 活結(jié)點(diǎn)優(yōu)先 C.擴(kuò)展結(jié)點(diǎn)優(yōu)先 D. 深度優(yōu)先11. 下面不是分支界限法搜索方式的是( D )。A、廣度優(yōu)先 B、最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先 D、深度優(yōu)先12分

4、支限界法解0-1背包問(wèn)題時(shí),活結(jié)點(diǎn)表的組織形式是( B )。A、最小堆 B、最大堆 C、棧D、數(shù)組13. 常見(jiàn)的兩種分支限界法為(D)A、 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法;B、 隊(duì)列式(FIFO)分支限界法與堆棧式分支限界法;C、 排列樹(shù)法與子集樹(shù)法;D、 隊(duì)列式(FIFO)分支限界法與優(yōu)先隊(duì)列式分支限界法;14、記號(hào)O的定義正確的是(A)。A、O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 f(n) cg(n) ;B、 O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 cg(n) f(n) ;C、 O(g(n) = f(n)

5、 | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有nn0有:0 f(n)<cg(n) ;D、 O(g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所 有nn0有:0 cg(n) < f(n) ;15. 記號(hào)的定義正確的是(B)。A、 O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 f(n) cg(n) ;B、 O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 cg(n) f(n) ;C、 (g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使

6、得對(duì)所有nn0有:0 f(n)<cg(n) ;D、 (g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有nn0有:0 cg(n) < f(n) ;16. 具有最優(yōu)子結(jié)構(gòu)的算法有:( D ) A窮舉法 B回溯法 C分支限界法 D動(dòng)態(tài)規(guī)劃法17. 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是( A )。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法 D、回溯法18. 實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是( B )。A、分治策略B、動(dòng)態(tài)規(guī)劃法 C、貪心法D、回溯法19下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是( D )。A、備忘錄法B

7、、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法20. 以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為 ( D ) 。A、分支界限算法 B、概率算法    C、貪心算法  D、回溯算法21哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為( B )。A、O(n2n)B、O(nlogn)C、O(2n)D、O(n)22最長(zhǎng)公共子序列算法利用的算法是( B   )。A、分支界限法B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法23實(shí)現(xiàn)棋盤(pán)覆蓋算法利用的算法是(  A  )。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法 D、回溯法24.下面是貪心算法的基本要素

8、的是( C )。A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解25.回溯法的效率不依賴(lài)于下列哪些因素( D )A.滿(mǎn)足顯約束的值的個(gè)數(shù) B. 計(jì)算約束函數(shù)的時(shí)間 C. 計(jì)算限界函數(shù)的時(shí)間 D. 確定解空間的時(shí)間26.下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略(    B    )A遞歸函數(shù)B.剪枝函數(shù) C。隨機(jī)數(shù)函數(shù) D.搜索函數(shù)27. ( D )是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)28. 矩陣連乘問(wèn)題的算法可由(B)設(shè)

9、計(jì)實(shí)現(xiàn)。A、分支界限算法  B、動(dòng)態(tài)規(guī)劃算法  C、貪心算法  D、回溯算法29. 分支限界法解旅行售貨員問(wèn)題時(shí),活結(jié)點(diǎn)表的組織形式是(A )。A、最小堆B、最大堆 C、棧D、數(shù)組30、Strassen矩陣乘法是利用(A)實(shí)現(xiàn)的算法。A、分治策略   B、動(dòng)態(tài)規(guī)劃法   C、貪心法    D、回溯法31、使用分治法求解不需要滿(mǎn)足的條件是(A )。A、 子問(wèn)題必須是一樣的 B、 子問(wèn)題不能夠重復(fù)C、 子問(wèn)題的解可以合并 D、 原問(wèn)題和子問(wèn)題使用相同的方法解32、下面問(wèn)題(B )不能使用貪心法解決。

10、A、 單源最短路徑問(wèn)題 B、 N皇后問(wèn)題 C、 最小花費(fèi)生成樹(shù)問(wèn)題 D、 背包問(wèn)題33、下列算法中不能解決0/1背包問(wèn)題的是(A )A、 貪心法 B、 動(dòng)態(tài)規(guī)劃 C、 回溯法 D、 分支限界法34、回溯法搜索狀態(tài)空間樹(shù)是按照(C )的順序。A、 中序遍歷 B、廣度優(yōu)先遍歷 C、深度優(yōu)先遍歷 D、 層次優(yōu)先遍歷35、采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序,故算法的時(shí)間復(fù)雜度為( B ) 。A、O(n2n)B、O(nlogn)C、O(2n) D、O(n)36實(shí)現(xiàn)合并排序利用的算法是(A)。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法 D、回溯法37下列是動(dòng)態(tài)規(guī)劃算法基本要素

11、的是(D )。A、定義最優(yōu)解 B、構(gòu)造最優(yōu)解 C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)38下列算法中通常以自底向下的方式求解最優(yōu)解的是(B)。A、分治法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法39采用廣度優(yōu)先策略搜索的算法是(A)。A、分支界限法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法40、合并排序算法是利用(A )實(shí)現(xiàn)的算法。A、分治策略   B、動(dòng)態(tài)規(guī)劃法   C、貪心法    D、回溯法41、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為(B )A、O(n2n)     B、O(nlogn)

12、0;   C、O(2n)      D、O(n)42實(shí)現(xiàn)大整數(shù)的乘法是利用的算法(C )。A、貪心法B、動(dòng)態(tài)規(guī)劃法C、分治策略D、回溯法43采用最大效益優(yōu)先搜索方式的算法是(A)。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法44貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是(B)。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解45. 實(shí)現(xiàn)最大子段和利用的算法是(B)。A、分治策略 B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法46.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是(C)。A、先進(jìn)先出B、后進(jìn)先出 C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)47

13、.背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為(B)。A、O(n2n)B、O(nlogn)C、O(2n) D、O(n)48、廣度優(yōu)先是(A)的一搜索方式。A、分支界限法  B、動(dòng)態(tài)規(guī)劃法   C、貪心法    D、回溯法49. 一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的(B )。A、重疊子問(wèn)題 B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解50. 算法分析中,記號(hào)O表示(B), 記號(hào)表示(A), 記號(hào)表示(D)。A、 漸進(jìn)下界 B、漸進(jìn)上界 C、非緊上界 D、緊漸進(jìn)界 二、 填空題1. 四后問(wèn)題的搜索空間為 排序 樹(shù);0-1背包

14、問(wèn)題的搜索空間為 子集 樹(shù); 旅行售貨員問(wèn)題的搜索空間為 排序 樹(shù)。2. 回溯 法的求解目標(biāo)是找出解空間樹(shù)中滿(mǎn)足約束條件的所有解,而 分支限界 法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解,或是在滿(mǎn)足約束條件的解中找出在某種意義下的最優(yōu)解。3. 回溯法一般以 深度 優(yōu)先的方式搜索解空間樹(shù),而分支限界法則一般以 廣度 優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。4. 在忽略常數(shù)因子的情況下,O、和三個(gè)符號(hào)中, O 提供了算法運(yùn)行時(shí)間的一個(gè)上界。5. 分治算法的基本步驟包括 (1)分解 (2) 解決 (3) 合并 。6. 回溯算法的基本思想是 從根結(jié)點(diǎn)出發(fā),按照深度優(yōu)先策略遍歷解空間。7. 動(dòng)態(tài)規(guī)劃和分治

15、法在分解子問(wèn)題方面的不同點(diǎn)是 分解后的子問(wèn)題往往不相互獨(dú)立 。8. 貪心算法中每次做出的貪心選擇都是 當(dāng)前的 最優(yōu)選擇。9. 選擇排序、插入排序和歸并排序算法中, 歸并排序 算法是分治算法。10. 算法的復(fù)雜性有 時(shí)間 復(fù)雜性和 空間 復(fù)雜性之分。11. 程序是 算法 用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。12. 算法的“確定性”指的是組成算法的每條 指令 是清晰的,無(wú)歧義的。13. 矩陣連乘問(wèn)題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。14. 算法是指解決問(wèn)題的 一種方法 。15. 從分治法的一般設(shè)計(jì)模式可以看出,用它設(shè)計(jì)出的程序一般是 遞歸算法 。16. 問(wèn)題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問(wèn)題可用動(dòng)態(tài)規(guī)

16、劃算法或貪心算法求解的關(guān)鍵特征。17. 以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為 回溯法 。18. 計(jì)算一個(gè)算法時(shí)間復(fù)雜度通常可以計(jì)算的 循環(huán)次數(shù) 、 基本操作的頻度 或計(jì)算步。19. 解決0/1背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法,其中不需要排序的是 動(dòng)態(tài)規(guī)劃 ,需要排序的是 回溯法 , 分支限界法 。20. 使用回溯法進(jìn)行狀態(tài)空間樹(shù)裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn):約束條件和目標(biāo)函數(shù)的界,N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類(lèi)型,其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是 0/1背包 ,只使用約束條件進(jìn)行裁剪的是 N 皇后問(wèn)題 。21. 貪心選擇性質(zhì) 是貪心算法可行的第一個(gè)基本要素

17、,也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。22. 貪心算法的基本要素是 貪心選擇 性質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。23. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干 子問(wèn)題 ,先求解 子問(wèn)題最優(yōu)解 ,然后從這些 子問(wèn)題 的解得到原問(wèn)題的解。24. 算法是由若干條指令組成的有窮序列,且要滿(mǎn)足輸入、 輸出 、確定性、有窮性和 可行性 五條性質(zhì)。25. 大整數(shù)乘積算法是用 分治法 來(lái)設(shè)計(jì)的。26. 以廣度優(yōu)先或以最小耗費(fèi)方式搜索問(wèn)題解的算法稱(chēng)為 分支限界法 。27. 快速排序算法是基于 分治策略 的一種排序算法。28. 動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是. 最優(yōu)子結(jié)構(gòu) 性質(zhì)和 重疊子問(wèn)題 性質(zhì) 。29. 回

18、溯法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 30. 分支限界法主要有 隊(duì)列式 分支限界法和 優(yōu)先隊(duì)列式 分支限界法。31. 分支限界法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。32. 回溯法搜索解空間樹(shù)時(shí),常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù)。33. 任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其 規(guī)模 有關(guān)。34. 快速排序算法的性能取決于 劃分的對(duì)稱(chēng)性 。35. 算法就是一組有窮 規(guī)則的集合 ,它們規(guī)定了解決某一特定類(lèi)型問(wèn)題的 步驟 。36. 算法的復(fù)雜性是 算法效率 的度量,是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。37. 計(jì)算機(jī)的資源最重要的是 CPU 和 內(nèi)存 資源。因而,算法

19、的復(fù)雜性有 時(shí)間復(fù)雜度 和 空間復(fù)雜度 之分。38. f(n)= 6×2n+n2,f(n)的漸進(jìn)性態(tài)f(n)= O( n2 )39. 貪心算法總是做出在當(dāng)前看來(lái) 最佳 的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮,它所做出的選擇只是在某種意義上的 最優(yōu)值 。40. 常見(jiàn)的減治策略分為三類(lèi):減去一個(gè)常量,減去一個(gè)常量因子,減可變規(guī)模。41. 變治思想有三種主要的類(lèi)型:實(shí)例化簡(jiǎn),改變表現(xiàn),問(wèn)題化簡(jiǎn)。42. 減常量算法是在每次選法迭代中從實(shí)例規(guī)模中減去一個(gè)規(guī)模相同的常量。43. 減常量因子算法是在每次迭代中從實(shí)例規(guī)模中減去一個(gè)相同的常量因子,也就是每次縮減的實(shí)例規(guī)模其比例相同。44. 堆的構(gòu)建過(guò)程對(duì)于堆排序而言是一種 變治 策略。屬于變治思想中的實(shí)例化簡(jiǎn)類(lèi)型。45. 平衡二叉樹(shù)對(duì)于查找算法而言是一種變治策略,屬于變治思想中的實(shí)例化簡(jiǎn)類(lèi)型。三、 課程內(nèi)容基本要求1. 算法的描述方法:自然語(yǔ)言描述、類(lèi)程序設(shè)計(jì)語(yǔ)言或流程圖、程序設(shè)計(jì)語(yǔ)言描述或程序?qū)崿F(xiàn)。要求能夠用上述描述方法對(duì)算法進(jìn)行描述。2. 算法效率分析的基本方法,要求在給定程序的情況下能夠求解算法的時(shí)間復(fù)雜度。3. 算法時(shí)間復(fù)雜度的度量方法,要求在給定函數(shù)的情況下

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論