1、2011 年 12 月考試算法設(shè)計(jì)分析第一次作業(yè)一、單項(xiàng)選擇題（本大題共 30 分，共 15 小題，每小題 2 分）1. 算法分析的兩個(gè)主要方面是（ ）。A. 空間復(fù)雜度和時(shí)間復(fù)雜度B. 正確性和簡(jiǎn)單性C. 可讀性和文檔性D. 數(shù)據(jù)復(fù)雜度和程序復(fù)雜度2. 計(jì)算機(jī)算法指的是（ ）。A. 計(jì)算方法B. 排序方法C. 解決問(wèn)題的方法和過(guò)程D. 調(diào)度方法3. 多階段決策問(wèn)題就是要在可以選擇的那些策略中間選取一個(gè)（ ）策略使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果。A. 最優(yōu)B. 最差C. 平衡D. 任意4. 根據(jù)排序元素所在位置的不同，排序分（ ）。A. 內(nèi)排序和外排序B. 首排序和尾排序C. 順序排序和逆序排序

2、D. 堆排序和棧排序5. 算法必須具備輸入、輸出和（ ）等 5 個(gè)特性。A. 可執(zhí)行性、可移植性和可擴(kuò)充性B. 可行性、確定性和有窮性C. 確定性、有窮性和穩(wěn)定性D. 易讀性、穩(wěn)定性和安全性6. 與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題（ ）A. 經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的B. 經(jīng)分解得到子問(wèn)題往往是互相獨(dú)立的C. 經(jīng)分解得到子問(wèn)題往往是互相交叉的D. 經(jīng)分解得到子問(wèn)題往往是任意的7. 二分搜索算法的基本思想是將 n 個(gè)元素分成個(gè)數(shù)大致相同的兩半，取 an/2與 x 進(jìn)行比較：如果（ ），則只要在數(shù)組 a 的左半部繼續(xù)搜索 x。A. xan/2B. xan/2C. xan/2D.

3、xan/28. 活動(dòng)安排問(wèn)題就是在所給的活動(dòng)集合中，選出（ ）的相容活子集。A. 最小B. 任意C. 最大D. 一個(gè)9. 在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是（ ）A. 回溯法B. 分支限界法C. 回溯法和分支限界法D. 回溯法求解子集樹(shù)問(wèn)題10. 適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿(mǎn)足（ ）A. 最優(yōu)化原理B. 無(wú)前效性C. 最優(yōu)化原理和后效性D. 最優(yōu)化原理和無(wú)后效性11. 算法的每種運(yùn)算必須要有確切的定義不能有二義性以下符合算法確定性運(yùn)算的是（ ）A. 5/0B. 將 6 或 7 與 x 相加C. 未賦值變量參與運(yùn)算D. fnfn-12F110n 為自然數(shù)12.

4、直接或間接的調(diào)用自身的算法稱(chēng)為（ ）。A. 貪心算法B. 遞歸算法C. 迭代算法D. 動(dòng)態(tài)規(guī)劃算法13. 二分查找只適用（ ）存儲(chǔ)結(jié)構(gòu)。A. 堆B. 順序C. 任意順序D. 棧14. 實(shí)現(xiàn)快速排序算法如下：private static void quickSort(int p,int r)if(pr)int q=partition(p,r);();qicksort(q+1,r);A. quickSortpq-1B. quickSortp1q-1C. quickSortpq1D. quickSortpq-215. 應(yīng)用分治法的兩個(gè)前提是（ ）。A. 問(wèn)題的可分性和解的可歸并性B. 問(wèn)題的可分性和

5、解的存在性C. 問(wèn)題的復(fù)雜性和解的可歸并性D. 問(wèn)題的可分性和解的復(fù)雜性2、 判斷題（本大題共 70 分，共 20 小題，每小題 3.5 分）1. 算法就是一組有窮的規(guī)則？ 2. 概率算法中蒙特卡羅算法得到的解必是正確的？ 3. 程序和算法一樣，都是某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。 （ ）4. 合并排序算法是漸近最優(yōu)算法？ 5. 遞歸定義必須是有確切含義是指必須一步比一步簡(jiǎn)單最后是有終結(jié)的決不能無(wú)限循環(huán)下去？ 6. 二分搜索方法在最壞的情況下用 Olog n時(shí)間完成搜索任務(wù)。（ ）7. 能否利用分治法完全取決于問(wèn)題是否具有如下特征：利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解。 8. 分治法的

6、基本思想是將一個(gè)規(guī)模較大的問(wèn)題分解成若干個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題之間并不一定相互獨(dú)立（ ）9. 遞歸算法的效率往往很低，費(fèi)時(shí)和費(fèi)內(nèi)存空間 10. 當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)只能用動(dòng)態(tài)規(guī)劃方法求解。 11. 如果一類(lèi)活動(dòng)過(guò)程一個(gè)階段的決策確定以后，常影響到下一個(gè)階段的決策，則稱(chēng)它為多階段決策問(wèn)題。（ ）12. 反復(fù)應(yīng)用分治手段不能使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮?。?13. 裴波那契數(shù)列的定義：fnfn-1fn-2f01f12，其數(shù)據(jù)的定義形式不是按遞歸定義。 14. 0-1 背包問(wèn)題與背包問(wèn)題這兩類(lèi)問(wèn)題都可以用貪心算法求解。（ ）15. 證明貪心選擇后的問(wèn)題簡(jiǎn)化為規(guī)模更小的類(lèi)似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)。（ ）16. 子問(wèn)題之間不包含公共的子問(wèn)題這個(gè)條件涉及到分治法的效率 17. 概率算法允許在執(zhí)行過(guò)程中隨機(jī)地選擇下一個(gè)計(jì)算步驟？ 18. 二分搜索法的二分查找只適用于順序存儲(chǔ)結(jié)構(gòu)。 （ ）19. 要想在電腦上擴(kuò)大所處理問(wèn)題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度 20. 用回溯法解題一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間（ ）答案：一、單項(xiàng)選擇題（30 分，共 15 題，每小題 2 分）1. A 2. C 3. A 4. A 5. B 6. A 7. A 8. C 9. B 10. D 11. B 12. B 13. B