川農(nóng)大算法分析期末復(fù)習(xí)

1、Word資料算法分析與設(shè)計(jì)復(fù)習(xí)題1.5判斷題 選擇題:判斷題1 .算法就是一組有窮的規(guī)則。答案：正確2 .概率算法中蒙特卡羅算法得到的解必是正確的。答案：錯(cuò)誤3 .程序和算法一樣，都是某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。答案：錯(cuò)誤4 .合并排序算法是漸近最優(yōu)算法。答案：正確5 .遞歸定義必須是有確切含義是指必須一步比一步簡(jiǎn)單，最后是有終結(jié)的，決不能無(wú)限循 環(huán)下去。答案：正確6 .二分搜索方法在最壞的情況下用O(log n)時(shí)間完成搜索任務(wù)。答案：正確7 .能否利用分治法完全取決于問(wèn)題是否具有如下特征：利用該問(wèn)題分解出的子問(wèn)題的解可 以合并為該問(wèn)題的解。答案：正確8 .分治法的基本思想是將一個(gè)規(guī)模較大的

2、問(wèn)題分解成若干個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn) 題之間并不一定相互獨(dú)立。答案：錯(cuò)誤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ī)劃方法求解。答案：錯(cuò)誤常影響到下一個(gè)階段的決策，則稱(chēng)它為多11 .如果一類(lèi)活動(dòng)過(guò)程一個(gè)階段的決策確定以后, 階段決策問(wèn)題。答案：正確12 .反復(fù)應(yīng)用分治手段，不能使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小。答案：錯(cuò)誤13 .裴波那契數(shù)列的定義：f(n尸f(n-1)+f(n-2),f(0)=1,f(1)=2,其數(shù)據(jù)的定義形式不是按遞歸定義。答案：錯(cuò)誤14 . 0-1背包問(wèn)題與背包問(wèn)題這兩類(lèi)問(wèn)題都可以用貪心算法求解

3、。答案：錯(cuò)誤15 .證明貪心選擇后的問(wèn)題簡(jiǎn)化為規(guī)模更小的類(lèi)似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子 結(jié)構(gòu)性質(zhì)。答案：錯(cuò)誤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)題的解空間。答案：錯(cuò)誤21 .從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是一個(gè)遞歸過(guò)程。因此，分 治法的計(jì)算效率通?？梢杂眠f歸方

4、程來(lái)進(jìn)行分析。答案：正確22 .多階段決策問(wèn)題中，每一個(gè)階段可能有若干個(gè)決策可供選擇答案：正確23 .拉斯維加斯算法不會(huì)得到不正確的解，但有時(shí)找不到解。答案：正確24 .在通往邊界條件的遞歸調(diào)用過(guò)程中，系統(tǒng)用堆棧保存的每次調(diào)用的中間結(jié)果是局部變量 和返回地址值。答案：正確25 .要想在電腦上擴(kuò)大所處理問(wèn)題的規(guī)模，有效的途徑是提高算法的計(jì)算復(fù)雜度。 答案：錯(cuò)誤26 .程序必須滿(mǎn)足算法具有數(shù)據(jù)輸出的性質(zhì)。答案：正確27 .反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小答案：正確28 . 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，它們是同輸入有某種特定關(guān)系的量 答案：正確29 .最優(yōu)子結(jié)構(gòu)性質(zhì)特

5、征反映了遞歸思想的應(yīng)用答案：正確30 .遞歸邊界本身并不使用遞歸的定義答案：正確31 .用分治法求解一個(gè)問(wèn)題，所需的時(shí)間是由子問(wèn)題的個(gè)數(shù)、大小以及把這個(gè)問(wèn)題分解為子問(wèn)題所需的工作總量來(lái)確定的。答案：正確32 .應(yīng)用回溯法解問(wèn)題時(shí)，首先應(yīng)明確定義問(wèn)題的解空間。問(wèn)題的解空間應(yīng)至少包含問(wèn)題的一個(gè)（最優(yōu)）解。答案：正確33 .好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)，但這樣的約束函數(shù)往往計(jì)算量較大。因此,在選擇約束函數(shù)時(shí)通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。答案：正確34 . 一個(gè)遞歸定義必須是有確切含義的，必須一步比一步簡(jiǎn)單，最后是有終結(jié)的，不能無(wú)限 循環(huán)下去。答案：正確35 .最優(yōu)子結(jié)構(gòu)性質(zhì)

6、是應(yīng)用分治法的前提。答案：正確36 .操作系統(tǒng)，它是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。 答案：正確37 .有些數(shù)據(jù)結(jié)構(gòu)如二叉樹(shù)等，由于其本身的遞歸特性、特別適合用遞歸的形式來(lái)描述。答案：正確38 .概率算法的一個(gè)基本特征是，對(duì)所求問(wèn)題的同一個(gè)實(shí)例用同一個(gè)算法求解兩次一定能得到完全相同的效果。答案：錯(cuò)誤39 .問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。答案：錯(cuò)誤40 .遞推是從內(nèi)邊界條件出發(fā)，通過(guò)遞推式達(dá)到邊界條件。答案：正確41 .所有的遞歸函數(shù)都能找到對(duì)應(yīng)的非遞歸定義。 答案：正確42 .定義遞歸函數(shù)時(shí)可以沒(méi)有初始值。答案：錯(cuò)誤43 .動(dòng)態(tài)規(guī)劃算法的基

7、本要素是最優(yōu)子結(jié)構(gòu)。答案：正確44 .最優(yōu)子結(jié)構(gòu)性質(zhì)是指原問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解。答案：正確45 .動(dòng)態(tài)規(guī)劃算法求解問(wèn)題時(shí)，分解出來(lái)的子問(wèn)題相互獨(dú)立。答案：錯(cuò)誤46 .滿(mǎn)足貪心選擇性質(zhì)必滿(mǎn)足最優(yōu)子結(jié)構(gòu)性質(zhì)。答案：錯(cuò)誤47 .回溯法中限界函數(shù)的目的是剪去得不到最優(yōu)解的子樹(shù)。答案：正確48 .分支限界法類(lèi)似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T上搜索問(wèn)題解的算法， 兩者的搜索方式是相同的。答案：錯(cuò)誤49 .任何遞歸算法都有遞歸出口。答案：正確50 .遞歸算法的執(zhí)行效率比功能相同的非遞歸算法的執(zhí)行效率高。答案：錯(cuò)誤51 .遞歸算法不能轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法。答案：錯(cuò)誤52 .數(shù)據(jù)元素是數(shù)據(jù)的

