算法設(shè)計與分析A7卷

第=page1*2-11頁，共=sectionpages4*28頁第=page1*22頁，共=sectionpages4*28頁南陽理工學(xué)院試卷課程：《算法設(shè)計與分析》考核方式：（閉卷）課程性質(zhì)：_專業(yè)平臺必修課_適用對象：題號一二三四五六七總分復(fù)核人滿分得分一、填空題：（每空2分，共20分）評卷人得分Prim算法求最小生成樹的過程中，貪心策略是給定n個頂點的無向連通圖，該算法的時間復(fù)雜度為。2．用分治法設(shè)計的合并排序算法描述如下，其中A[low:high]存放的待排序序列，請?zhí)顚懣杖辈糠值恼Z句。voidMergeSort(intA[]，intlow，inthigh){intmiddle;if(low<high){;MergeSort(A,low,middle);;Merge(A,low,middle,high);}}3．給定n個頂點的無向圖和m種顏色，圖的m可著色問題描述如下，其中t為當(dāng)前擴展結(jié)點所處的層次，OK函數(shù)是用來判斷是否可以著相應(yīng)顏色，請?zhí)顚懣杖辈糠值恼Z句。voidBacktrack((intt){

if(t>n)

sum++；

else

for(inti=1;i<=m;i++)

{;if(OK(t));

}}4．動態(tài)規(guī)劃的求解步驟是：最優(yōu)子結(jié)構(gòu)性質(zhì)分析、、計算最優(yōu)值，并記錄相關(guān)信息，。5．給定n個城市的交通圖，住地城市為1號城市，旅行售貨員問題的解空間樹是，該問題回溯法的時間復(fù)雜度為。二、選擇題：（每題2分，共20分）（說明：將認(rèn)為正確答案的字母填寫在每小題的括號內(nèi)）評卷人得分1．算法必須滿足的特性除了有輸入、輸出外，還有（）。A．確定性B．有限性C．無限性D．能行性2．最長公共子序列問題中，給定兩個序列的長度分別為m、n，求這兩個序列的最長公共子序需要耗時（）。A．O(m2)B．O(n2)C．O(mn)D．O(mn)3．0-1背包問題：給定n=4，W=7，w=(3,5,2,1)，p=(9,10,7,4)，該問題的最大價值是（）。A．19B．20C．21D．304．分支限界法與回溯法的不同主要表現(xiàn)在（）。A．搜索目標(biāo)B．搜索方式C．搜索開始D．?dāng)U展方式5．影響算法時間復(fù)雜度的主要因素除算法本身外，以下說法正確的是（）。A．算法的時間復(fù)雜度一定與輸入序列有關(guān)B．算法的時間復(fù)雜度一定不與輸入序列有關(guān)C．算法的時間復(fù)雜度不一定與輸入序列有關(guān)D．算法的時間復(fù)雜度一般與問題的規(guī)模有關(guān)6．某算法的時間復(fù)雜度表達(dá)式為T(n)=30n4+20n3+40n2+46n+100，該算法的時間復(fù)雜度可以用下列哪個漸進(jìn)意義下的符號表示。（）A．OB．C．D．以上符號都不能用來表示7．有關(guān)Kruskal算法的描述說法正確的是（）A．Kruskal算法的時間復(fù)雜度為（eloge），其中e為無向連通圖的邊數(shù)B．對稠密圖，Kruskal算法比Prim算法有效C．對稀疏圖，Kruskal算法比Prim算法有效D．對任何無向連通圖，Kruskal算法都比Prim算法有效8．給定一個網(wǎng)絡(luò)G=（V,E），假設(shè)s為源點，其標(biāo)號為（0，+∞）。從已標(biāo)號而未檢查的點v出發(fā)，對于邊<v，w>，如果（），則可以對w進(jìn)行標(biāo)號。A．flow(v，w)cap(v，w)B．flow(v，w)>0C．flow(v，w)<cap(v，w)D．flow(v，w)09．分治法中，將規(guī)模大的問題分解為多個子問題，子問題必須滿足的條件是（）。A．一般不相互獨立B．相互獨立C．規(guī)模變小D．與原問題相同10．二分查找的時間復(fù)雜度為（）。A．O(nlogn)B．O(n)C．O(logn)D．以上都不對三、簡答題：（每題5分，共20分）評卷人得分1．簡述哈夫曼編碼算法的思想。2．簡述快速排序算法的思想。3．簡述動態(tài)規(guī)劃的基本要素。4．簡述分支限界法的思想。四、求解題：（每題10分，共30分）評卷人得分1．用動態(tài)規(guī)劃中的跳躍點算法求解如下問題：有5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為8，物品不可分割，求裝入背包的物品和獲得的最大價值。（要求：先寫出求解公式，然后寫出求解過程，最后給出最優(yōu)解和最優(yōu)值）2．用回溯法解決4皇后問