計(jì)算機(jī)算法與設(shè)計(jì)復(fù)習(xí)題含答案

1、計(jì)算機(jī)算法與設(shè)計(jì)復(fù)習(xí)題（含答案）1、一個(gè)算法的優(yōu)劣可以用與與來(lái)衡量。2、回溯法在問(wèn)題的解空間中，按從根結(jié)點(diǎn)由發(fā)搜索解 空間樹(shù)。3、直接或間接地調(diào)用自身的算法稱(chēng)為。4、記號(hào)在算法復(fù)雜性的表示法中表示。5、在分治法中，使子問(wèn)題規(guī)模大致相等的做法是由自 一種?？梢越鉀Q背包問(wèn)題28、投點(diǎn)法是的一種。29、若線(xiàn)性規(guī)劃問(wèn)題存在最優(yōu)解，它一定不在30、n皇后問(wèn)題可以用解決。 31、若L是一個(gè)NP完全 問(wèn)題，L經(jīng)過(guò)多項(xiàng)式時(shí)間變換后得到問(wèn)題 l ,則l是（P類(lèi) 問(wèn)題）.32、算法與程序在性質(zhì)上有所不同，下列性質(zhì)中，程序 可以不滿(mǎn)足哪個(gè)性質(zhì)：。案。對(duì)；8）動(dòng)態(tài)規(guī)劃算法是用于解最優(yōu)化問(wèn)題，采用自頂向下 的方式計(jì)算由

2、最優(yōu)解。錯(cuò)；9）貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題必須具有最優(yōu) 子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)。錯(cuò)；10 ）隊(duì)列式分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，并按隊(duì)列的先進(jìn)現(xiàn)由原則 選取下一個(gè)結(jié)點(diǎn)稱(chēng)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。錯(cuò)；四、算法設(shè)計(jì)說(shuō)明：任意選擇所使用的算法策略；要求：說(shuō)問(wèn)題）的思想6、動(dòng)態(tài)規(guī)劃算法適用于解問(wèn)題。7、貪心算法做由的選擇只是最優(yōu)選擇。8、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是。9、回溯法按策略從根結(jié)點(diǎn)由發(fā)搜索解空間樹(shù)。10、拉斯維加斯算法找到的解一定是。11、按照符號(hào)O的定義O(f)+O(g)等于 O(maxf(n),g(n)。12、二分搜索技術(shù)是運(yùn)用策略的典型例子。13、動(dòng)態(tài)規(guī)劃算法中，通常不同子問(wèn)題的個(gè)數(shù)

3、隨問(wèn)題規(guī) 模呈級(jí)增長(zhǎng)。14、和是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。 15、和是貪心算法的基本要素。16、是設(shè)計(jì)貪心算法的核心問(wèn)題。17、分支限界法常以或的方式搜索問(wèn)題的解空間樹(shù)。18、貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò) 一系列的選擇，即貪心選擇達(dá)到。19、按照活結(jié)點(diǎn)表的組織方式的不同，分支限界法包括 和兩種形式。20、如果對(duì)于同一實(shí)例，蒙特卡洛算法不會(huì)給由兩個(gè)不 同的正確解答，則稱(chēng)該蒙特卡洛算法是。21、哈夫曼編碼可利用算法實(shí)現(xiàn)。22概率算法有數(shù)值概率算法，蒙特卡羅算法，拉斯維加 斯算法和舍伍德算法 23以自頂向下的方式求解最優(yōu)解的有24、下列算法中通常以自頂向下的方式求解最優(yōu)解的 是