8、最小單位 答案：錯(cuò)誤53 .數(shù)據(jù)對(duì)象就是一組數(shù)據(jù)元素的集合答案：錯(cuò)誤54 .任何數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找。答案：錯(cuò)誤55 .數(shù)據(jù)對(duì)象是由有限個(gè)類(lèi)型相同的數(shù)據(jù)元素構(gòu)成的。 答案：正確56 .數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計(jì)算機(jī)中如何存儲(chǔ)有關(guān)。答案：錯(cuò)誤57 .如果數(shù)據(jù)元素值發(fā)生改變，則數(shù)據(jù)的邏輯結(jié)構(gòu)也隨之改變。答案：錯(cuò)誤58 .邏輯結(jié)構(gòu)相同的數(shù)據(jù)，可以采用多種不同的存儲(chǔ)方法。 答案：正確59 .邏輯結(jié)構(gòu)不相同的數(shù)據(jù)，必須采用不同的存儲(chǔ)方法來(lái)存儲(chǔ)。 答案：錯(cuò)誤60 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。答案：錯(cuò)誤61 .順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)。答案：錯(cuò)誤

9、則算法62 .算法可以用不同的語(yǔ)言來(lái)描述，如果用C語(yǔ)言或Pascal語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述,就等同于程序。答案：錯(cuò)誤63 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系。答案：正確64 .數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像（或表示）分別稱(chēng)為存儲(chǔ)結(jié)構(gòu)、節(jié)點(diǎn)和 數(shù)據(jù)域。答案：正確65 .數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。答案：正確66 .分配給單鏈表的內(nèi)存與地址必須是連續(xù)的。答案：錯(cuò)誤67 .從長(zhǎng)度為n的順序表中刪除任何一個(gè)元素，時(shí)間復(fù)雜度都是 O(n)。答案：錯(cuò)誤68 .向順序表中插入一個(gè)元素，平均要移動(dòng)大約一半的元素。答案：正確69 .凡是為空的單鏈表都是不含任何節(jié)點(diǎn)的。答案

10、：錯(cuò)誤70 .如果單鏈表帶有頭節(jié)點(diǎn)，則插入操作永遠(yuǎn)不會(huì)改變頭節(jié)點(diǎn)指針的值。答案：正確71 .在循環(huán)單鏈表中，任何一個(gè)節(jié)點(diǎn)的指針域都不可能為空。答案：正確72 .順序存儲(chǔ)方式的特點(diǎn)是存儲(chǔ)密度大且插入、刪除運(yùn)算效率高。答案：錯(cuò)誤73 .線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。答案：錯(cuò)誤74 .順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)。答案：正確75 .由于順序存儲(chǔ)結(jié)構(gòu)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活。答案：正確76 .對(duì)于單鏈表來(lái)說(shuō)，只有從頭節(jié)點(diǎn)開(kāi)始才能掃描表中全部節(jié)點(diǎn)。答案：正確77 .對(duì)于循環(huán)單鏈表來(lái)說(shuō)，從表中任一節(jié)點(diǎn)出發(fā)都能掃描表中全部節(jié)點(diǎn)。答案：正確78 .雙鏈表的特點(diǎn)

11、是很容易找任一節(jié)點(diǎn)的前趨和后繼。答案：正確79 .線(xiàn)性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。答案：正確80 .如果有多個(gè)線(xiàn)性表同時(shí)共存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)地發(fā)生變化，線(xiàn)性表 的總數(shù)也會(huì)自動(dòng)改變。在此情況下，應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。答案：正確81 .若線(xiàn)性表的總數(shù)基本穩(wěn)定且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表中的元素，那么應(yīng)該選用順序存儲(chǔ)結(jié)構(gòu)。答案：正確82 .對(duì)于單鏈表和雙鏈表，均能從當(dāng)前節(jié)點(diǎn)出發(fā)訪(fǎng)問(wèn)到任一節(jié)點(diǎn)。答案：錯(cuò)誤83 .循環(huán)單鏈表和循環(huán)雙鏈表從尾指針出發(fā)可以訪(fǎng)問(wèn)到鏈表中的任意節(jié)點(diǎn)。答案：正確84 .若頻繁地對(duì)一個(gè)線(xiàn)性表進(jìn)行插入和刪除操作，該線(xiàn)性表宜采用鏈?zhǔn)?/p>

12、存儲(chǔ)結(jié)構(gòu)。答案：正確85 .棧底元素是不能刪除的元素。答案：錯(cuò)誤86 .順序棧中元素值的大小是有序的。答案：錯(cuò)誤87 .棧頂元素和棧底元素有可能是同一個(gè)元素。答案：正確88 .若用s1m表示順序棧的存儲(chǔ)空間，則對(duì)棧的進(jìn)棧、出棧操作最多只能進(jìn)行m次。答案：錯(cuò)誤89 .棧是一種對(duì)進(jìn)棧、出棧操作總次數(shù)作了限制的線(xiàn)性表。答案：錯(cuò)誤90 .空棧沒(méi)有棧頂指針答案：錯(cuò)誤91 .環(huán)形隊(duì)列中有多少元素，可以根據(jù)隊(duì)首指針和隊(duì)尾指針的值來(lái)計(jì)算。答案：正確92 .無(wú)論是順序隊(duì)列，還是鏈?zhǔn)疥?duì)列，插入、刪除運(yùn)算的時(shí)間復(fù)雜度都是0(1)。答案：正確93 .棧和隊(duì)列都是插入和刪除操作受限的線(xiàn)性表。答案：正確94 .棧和隊(duì)列的

