完美WORD格式 計算機算法設計與分析習題及答案一選擇題1、二分搜索算法是利用（ A ）實現的算法。A、分治策略 B、動態規劃法 C、貪心法 D、回溯法2、下列不是動態規劃算法基本步驟的是（ A ）。A、找出最優解的性質 B、構造最優解 C、算出最優解 D、定義最優解3、最大效益優先是（A ）的一搜索方式。A、分支界限法 B、動態規劃法 C、貪心法 D、回溯法4. 回溯法解旅行售貨員問題時的解空間樹是（ A ）。A、子集樹 B、排列樹 C、深度優先生成樹 D、廣度優先生成樹5下列算法中通常以自底向上的方式求解最優解的是（B ）。A、備忘錄法 B、動態規劃法 C、貪心法 D、回溯法6、衡量一個算法好壞的標準是（ C ）。A 運行速度快 B 占用空間少 C 時間復雜度低 D 代碼短7、以下不可以使用分治法求解的是（ D ）。A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題8. 實現循環賽日程表利用的算法是（A ）。A、分治策略 B、動態規劃法 C、貪心法 D、回溯法9下面不是分支界限法搜索方式的是（D ）。A、廣度優先 B、最小耗費優先 C、最大效益優先 D、深度優先10下列算法中通常以深度優先方式系統搜索問題解的是（D ）。A、備忘錄法 B、動態規劃法 C、貪心法 D、回溯法11.備忘錄方法是那種算法的變形。（ B ）A、分治法 B、動態規劃法 C、貪心法 D、回溯法12哈夫曼編碼的貪心算法所需的計算時間為（B ）。A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）13分支限界法解最大團問題時，活結點表的組織形式是（B ）。A、最小堆 B、最大堆 C、棧 D、數組14最長公共子序列算法利用的算法是（B）。A、分支界限法 B、動態規劃法 C、貪心法 D、回溯法15實現棋盤覆蓋算法利用的算法是（A ）。A、分治法 B、動態規劃法 C、貪心法 D、回溯法16.下面是貪心算法的基本要素的是（C ）。A、重疊子問題 B、構造最優解 C、貪心選擇性質 D、定義最優解17.回溯法的效率不依賴于下列哪些因素（ D ）A.滿足顯約束的值的個數 B. 計算約束函數的時間 C.計算限界函數的時間 D. 確定解空間的時間18.下面哪種函數是回溯法中為避免無效搜索采取的策略（B ）A遞歸函數 B.剪枝函數 C。隨機數函數 D.搜索函數19. （D）是貪心算法與動態規劃算法的共同點。A、重疊子問題 B、構造最優解 C、貪心選擇性質 D、最優子結構性質20. 矩陣連乘問題的算法可由（ B ）設計實現。A、分支界限算法 B、動態規劃算法 C、貪心算法 D、回溯算法21. 分支限界法解旅行售貨員問題時，活結點表的組織形式是（ A ）。A、最小堆 B、最大堆 C、棧 D、數組22、Strassen矩陣乘法是利用（A ）實現的算法。A、分治策略 B、動態規劃法 C、貪心法 D、回溯法23、使用分治法求解不需要滿足的條件是（ A ）。A 子問題必須是一樣的 B 子問題不能夠重復C 子問題的解可以合并 D 原問題和子問題使用相同的方法解24、下面問題（ B ）不能使用貪心法解決。A 單源最短路徑問題 B N皇后問題 C 最小生成樹問題 D 背包問題25、下列算法中不能解決0/1背包問題的是（ A ）A 貪心法 B 動態規劃 C 回溯法 D 分支限界法26、回溯法搜索狀態空間樹是按照（ C ）的順序。A 中序遍歷 B 廣度優先遍歷 C 深度優先遍歷 D 層次優先遍歷27實現合并排序利用的算法是（A ）。A、分治策略 B、動態規劃法 C、貪心法 D、回溯法28下列是動態規劃算法基本要素的是（D ）。A、定義最優解 B、構造最優解 C、算出最優解 D、子問題重疊性質29下列算法中通常以自底向下的方式求解最優解的是（ B ）。A、分治法 B、動態規劃法 C、貪心法 D、回溯法30采用廣度優先策略搜索的算法是（A ）。A、分支界限法 B、動態規劃法 C、貪心法 D、回溯法31、合并排序算法是利用（ A ）實現的算法。A、分治策略 B、動態規劃法 C、貪心法 D、回溯法32、背包問題的貪心算法所需的計算時間為（ B ）A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）33實現大整數的乘法是利用的算法（C ）。A、貪心法 B、動態規劃法 C、分治策略 D、回溯法340-1背包問題的回溯算法所需的計算時間為（A ）A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）35采用最大效益優先搜索方式的算法是（A）。A、分支界限法 B、動態規劃法 C、貪心法 D、回溯法36貪心算法與動態規劃算法的主要區別是（B）。A、最優子結構 B、貪心選擇性質 C、構造最優解 D、定義最優解37. 實現最大子段和利用的算法是（B ）。A、分治策略 B、動態規劃法 C、貪心法 D、回溯法38.優先隊列式分支限界法選取擴展結點的原則是（ C ）。A、先進先出 B、后進先出 C、結點的優先級 D、隨機39.背包問題的貪心算法所需的計算時間為（ B ）。A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）40、廣度優先是（A ）的一搜索方式。A、分支界限法 B、動態規劃法 C、貪心法 D、回溯法41. 一個問題可用動態規劃算法或貪心算法求解的關鍵特征是問題的（ B ）。A、重疊子問題 B、最優子結構性質 C、貪心選擇性質 D、定義最優解42采用貪心算法的最優裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復雜度為 ( B ) 。A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）43. 以深度優先方式系統搜索問題解的算法稱為 ( D ) 。A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法44. 實現最長公共子序列利用的算法是（B ）。A、分治策略 B、動態規劃法 C、貪心法 D、回溯法A. void hanoi(int n, int A, int C, int B) if (n 0) hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); 45. Hanoi塔問題如下圖所示。現要求將塔座A上的的所有圓盤移到塔座B上，并仍按同樣順序疊置。移動圓盤時遵守Hanoi塔問題的移動規則。由此設計出解Hanoi塔問題的遞歸算法正確的為：（B）Hanoi塔B. void hanoi(int n, int A, int B, int C) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); C. void hanoi(int n, int C, int B, int A) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C, int A, int B) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 46. 動態規劃算法的基本要素為（ C ）A. 最優子結構性質與貪心選擇性質 B重疊子問題性質與貪心選擇性質C最優子結構性質與重疊子問題性質 D. 預排序與遞歸調用47. 能采用貪心算法求最優解的問題，一般具有的重要性質為：（ A ）A. 最優子結構性質與貪心選擇性質 B重疊子問題性質與貪心選擇性質C最優子結構性質與重疊子問題性質 D. 預排序與遞歸調用48. 回溯法在問題的解空間樹中，按（ D ）策略，從根結點出發搜索解空間樹。A.廣度優先 B. 活結點優先 C.擴展結點優先 D. 深度優先49. 分支限界法在問題的解空間樹中，按（ A ）策略，從根結點出發搜索解空間樹。 A.廣度優先 B. 活結點優先 C.擴展結點優先 D. 深度優先50. 程序塊（ A ）是回溯法中遍歷排列樹的算法框架程序。void backtrack (int t) if (tn) output(x); else for (int i=t;in) output(x); else for (int i=0;in) output(x); else for (int i=0;in) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); D.51. 常見的兩種分支限界法為（D）A. 廣度優先分支限界法與深度優先分支限界法；B. 隊列式（FIFO）分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊列式（FIFO）分支限界法與優先隊列式分支限界法；二、填空題 1.算法的復雜性有 時間 復雜性和 空間 復雜性之分。2、程序是 算法用某種程序設計語言的具體實現。3、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。4. 矩陣連乘問題的算法可由 動態規劃 設計實現。5、算法是指解決問題的 一種方法 或 一個過程 。6、從分治法的一般設計模式可以看出，用它設計出的程序一般是 遞歸算法 。7、問題的 最優子結構性質 是該問題可用動態規劃算法或貪心算法求解的關鍵特征。8、以深度優先方式系統搜索問題解的算法稱為 回溯法 。9、計算一個算法時間復雜度通常可以計算 循環次數 、 基本操作的頻率 或計算步。10、解決0/1背包問題可以使用動態規劃、回溯法和分支限界法，其中不需要排序的是 動態規劃 ，需要排序的是 回溯法 ，分支限界法 。11、使用回溯法進行狀態空間樹裁剪分支時一般有兩個標準：約束條件和目標函數的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標函數的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。12、 貪心選擇性質 是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。13、矩陣連乘問題的算法可由 動態規劃 設計實現。14.貪心算法的基本要素是 貪心選擇 性質和 最優子結構 性質 。15. 動態規劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。16.算法是由若干條指令組成的有窮序列，且要滿足輸入、 輸出 、確定性和 有限性 四條性質。17、大整數乘積算法是用 分治法 來設計的。18、以廣度優先或以最小耗費方式搜索問題解的算法稱為 分支限界法 。19、 貪心選擇性質 是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。20.快速排序算法是基于 分治策略 的一種排序算法。21.動態規劃算法的兩個基本要素是. 最優子結構 性質和 重疊子問題 性質 。 22.回溯法是一種既帶有 系統性 又帶有 跳躍性 的搜索算法。 23.分支限界法主要有 隊列式（FIFO） 分支限界法和 優先隊列式 分支限界法。24.分支限界法是一種既帶有 系統性 又帶有 跳躍性 的搜索算法。25.回溯法搜索解空間樹時，常用的兩種剪枝函數為 約束函數 和 限界函數 。26.任何可用計算機求解的問題所需的時間都與其 規模 有關。27.快速排序算法的性能取決于 劃分的對稱性 。28.所謂貪心選擇性質是指 所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到 。29.所謂最優子結構性質是指 問題的最優解包含了其子問題的最優解 。30.回溯法是指 具有限界函數的深度優先生成法 。31.用回溯法解題的一個顯著特征是在搜索過程中動態產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為 O(h(n) ）。32.回溯法的算法框架按照問題的解空間一般分為 子集樹 算法框架與 排列樹 算法框架。33.用回溯法解0/1背包問題時，該問題的解空間結構為 子集樹 結構。34.用回溯法解批處理作業調度問題時，該問題的解空間結構為 排列樹 結構。35.旅行售貨員問題的解空間樹是 排列樹 。三、算法填空1.背包問題的貪心算法void Knapsack(int n,float M,float v,float w,float x)/重量為w1.n,價值為v1.n的 n個物品，裝入容量為M的背包/用貪心算法求最優解向量x1.nint i; Sort(n,v,w); for (i=1;i=n;i+) xi=0; float c=M; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi;2.最大子段和: 動態規劃算法int MaxSum(int n, int a) int sum=0, b=0； /sum存儲當前最大的bj, b存儲bj for (int j=1； j0) b+= aj ； else b=ai; ； /一旦某個區段和為負，則從下一個位置累和 if(bsum) sum=b; return sum； 3.貪心算法求活動安排問題templatevoid GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false;4.快速排序templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 5. 回溯法解迷宮問題 迷宮用二維數組存儲，用H表示墻,O表示通道int x1,y1,success=0; /出口點void MazePath(int x,int y)/遞歸求解:求迷宮maze從入口(x,y)到出口(x1,y1)的一條路徑 mazexy=*; /路徑置為* if (x=x1)&(y=y1) success=1; /到出口則成功 else if (mazexy+1=O) MazePath(x,+y); /東鄰方格是通路,向東嘗試 if (!success)&(mazex+1y=O) MazePath(+x,y); /不成功且南鄰方格是通路,向南嘗試 if (!success)&(mazexy-1=O) MazePath(x,-y); /不成功且西鄰方格是通路,向西嘗試 if (!success)&(mazex-1y=O) MazePath(-x,y); /不成功且北鄰方格是通路,向北嘗試 if (!success) mazexy=; /死胡同置為四、算法設計題1. 給定已按升序排好序的n個元素a0:n-1，現要在這n個元素中找出一特定元素x，返回其在數組中的位置，如果未找到返回-1。寫出二分搜索的算法，并分析其時間復雜度。template int BinarySearch(Type a, const Type& x, int n)/在a0:n中搜索x，找到x時返回其在數組中的位置，否則返回-1 Int left=0; int right=n-1; While (leftamiddle) left=middle+1; else right=middle-1; Return -1; 時間復雜性為O(logn)2. 利用分治算法寫出合并排序的算法，并分析其時間復雜度 void MergeSort(Type a, int left, int right) if (leftright) /至少有2個元素 int i=(left+right)/2; /取中點 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到數組b copy(a, b, left, right); /復制回數組a 算法在最壞情況下的時間復雜度為O(nlogn)。3.N皇后回溯法bool Queen:Place(int k) /檢查xk位置是否合法 for (int j=1;jn) sum+; else for (int i=1;i n) / 到達葉結點 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 檢查頂點 i 與當前團的連接 int OK = 1; for (int j = 1; j bestn) / 進入右子樹 xi = 0; Backtrack(i+1); 5.