4、。A、分治法B、動(dòng)態(tài)規(guī)劃法 C、貪心法D、回溯法25、在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)有多次機(jī)會(huì)成為活結(jié)點(diǎn)的是26、旅行售貨員問(wèn)題不能用解決可以用回溯法解決，分支限界法，NP完全性理論與近似算法 27、貪心算法不能 解決34、動(dòng)態(tài)規(guī)劃算法的基本步驟不包括下列哪一步：包括:劃分階段：選擇狀態(tài)確定決策并寫(xiě)由狀態(tài)轉(zhuǎn)移方程寫(xiě)由規(guī)劃方程：35、在調(diào)試程序過(guò)程中，下列哪一種錯(cuò)誤是計(jì)算機(jī)檢查 不由來(lái)的：36、分治算法不包括以下哪項(xiàng)內(nèi)容：包括：二 分搜索技術(shù)；大整數(shù)乘法；Strassen矩陣乘法；棋盤(pán)覆蓋；合并排序和快速排序；線(xiàn)性時(shí)間選擇；最接近點(diǎn)對(duì)問(wèn)題；循 環(huán)賽日程表37、貪心算法不能解決。3

5、8、舍伍德算法是的一種。39、若線(xiàn)性規(guī)劃問(wèn)題存在最優(yōu)解，它一定不在40、回溯法可以解決的問(wèn)題包括判斷題1）分支限界法類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題解的算法， 兩者的求解目標(biāo)是相同的。 對(duì);2）優(yōu)先隊(duì)列式的分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu) 先隊(duì)列，并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高 的下一個(gè)結(jié)點(diǎn)稱(chēng)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)；3）回溯法求解問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié) 點(diǎn)的所有子樹(shù)都被搜索遍才結(jié)束。錯(cuò)，搜索到一個(gè)解就可結(jié) 束；4）動(dòng)態(tài)規(guī)劃法用一個(gè)表來(lái)記錄所有已解決的子問(wèn)題的 答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就 將其結(jié)果填入表中。對(duì)；一個(gè)直接或間接地調(diào)用

6、自身的算法稱(chēng)為遞歸算法， 而一個(gè)使用函數(shù)自身給由定義的函數(shù)稱(chēng)為遞歸函數(shù)。定義遞 歸函數(shù)時(shí)可以沒(méi)有初始值。錯(cuò)，應(yīng)該有初始值；一個(gè)直接或間接地調(diào)用自身的算法稱(chēng)為遞歸算法， 而一個(gè)使用函數(shù)自身給由定義的函數(shù)稱(chēng)為遞歸函數(shù)。定義遞 歸函數(shù)時(shí)可以沒(méi)有初始值。錯(cuò)，應(yīng)該有初始值；7）動(dòng)態(tài)規(guī)劃法用一個(gè)表來(lái)記錄所有已解決的子問(wèn)題的 答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就 將其結(jié)果填入表中。在需要時(shí)從表中找由以求得的答明所使 用的算法策略；寫(xiě)由算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間 復(fù)雜性。0-1背包問(wèn)題第三章，第五章，第六章單源最短路徑問(wèn)題第四章，第六章0-1背包問(wèn)題： 算法策略：動(dòng)態(tài)規(guī)劃算法。動(dòng)態(tài)規(guī)劃

7、算 法基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，但是經(jīng)分 解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常 常只有多項(xiàng)式量級(jí)。步驟：1我由最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。2遞歸地定義最優(yōu)值。3以自底向上的方式計(jì)算 由最優(yōu)值。4根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。時(shí)間復(fù)雜度：改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(2M) o當(dāng)所給物品的重量 wi(1 wiwn)是整數(shù)時(shí)，|pi|c+1, (1 i n) o在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為 O(minnc,2An) 單源最短路徑問(wèn)題：算法策略：貪心算法。貪心算法總是作曲在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算 法并不從整體最優(yōu)考慮，它所作曲

8、的選擇只是在莫種意義上 的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是 整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu) 解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn) 題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能 得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。貪心 算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作由相繼 的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更 小的子問(wèn)題。步驟：Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí)，S中僅含有源。設(shè)u是G的奧一個(gè)頂點(diǎn)，把從源到 u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱(chēng)為從 源到u的特殊路徑，并用數(shù)組 dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì) 應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra 算法每次從V-S中取由具 有最短特殊路長(zhǎng)度的頂點(diǎn)u,將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦 S包含了所有 V中頂點(diǎn)，dist就 記錄了從源到所有