13、存儲(chǔ)方式既可以是順序方式，也可以是鏈?zhǔn)椒绞酱鸢福赫_95 .環(huán)形隊(duì)列也存在空間溢出的問(wèn)題答案：正確96 .消除遞歸不一定需要使用棧。答案：正確97 .二分搜索算法是利用貪心法實(shí)現(xiàn)的算法。答案：錯(cuò)誤98 .動(dòng)態(tài)規(guī)劃算法通常是以自底向上的方式求解最優(yōu)解。答案：正確99 .貪心法不能解決 0/1背包問(wèn)題。答案：正確100 .深度優(yōu)先不是分支限界法的搜索方式。答案：正確101 .二分搜索算法是利用分治策略實(shí)現(xiàn)的算法。答案：正確102 .背包問(wèn)題不能使用貪心法解決。答案：錯(cuò)誤103 .單源最短路徑問(wèn)題不能使用貪心法解決。答案：錯(cuò)誤104 .時(shí)間復(fù)雜度低是衡量一個(gè)算法好壞的標(biāo)準(zhǔn)。答案：正確105 .歸并排

14、序不可以使用分治法求解。答案：錯(cuò)誤106 .拉斯維加斯算法有時(shí)找不到問(wèn)題的解。答案：正確107 .舍伍德算法有時(shí)候找不到問(wèn)題的解。答案：錯(cuò)誤108 . NP問(wèn)題都是不可能解決的問(wèn)題答案：錯(cuò)誤109 . P類(lèi)問(wèn)題包含在 NP類(lèi)問(wèn)題中。答案：正確110 . NP類(lèi)問(wèn)題包含在 P類(lèi)問(wèn)題中。答案：錯(cuò)誤111 . NP完全問(wèn)題是P類(lèi)問(wèn)題的子集答案：錯(cuò)誤112 .蒙特卡羅算法是概率算法的一種答案：正確113 .蒙特卡羅算法是貪心算法的一種答案：錯(cuò)誤114 .蒙特卡羅算法是回溯算法的一種答案：錯(cuò)誤115 .動(dòng)態(tài)規(guī)劃算法不是隨機(jī)化算法答案：正確116 .最優(yōu)子結(jié)構(gòu)性質(zhì)是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)答案：正確

15、117 .矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃算法來(lái)設(shè)計(jì)實(shí)現(xiàn)答案：正確118 . Strassen矩陣乘法是利用分治策略實(shí)現(xiàn)的算法答案：正確119 . Strassen矩陣乘法是利用貪心法實(shí)現(xiàn)的算法答案：錯(cuò)誤120 .貪心選擇性質(zhì)是貪心算法的基本要素答案：正確121 .以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為回溯算法答案：正確122 .算法分析的兩個(gè)主要方面是時(shí)間復(fù)雜度和空間復(fù)雜度分析答案：正確123 .實(shí)現(xiàn)最大子段和利用的算法是動(dòng)態(tài)規(guī)劃法答案：正確124 .實(shí)現(xiàn)最大子段和利用的算法是貪心法答案：錯(cuò)誤125 .實(shí)現(xiàn)最大子段和利用的算法是回溯法答案：錯(cuò)誤126 .廣度優(yōu)先是分支限界算法的一種搜索方式答案

16、：正確127 .廣度優(yōu)先是回溯算法的一種搜索方式答案：錯(cuò)誤128 .廣度優(yōu)先是貪心算法的一種搜索方式答案：錯(cuò)誤129 .舍伍德算法是概率算法的一種答案：正確130 .舍伍德算法是貪心算法的一種。答案：錯(cuò)誤131 .舍伍德算法是回溯算法的一種。答案：錯(cuò)誤132 .實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是動(dòng)態(tài)規(guī)劃法。答案：正確133 .計(jì)算機(jī)算法指的是解決問(wèn)題的方法和過(guò)程。答案：正確134 .根據(jù)排序元素所在位置的不同，排序分內(nèi)排序和外排序。答案：正確135 .根據(jù)排序元素所在位置的不同，排序分首排序和尾排序。答案：錯(cuò)誤136 .算法必須具備輸入、輸出和有窮性、確定性和可行性等5個(gè)特性。答案：正確137 .

17、算法必須具備輸入、輸出和易讀性、穩(wěn)定性和安全性等5個(gè)特性。答案：錯(cuò)誤138 .與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題經(jīng)分解得到的子問(wèn)題往往不是相互 獨(dú)立的答案：正確139 .與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題往往是相互獨(dú)立的 答案：錯(cuò)誤140 .二分搜索算法的基本思想是將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取 an/2與x進(jìn)行比較：如果x<an/2,則只要在數(shù)組 a的左半部繼續(xù)搜索 x 答案：正確141 .二分搜索算法的基本思想是將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取 an/2與x進(jìn)行比較：如果x>an/2,則只要在數(shù)組 a的左半部繼續(xù)搜索 x 答案：錯(cuò)誤142 .算法必

18、須具備輸入、輸出和可執(zhí)行T1E、可移植性和可擴(kuò)充性等5個(gè)特性。答案：錯(cuò)誤143 .適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿(mǎn)足最優(yōu)化原理和無(wú)后效性。答案：正確144 .適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿(mǎn)足最優(yōu)化原理和后效性。答案：錯(cuò)誤145 .二分查找只適用于順序存儲(chǔ)結(jié)構(gòu)。答案：正確146 .二分查找只適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。答案：錯(cuò)誤147 .應(yīng)用分治法的兩個(gè)前提是問(wèn)題的可分性和解的可歸并性。答案：正確148 .應(yīng)用分治法的兩個(gè)前提是問(wèn)題的可分性和解的復(fù)雜性。答案：錯(cuò)誤149 .對(duì)于n個(gè)元素的排序問(wèn)題。n=2時(shí)只要作1次比較即可排好序。 答案：正確150 .對(duì)于n個(gè)元素的排序問(wèn)題。n= 2時(shí)要作2次比較即可排好序。 答案：

