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

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

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

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

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

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

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

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

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