【正文】 型，其中同時使用約束條件和目標(biāo)函數(shù)的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。 劃分的對稱性 。 float c=M。}templateclass Typevoid QuickSort (Type a[], int p, int r){ if (pr) {int q=Partition(a,p,r)。 //東鄰方格是通路,向東嘗試 if ((!success)amp。39。 //復(fù)制回數(shù)組a } }算法在最壞情況下的時間復(fù)雜度為O(nlogn)。 for (int j = 1。編寫對順序表L進行快速排序的算法。L,int low,int high){//[low..high]作快速排序 int pivotloc。 [high]=[low]。 Backtrack(i+1)。 j++) bestx[j] = x[j]。 //取中點 mergeSort(a, left, i)。(maze[x1][y]==39。(y==y1)) success=1。i=n。 Sort(n,v,w)。 隊列式（FIFO） 分支限界法和 優(yōu)先隊列式 分支限界法。問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 }}void backtrack (int t){ if (tn) output(x)。void backtrack (int t){ if (tn) output(x)。 hanoi(n1, C, B, A)。BA、分支界限算法 B、動態(tài)規(guī)劃算法 C、貪心算法 D、回溯算法21. 分支限界法解旅行售貨員問題時，活結(jié)點表的組織形式是（ A ）。A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法15．實現(xiàn)棋盤覆蓋算法利用的算法是（A、廣度優(yōu)先 B、最小耗費優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先10．下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（ B、動態(tài)規(guī)劃法A、找出最優(yōu)解的性質(zhì)（ B ）A、分治法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法12．哈夫曼編碼的貪心算法所需的計算時間為（CA 單源最短路徑問題 B N皇后問題 C 最小生成樹問題 D 背包問題2下列算法中不能解決0/1背包問題的是（ A ）A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法2回溯法搜索狀態(tài)空間樹是按照（ C ）的順序。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法3背包問題的貪心算法所需的計算時間為（ B ）A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）33．實現(xiàn)大整數(shù)的乘法是利用的算法（A、先進先出 B、后進先出 C、結(jié)點的優(yōu)先級 D、隨機（ move(n,a,b)。 swap(x[t], x[i])。 }} D.51. 常見的兩種分支限界法為（D）A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊列式（FIFO）分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法；二、填空題 時間 復(fù)雜性和 空間 復(fù)雜性之分。1 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到 。 for (i=1。 QuickSort (a,p,q1)。amp。 //死胡同置為}四、算法設(shè)計題1. 給定已按升序排好序的n個元素a[0:n1]，現(xiàn)要在這n個元素中找出一特定元素x，返回其在數(shù)組中的位置，如果未找到返回1。bool Queen::Place(int k){ //檢查x[k]位置是否合法 for (int j=1。 j i。int Partition(SqList amp。 if (lowhigh) //長度1 {pivotloc=Partition(L,low,high)。[low].key=pivotkey) ++low。 } if (+nibe