19、錯(cuò)誤151 .分治法所能解決的問(wèn)題應(yīng)具有的關(guān)鍵特征是利用該問(wèn)題分解出的子問(wèn)題的解可以合并 為該問(wèn)題的解。答案：正確152 .分治法所能解決的問(wèn)題應(yīng)具有的關(guān)鍵特征是該問(wèn)題的規(guī)?？s小到一定的程度就可以容 易地解決。答案：錯(cuò)誤153 .直接或間接的調(diào)用自身的算法稱(chēng)為遞歸算法。答案：正確154 .直接或間接的調(diào)用自身的算法稱(chēng)為動(dòng)態(tài)規(guī)劃算法。答案：錯(cuò)誤155 .當(dāng)上下限表示相等時(shí)我們使用。表示法來(lái)描述算法代價(jià)。答案：正確156 .當(dāng)上下限表示相等時(shí)我們使用大。表示法來(lái)描述算法代價(jià)。答案：錯(cuò)誤157 .遞歸通常用棧來(lái)實(shí)現(xiàn)。答案：正確158 .遞歸通常用隊(duì)列來(lái)實(shí)現(xiàn)。答案：錯(cuò)誤159 .分治法的設(shè)計(jì)思想是將一

20、個(gè)難以直接解決的大問(wèn)題分割成規(guī)模較小的子問(wèn)題分別解決 子問(wèn)題最后將子問(wèn)題的解組合起來(lái)形成原問(wèn)題的解。這要求原問(wèn)題和子問(wèn)題的問(wèn)題規(guī)模不 同，問(wèn)題性質(zhì)相同。答案：正確160 . 0/1背包問(wèn)題不能用貪心算法求解。答案：正確161 .可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的。答案：正確162 .可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是難處理的。答案：錯(cuò)誤163 .需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是不能處理的。答案：錯(cuò)誤164 .遞歸通常用數(shù)組來(lái)實(shí)現(xiàn)。答案：錯(cuò)誤165 .哈密爾頓回路問(wèn)題是典型的NP完全問(wèn)題。答案：正確166 .排序問(wèn)題是典型的 NP完全問(wèn)題。167 .算法分析需要對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)

21、空間作定量分析。答案：正確168 .用數(shù)量級(jí)形式表示算法的執(zhí)行時(shí)間稱(chēng)為算法的時(shí)間復(fù)雜度。答案：正確169 .用數(shù)量級(jí)形式表示算法的執(zhí)行時(shí)間稱(chēng)為算法的空間復(fù)雜度。答案：錯(cuò)誤170 .最壞情況下，順序查找的時(shí)間復(fù)雜度為O(n)。答案：正確171 .最壞情況下，折半查找的時(shí)間復(fù)雜度為O(log2n)。答案：正確172 .合并排序的基本運(yùn)算是把兩個(gè)或多個(gè)有序序列合并成一個(gè)有序序列 答案：正確173 .最優(yōu)子結(jié)構(gòu)是動(dòng)態(tài)規(guī)劃算法的基本要素之一。答案：正確174 .快速排序算法是基于分治策略的一種排序算法。答案：正確175 .快速排序算法是基于回溯的一種排序算法。答案：錯(cuò)誤176 .快速排序算法是基于貪心法

22、的一種排序算法。答案：錯(cuò)誤177 .貪心法通常以自頂向下的方式求解最優(yōu)解。答案：正確178 .分治法通常以自頂向下的方式求解最優(yōu)解。答案：錯(cuò)誤179 .回溯法通常以自頂向下的方式求解最優(yōu)解。答案：錯(cuò)誤180 .不斷回頭尋找目標(biāo)的方法稱(chēng)為回溯法。答案：正確Word資料181 .不斷回頭尋找目標(biāo)的方法稱(chēng)為概率算法。答案：錯(cuò)誤182 .不斷回頭尋找目標(biāo)的方法稱(chēng)為貪心法。答案：錯(cuò)誤183 .拉斯維加斯算法找到的解一定是正確的。答案：正確184 .拉斯維加斯算法找到的解正確與否不確定。答案：錯(cuò)誤185 . 記號(hào)在算法復(fù)雜性的表示法中表示緊致界。答案：正確186 . 記號(hào)在算法復(fù)雜性的表示法中表示上界。答

23、案：錯(cuò)誤187 . 記號(hào)在算法復(fù)雜性的表示法中表示下界。答案：錯(cuò)誤188 . 一個(gè)算法是對(duì)特定問(wèn)題求解的一種描述，它是指令的有限序列。答案：正確189 . 一個(gè)遞歸算法必須包括終止條件和遞歸部分。答案：正確190 .棧和隊(duì)列的共同點(diǎn)是只允許在端點(diǎn)處插入和刪除元素。答案：正確191 .排序趟數(shù)與原始序列有關(guān)的排序方法是冒泡排序法。答案：正確192 .棧和隊(duì)列的共同點(diǎn)都是先進(jìn)先出。答案：錯(cuò)誤193 .棧和隊(duì)列的共同點(diǎn)都是先進(jìn)后出。答案：錯(cuò)誤194 .排序趟數(shù)與原始序列有關(guān)的排序方法是選擇排序法。答案：錯(cuò)誤195 .在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實(shí)際價(jià)值的是最壞情況下的時(shí) 間復(fù)雜度

24、。答案：正確196 .在算法的三種情況下的復(fù)雜性中，可操作性最好且最有實(shí)際價(jià)值的是最好情況下的時(shí) 間復(fù)雜度。答案：錯(cuò)誤197 .若一個(gè)算法的時(shí)間復(fù)雜度用T（n）表示，其中n的含義是問(wèn)題規(guī)模。答案：正確198 .合并排序法的基本思想是：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)每個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。答案：正確選擇題:1 .二分搜索算法是利用（ A ）實(shí)現(xiàn)的算法。選項(xiàng)A.分治策略選項(xiàng)B.動(dòng)態(tài)規(guī)劃法選項(xiàng)C.貪心法選項(xiàng)D.回溯法答案：2 .回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹(shù)是（ B ）。選項(xiàng)A.子集樹(shù)選項(xiàng)B.排列樹(shù)選項(xiàng)C.深度優(yōu)先生成樹(shù)選項(xiàng)D.廣度

25、優(yōu)先生成樹(shù)答案：3 .下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）。選項(xiàng)A.備忘錄法選項(xiàng)B.動(dòng)態(tài)規(guī)劃法選項(xiàng)C.貪心法選項(xiàng)D.回溯法答案：4 .下面不是分支界限法搜索方式的是（ D ）。選項(xiàng)A.廣度優(yōu)先選項(xiàng)B.最小耗費(fèi)優(yōu)先選項(xiàng)C.最大效益優(yōu)先選項(xiàng)D.深度優(yōu)先答案：5 .采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算 法的時(shí)間復(fù)雜度( B )。A、O ()B、O ( n log n)C、O ()D、O (n )6 .分支限界法求解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是( B )。A、最小堆B、最大堆C、棧D、數(shù)組7、下面問(wèn)題(B )不能使用貪心法解決。A單源最短

26、路徑問(wèn)題B N皇后問(wèn)題C最小花費(fèi)生成樹(shù)問(wèn)題D背包問(wèn)題答案：8 .下列算法中不能解決 0/1背包問(wèn)題的是( A )。A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法答案：9 .背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為(B )。A、 O (n )B、O (nlogn )C、O ()D、 O (n)答案：10 .二分搜索算法是利用( A )實(shí)現(xiàn)的算法。A.分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：11 .下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是( B )。A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解 答案：12.最大效益優(yōu)先是（ A ）的一種搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法

27、答案：13、在下列算法中有時(shí)找不到問(wèn)題解的是（ B ）。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：14.下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：14.下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：15、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（ C ）。A運(yùn)行速度快B占用空間少C時(shí)間復(fù)雜度低D代碼短答案：16、以下不可以使用分治法求解的是（ D ）A、棋盤(pán)覆蓋問(wèn)題B、選擇問(wèn)題C、歸并排序Word資料D、 O （n）答案：Word資料17.實(shí)現(xiàn)循環(huán)賽日程表

28、利用的算法是（ A ）A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：18、下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法答案：19 .下面不是分支界限法搜索方式的是（ D ）。A、廣度優(yōu)先B、最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先答案：D )。20 .下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：21 .備忘錄方法是那種算法的變形。 （B ）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：22 .哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（ B ）A、 O （n）B、O （nlo

29、gn ）C、O （）23 .最長(zhǎng)公共子序列算法利用的算法是（ B ）A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：24 .實(shí)現(xiàn)棋盤(pán)覆蓋算法利用的算法是（ A ）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：25 .下面是貪心算法的基本要素的是（A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解26 .回溯法的效率不依賴(lài)于下列哪些因素（ D ）。A.滿(mǎn)足顯約束的值的個(gè)數(shù)C.計(jì)算限界函數(shù)的時(shí)間B.計(jì)算約束函數(shù)的時(shí)間D.確定解空間的時(shí)間27.下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（ B ）。A.遞歸函數(shù)B.剪枝函數(shù)C.隨機(jī)數(shù)函數(shù)D.搜索函數(shù)28、下面關(guān)于 NP問(wèn)題說(shuō)法正

30、確的是（ B ）。A. NP問(wèn)題都是不可能解決的問(wèn)題B. P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中C. NP完全問(wèn)題是P類(lèi)問(wèn)題的子集D. NP類(lèi)問(wèn)題包含在 P類(lèi)問(wèn)題中29、蒙特卡羅算法是（ B ）的一種。A.分支界限算法B.概率算法C.貪心算法D.回溯算法答案：30 .下列哪一種算法不是隨機(jī)化算法（C ）。A.蒙特卡羅算法B.拉斯維加斯算法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法答案：31 . （ 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ì)答案：32 .矩陣連乘問(wèn)題的算法可由（ B ）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)態(tài)規(guī)劃算法C、貪心算法D、回溯算法答案：3

31、3、Strassen矩陣乘法是利用（ A ）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：34、使用分治法求解不需要滿(mǎn)足的條件是（ A ）。A子問(wèn)題必須是一樣的B子問(wèn)題不能夠重復(fù)C子問(wèn)題的解可以合并D原問(wèn)題和子問(wèn)題使用相同的方法求解答案：35、回溯法搜索狀態(tài)空間樹(shù)是按照（ C ）的順序。A中序遍歷B廣度優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷答案：36、實(shí)現(xiàn)合并排序利用的算法是（ A ）A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：37、下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（ D ）A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子空間重疊性質(zhì)答案：38.采用廣度優(yōu)先策略搜索的算法

32、是（ A ）A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法答案：39、在下列算法中得到的解未必正確的是（ A ）A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：40 .實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（ C ）A、貪心法B、動(dòng)態(tài)規(guī)劃法C、分治策略D、回溯法答案：41 . 0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（ A ）A、 O （n）B、O （nlogn ）C、O （）D、 O （n）答案：42 .貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（ B ）A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解答案：43 .實(shí)現(xiàn)最大子段和利用的算法是（ B ）。A、分治策略 B、動(dòng)態(tài)

33、規(guī)劃法C、貪心法D、回溯法 答案：44 .優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（C ）A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)答案：45、廣度優(yōu)先是（A ）的一種搜索方式。A、分支界限算法B、動(dòng)態(tài)規(guī)劃法C、貪心算法D、回溯算法答案：46、舍伍德算法是（ B ）的一種A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：47、在下列算法中有時(shí)找不到問(wèn)題解的是（ B ）A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法答案：48下列哪一種算法是隨機(jī)化算法（ D ）。A.貪心算法B.回溯法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法答案：49. 一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解

34、的關(guān)鍵特征是問(wèn)題的（B ）。A、重疊子問(wèn)題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解答案：52 .以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為（ D ）。A、分支界限算法B、概率算法C、貪心算法D、回溯算法答案：53 .實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是（ B ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法54 .算法分析的兩個(gè)主要方面是（ A ）。A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡(jiǎn)單性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜度和程序復(fù)雜度55 .計(jì)算機(jī)算法指的是（ C ）。A.計(jì)算方法B.排序方法C.解決問(wèn)題的方法和過(guò)程D.調(diào)度方法56 .多階段決策問(wèn)題就是要在可以選擇的那些策略中間選取一個(gè)（

35、A ）策略使在預(yù)定的標(biāo) 準(zhǔn)下達(dá)到最好的效果。A.最優(yōu)B.最差C.平衡D.任意57 .根據(jù)排序元素所在位置的不同，排序分（ A ）。A.內(nèi)排序和外排序B.首排序和尾排序C.順序排序和逆序排序D.堆排序和棧排序58 .算法必須具備輸入、輸出和（ B ）等5個(gè)特性。A.可執(zhí)行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性 C.確定性、有窮性和穩(wěn)定性 D.易讀性、穩(wěn)定性和安全性59 .與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題（ A ）。A.經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的B.經(jīng)分解得到子問(wèn)題往往是互相獨(dú)立的C.經(jīng)分解得到子問(wèn)題往往是互相交叉的D.經(jīng)分解得到子問(wèn)題往往是任意的60 .二分搜索算法

36、的基本思想是將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取an/2與x進(jìn)行比較：如果（A ）,則只要在數(shù)組a的左半部繼續(xù)搜索x。A. xv an/2B. x=an/2C. x>an/2D. x>=an/261 .活動(dòng)安排問(wèn)題就是在所給的活動(dòng)集合中，選出（ C ）的相容活子集。A.最小B.任意C.最大D. 一個(gè)62 .在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是 （B ）。A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集樹(shù)問(wèn)題63 .適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿(mǎn)足（ D ）。A.最優(yōu)化原理B.無(wú)前效性C.最優(yōu)化原理和后效性D.最優(yōu)化原理和無(wú)后效性64 .

37、算法的每種運(yùn)算必須要有確切的定義不能有二義性，以下符合算法確定性運(yùn)算的是 （B ）。A. 5/0B.將6或7與x相加C.未賦值變量參與運(yùn)算D. f（n尸f（n-1）+2 , F（1）=10 , n 為自然數(shù)65 .直接或間接的調(diào)用自身的算法稱(chēng)為（ B ）。A.貪心算法B.遞歸算法C.迭代算法D.動(dòng)態(tài)規(guī)劃算法66 .二分查找只適用(B )存儲(chǔ)結(jié)構(gòu)。A.堆B.順序C.任意順序D.棧67 .應(yīng)用分治法的兩個(gè)前提是( A )。A.問(wèn)題的可分性和解的可歸并性B.問(wèn)題的可分性和解的存在性C.問(wèn)題的復(fù)雜性和解的可歸并性D.問(wèn)題的可分性和解的復(fù)雜性68 .優(yōu)先隊(duì)列的分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，并按

38、優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值p來(lái)表示。結(jié)點(diǎn)優(yōu)先級(jí)的高低與p值大小相關(guān)，根據(jù)問(wèn)題的不同情況，采用(C )來(lái)描述優(yōu)先隊(duì)列。 A.先進(jìn)先出隊(duì)列B.后進(jìn)先出的棧C.最大堆或最小堆D.隨機(jī)序列69 .階乘函數(shù)用遞歸定義Public static int factorial (int n) if (n=0 ) return 1; return(B )： A. n*factorial(n)B. n*factorial(n-1) C. n*factorial(n-2) D. n*factorial(n+1)70 .

39、( B )能夠求得問(wèn)題的解但卻無(wú)法有效地判定解的正確性。A.數(shù)值概率算法B.蒙特卡羅算法C.拉斯維加斯算法D.舍伍得算法71 .對(duì)于n個(gè)元素的排序問(wèn)題。n=2時(shí)只要作(C )次比較即可排好序。A. 3B. 2C. 1D. 472. 一般地講，當(dāng)一個(gè)問(wèn)題的所有子問(wèn)題都至少要解一次時(shí)，用動(dòng)態(tài)規(guī)劃算法和備忘錄算法 相比：（B ）。A.效果一樣B.動(dòng)態(tài)規(guī)劃效果好C.備忘錄方法效果好D.無(wú)法判斷哪個(gè)效果好T上搜索問(wèn)題的解，二者（B ）。則分治法要做許多不必要的工作，重復(fù)地解公73 .分支限界法 與回溯法都是在問(wèn)題的解空間樹(shù)A.求解目標(biāo)不同搜索方式相同B.求解目標(biāo)不同搜索方式也不同C.求解目標(biāo)相同搜索方式

40、不同D.求解目標(biāo)相同搜索方式也相同74 .遞歸算法不能適用以下場(chǎng)合（ D ）。A.數(shù)據(jù)的定義形式按遞歸定義B.數(shù)據(jù)之間的關(guān)系即數(shù)據(jù)結(jié)構(gòu)按遞歸定義C.問(wèn)題解法按遞歸算法實(shí)現(xiàn)D.概率問(wèn)題75 .若當(dāng)子問(wèn)題之間包含公共的子子問(wèn)題時(shí)， 共的子問(wèn)題，此時(shí)一般用（ A ）法較好。 A.動(dòng)態(tài)規(guī)劃B.分治C.貪心D.概率76 .分治法所能解決的問(wèn)題應(yīng)具有的關(guān)鍵特征是（ C ）。A.該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決B.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題C.利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解D.該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的77 .對(duì)于貨箱裝船問(wèn)題根據(jù)貪心策略首先選擇（ A

41、 ）的貨箱然后選 （A ）的貨箱如此下 去直到所有貨箱均裝上船或船上不能再容納其他任何一個(gè)貨箱。A.最輕次輕B.最重次重C.最輕次重D.最重次輕78 .用回溯法解n后問(wèn)題時(shí)，用完全 n叉樹(shù)表示解空間?？尚行约s束place剪去不滿(mǎn)足行、列和斜線(xiàn)約束的子樹(shù)，place中的if判斷條件應(yīng)為（A ）。A. （Math.abs（k-j）=Math.abs（xj-xkD）|xj=xkDB. (Math.abs(k-j)=Math.abs(xj-xkD) C. (xj-xk)D.以上都不正確79 .分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其(D )兒子結(jié)點(diǎn)(分支)，然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展

42、對(duì)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值(限界)，并根據(jù)這些已計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹(shù)上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。 A. 一個(gè) B.二個(gè) C.任意多個(gè) D.所有的80 .能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)題還有一個(gè)顯著特征( D )這個(gè)性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的 必要條件，但是如果該性質(zhì)無(wú)法滿(mǎn)足，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。A.子問(wèn)題的可求解性B.子問(wèn)題的獨(dú)立性C.子問(wèn)題的可合并性D.子問(wèn)題的重疊性81 .在任何一個(gè)2k 2k的棋盤(pán)覆蓋中，用到的L型骨牌個(gè)數(shù)恰為( A )。k

43、A. (41)/3B. (4k1)/2C. (2k1)/3D. (2k1)/282 .以Bitonic旅行路線(xiàn)問(wèn)題為例，動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為( C )。 A. O(n)B. O(n!)C. O(n2) D. O(n3)83 . 一個(gè)算法應(yīng)該包含如下幾條性質(zhì)除了( A )。 A.二義性B.有限性 C.正確性 D,可終止性84 .解決一個(gè)問(wèn)題通常有多種方法。若說(shuō)一個(gè)算法有效”是指（D ）。A.這個(gè)算法能在一定的時(shí)間和空間資源限制內(nèi)將問(wèn)題解決B.這個(gè)算法能在人的反應(yīng)時(shí)間內(nèi)將問(wèn)題解決C.這個(gè)算法比其他已知算法都更快地將問(wèn)題解決D. A 和 C85 .當(dāng)輸入規(guī)模為n時(shí)算法增長(zhǎng)率最小的是（B ）。A.

44、5nB. 2010g 2 nC. 2n2D. 3nlog3n86 .漸進(jìn)算法分析是指（B ）。A.算法在最佳情況、最差情況和平均情況下的代價(jià)B.當(dāng)規(guī)模逐步往極限方向增大時(shí)對(duì)算法資源開(kāi)銷(xiāo)增長(zhǎng)率”上的簡(jiǎn)化分析C.數(shù)據(jù)結(jié)構(gòu)所占用的空間D.在最小輸入規(guī)模下算法的資源代價(jià)87 .當(dāng)上下限表達(dá)式相等時(shí)我們使用下列哪種表示法來(lái)描述算法代價(jià)？（ C ）A.大O表不法B.大表不法C. O表不法D.小o表不法88 .采用 順序搜索法”從一個(gè)長(zhǎng)度為 N的隨機(jī)分布數(shù)組中搜尋值為K的元素，以下對(duì)順序搜索法分析正確的是（B ）。A.最佳情況、最差情況和平均情況下順序搜索法的漸進(jìn)代價(jià)都相同B.最佳情況的漸進(jìn)代價(jià)要好于最差情

45、況和平均情況的漸進(jìn)代價(jià)C.最佳情況和平均情況的漸進(jìn)代價(jià)要好于最差情況的漸進(jìn)代價(jià)D.最佳情況的漸進(jìn)代價(jià)要好于平均情況的漸進(jìn)代價(jià)而平均情況的漸進(jìn)代價(jià)要好于最差情況 的漸進(jìn)代價(jià)89 .遞歸通常用（C ）來(lái)實(shí)現(xiàn)。A.有序的線(xiàn)性表B.隊(duì)列C.棧D.數(shù)組90 .分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問(wèn)題分割成規(guī)模較小的子問(wèn)題分別解決子問(wèn)題最后將子問(wèn)題的解組合起來(lái)形成原問(wèn)題的解。這要求原問(wèn)題和子問(wèn)題（C ）。A問(wèn)題規(guī)模相同，問(wèn)題性質(zhì)相同B問(wèn)題規(guī)模相同，問(wèn)題性質(zhì)不同C問(wèn)題規(guī)模不同，問(wèn)題性質(zhì)相同D問(wèn)題規(guī)模不同，問(wèn)題性質(zhì)不同91 .在尋找n個(gè)元素中第k小元素問(wèn)題中如快速排序算法思想運(yùn)用分治算法對(duì)n個(gè)元素進(jìn)行劃分

46、如何選擇劃分基準(zhǔn)下面（D ）答案解釋最合理。A.隨機(jī)選擇一個(gè)元素作為劃分基準(zhǔn)B.取子序列的第一個(gè)元素作為劃分基準(zhǔn)C.用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)D.以上皆可行。但不同方法算法復(fù)雜度上界可能不同92 .對(duì)于01背包問(wèn)題和背包問(wèn)題的解法下面（ C ）答案解釋正確。A. 01背包問(wèn)題和背包問(wèn)題都可用貪心算法求解B. 01背包問(wèn)題可用貪心算法求解但背包問(wèn)題則不能用貪心算法求解C. 01背包問(wèn)題不能用貪心算法求解但可以使用動(dòng)態(tài)規(guī)劃或搜索算法求解而背包問(wèn)題則可以用貪心算法求解D.因?yàn)?1背包問(wèn)題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)所以不能用貪心算法求解93 .關(guān)于回溯搜索法的介紹下面（ D ）是不正確描述。A.回溯法

47、有通用解題法”之稱(chēng)它可以系統(tǒng)地搜索一個(gè)問(wèn)題的所有解或任意解B.回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C.回溯算法在生成解空間的任一結(jié)點(diǎn)時(shí)先判斷該結(jié)點(diǎn)是否可能包含問(wèn)題的解如果肯定不包含則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索逐層向祖先結(jié)點(diǎn)回溯D.回溯算法需要借助隊(duì)列這種結(jié)構(gòu)來(lái)保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑94 .關(guān)于回溯算法和分支限界法以下（ A ）是不正確描述。A回溯法中每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)B分支限界法中活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)在這些兒子結(jié)點(diǎn)中 那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄其余兒子加入活結(jié)點(diǎn)表中C回溯法采用深度優(yōu)先的結(jié)點(diǎn)生成策略D分支限界法

48、采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先最大效益優(yōu)先的結(jié)點(diǎn)生成策略95 .優(yōu)先隊(duì)列通常用以下（ B ）數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。A.棧B.堆C.隊(duì)列D.二叉查找樹(shù)96 .在分支限界算法中根據(jù)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式可有幾種常用分類(lèi), 以下（D ）描述最為準(zhǔn)確。A采用FIFO隊(duì)列的隊(duì)列式分支限界法B采用最小值堆的優(yōu)先隊(duì)列式分支限界法C采用最大值堆的優(yōu)先隊(duì)列式分支限界法D以上都常用針對(duì)具體問(wèn)題可以選擇采用其中某種更為合適的方式97 .對(duì)布線(xiàn)問(wèn)題以下（ C ）是不正確描述。A布線(xiàn)問(wèn)題的解空間是一個(gè)圖B可以對(duì)方格陣列四周設(shè)置圍墻，即增設(shè)標(biāo)記的附加方格的預(yù)處理，使得算法簡(jiǎn)化對(duì)邊界的判定C采用廣度優(yōu)先的標(biāo)號(hào)法找到從

49、起點(diǎn)到終點(diǎn)的布線(xiàn)方案這個(gè)方案如果存在的話(huà)不一定是最 短的D采用先入先出的隊(duì)列作為活結(jié)點(diǎn)表以，終點(diǎn)b為擴(kuò)展結(jié)點(diǎn)或活結(jié)點(diǎn)隊(duì)列為空作為算法結(jié)束條件98 .下述表達(dá)不正確的是（ D ）。A. n2/2 2n的漸進(jìn)表達(dá)式上界函數(shù)是O（2n）B. n2 /2 2n的漸進(jìn)表達(dá)式下界函數(shù)是（2n）.3C. logn的漸進(jìn)表達(dá)式上界函數(shù)是 O（logn） .3 . 3、D. logn的漸進(jìn)表達(dá)式下界函數(shù)是（n ）99 .當(dāng)輸入規(guī)模為n時(shí)，算法增長(zhǎng)率最大的是（ A ）。nA. 5B. 20log 2 nC. 2n2D. 3nlog3n100. T(n)表示當(dāng)輸入規(guī)模為 n時(shí)的算法效率，以下算法效率最優(yōu)的是( C

50、)。A. T(n)=T(n-1)+1 , T(1)=1 _2B. T(n)=2nC. T(n)=T(n/2)+1 , T(1)=1D. T(n)=3nlog 2n101.有9個(gè)村莊，其坐標(biāo)位置如下表所示:i123456789x(i)123456789y(i)123456789現(xiàn)在要蓋一所郵局為這9個(gè)村莊服務(wù)，請(qǐng)問(wèn)郵局應(yīng)該蓋在( C )才能使郵局到9個(gè)村莊的距離和最短。A. (4.5, 0)B. (4.5, 4.5)C. (5, 5)D. (5, 0)102 . n個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水水桶有大有小水桶必須打滿(mǎn)水水流恒定。如下(A ) 說(shuō)法不正確A.讓水桶大的人先打水可以使得每個(gè)人

51、排隊(duì)時(shí)間之和最小B.讓水桶小的人先打水可以使得每個(gè)人排隊(duì)時(shí)間之和最小C.讓水桶小的人先打水在某個(gè)確定的時(shí)間t內(nèi)可以讓盡可能多的人打上水D.若要在盡可能短的時(shí)間內(nèi)n個(gè)人都打完水按照什么順序其實(shí)都一樣103 .對(duì)于含有n個(gè)元素的子集樹(shù)問(wèn)題，最壞情況下其解空間的葉結(jié)點(diǎn)數(shù)目為( B )。A. n!B. 2nC. 2n 1 1nD. n!/i!i 1104 .以下關(guān)于判定問(wèn)題難易處理的敘述中正確的是( C )A.可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是難處理的B.需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的C.可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是易處理的D.需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是不能處理的105 .回溯法

52、在解空間樹(shù)T上的搜索方式是(A )A.深度優(yōu)先B.廣度優(yōu)先C.最小耗費(fèi)優(yōu)先D.活結(jié)點(diǎn)優(yōu)先106 .設(shè)f(N), g(N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù) C和自然數(shù)N0,使得當(dāng) N小0時(shí)有f(N) 9g(N),則稱(chēng)函數(shù)f(N)當(dāng)N充分大時(shí)有上界 g(N),記作f(N)=O(g(N),即f(N)I階（A ） g（N）的階。A.不高于B.不低于C.等價(jià)于D.逼近107 .以下（C ）不能在線(xiàn)性時(shí)間完成排序A.計(jì)數(shù)排序B基數(shù)排序C堆排序D.桶排序108 .以下（ A ）不一定得到問(wèn)題的最優(yōu)解A.貪心算法B.回溯算法C.分支限界法D.動(dòng)態(tài)規(guī)劃法109 .下列不屬于一個(gè)好的算法應(yīng)具有的特性的是（C ）。A.正確性B.簡(jiǎn)明性C.無(wú)限性D.最優(yōu)性110 .算法分析是（C ）。A.將算法用某種程序設(shè)計(jì)語(yǔ)言恰當(dāng)?shù)乇硎境鰜?lái)B.在抽象數(shù)據(jù)集合上執(zhí)行程序，以確定是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果C.對(duì)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量分析D.證明算法對(duì)所有可能的合法輸入都能算出正確的答案111 .學(xué)校要舉行運(yùn)動(dòng)會(huì)，請(qǐng)你設(shè)計(jì)一個(gè)能夠?qū)\(yùn)動(dòng)員分?jǐn)?shù)自動(dòng)排序的軟件，如果要設(shè)計(jì)此軟件，以下最好的方法和步驟是（C ）。A.分析問(wèn)題，編寫(xiě)程序，設(shè)計(jì)算法，調(diào)試程序B.設(shè)計(jì)算法，編