《高級算法設(shè)計與分析》試卷1

PAGEPAGE4《高級算法設(shè)計與分析》期末試卷（試卷1）姓名：___________________學(xué)號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學(xué)號一、選擇題（每題3分，共45分）目前比較排序所能夠達到的最優(yōu)計算復(fù)雜度為：A：Θ(n)B:Θ(nlogn)C:Θ(n2)D:Θ(n2logn)哪兩個算法需要最優(yōu)子結(jié)構(gòu)性質(zhì)A:分治和動態(tài)規(guī)劃B:分治和貪心C:動態(tài)規(guī)劃和貪心D:動態(tài)規(guī)劃和回溯線性規(guī)劃的標(biāo)準(zhǔn)形式是：B.C.D.下列標(biāo)準(zhǔn)型化轉(zhuǎn)化為松弛型:B.C.D.對于隨機快速排序,以下描述錯誤的是:A.隨機快速排序消除或減少了一般快速排序的最壞時間復(fù)雜度B.隨機快速排序?qū)儆谏嵛榈滤惴–.隨機快速排序的時間復(fù)雜度一定比一般快速排序的時間復(fù)雜度好D.隨機快速排序的期望時間復(fù)雜度為O(nlogn)對于拉斯維加斯和蒙特卡洛算法描述錯誤的是:A.拉斯維加斯算法不一定獲得解,但如果獲得解一定是正確的B.蒙特卡洛算法可能給出錯誤解C.拉斯維加斯算法找到解得概率與算法執(zhí)行時間成正比D.隨機選擇屬于蒙特卡洛算法以下對規(guī)約的描述錯誤的是：，如果B是P問題，則A一定也是P問題，如果A是NPC問題，則B一定也是NPC問題，如果B是NP問題，則A一定也是NP問題L1代表A的算法,L2代表B的算法,則L1(x)=L2(f(x)),其中f為規(guī)約函數(shù)對NPC問題,以下說法正確的是：A.這個問題是一定是NP問題B.這個問題一定不是NP問題C.已經(jīng)證明這個問題一定是P問題D.已經(jīng)證明這個問題一定不是P問題以下問題不是NPC問題的是：A.歐拉回路問題B.最大團問題C.3合取范式D.0-1背包問題在團問題(圖G)規(guī)約為頂點覆蓋問題(圖)中,以下說法錯誤的是：設(shè)（u,v）為的任意邊，則（u，v）其中至少一個點不屬于G的團設(shè)（u,v）為的任意邊，則（u，v）其中至少一個點屬于的頂點覆蓋如果有兩個頂點u,v都不屬于的頂點覆蓋，則這兩個頂點一定屬于G的團圖G中有規(guī)模為k的團，當(dāng)且僅當(dāng)圖有規(guī)模為k的頂點覆蓋在旅行商問題的NP難證明過程中,以下說法錯誤的是：通常通過哈密頓回路來規(guī)約旅行商問題在規(guī)約的過程中,目的是找一條成本為n(n為邊數(shù))的旅行線路在規(guī)約的過程中,需要將原圖擴展成一個完全圖擴展成完全圖后,原來的邊設(shè)成本為0,擴展的邊設(shè)成本為1下面對子集和的近似算法描述錯誤的是：如已知集合{x1,x2,x3,…,xi}所有的子集和Pi，則{x1,x2,x3,…,xi,xi+1}所有的子集和為。在計算過程中，為了減少子集和的規(guī)模，算法通過去除大于目標(biāo)值的子集和，以及刪除相似子集和的方法實現(xiàn)如果算法過程中，不刪除相似的子集和（僅僅去除大于目標(biāo)值的子集和），是可以得到精確的結(jié)果的子集和的近似算法只是一個多項式時間近似算法，而不是一個完全多項式時間的近似算法下面對在線算法和離線算法比較，以下描述錯誤的是：即使數(shù)據(jù)在計算時都已知，也可以采用在線算法來達到更好的結(jié)果在線算法通常是近似算法通常通過和離線最優(yōu)算法的比較來判斷在線算法的好壞，如果在線算法的代價Con和離線算法的代價Coff有關(guān)系，則稱在線算法在實例IA上為α競爭度算法最小生成樹在線算法可通過貪心算法實現(xiàn)下面對最小生成樹在線算法描述錯誤的是：最小生成樹在線算法是一種貪心算法算法復(fù)雜度為O（n2）算法競爭度為O（n）生成樹在線算法生成樹中第k長的邊長度小于等于2l/k，其中l(wèi)為最小生成樹的代價下面對模擬退火描述錯誤的是：Greedy算法，但是加入隨機因素若目標(biāo)函數(shù)在第i+1步移動后比第i步更優(yōu)，則總是被接受以一定的概率來接受一個比當(dāng)前解要差的解，用于跳出局部最優(yōu)解這個概率隨著溫度的降低，變的更大，以便更快的跳出局部最優(yōu)解二、計算、建模題（共40分）已知線性規(guī)劃問題,其對偶問題的最優(yōu)解為*=(y1,y2,y3,y4)=(0,0,4,4)，試用對偶的互補松弛性求原問題的最優(yōu)解（10分）min8x1+12x2s.t.2x1+2x2≥22x2≥1x1+x2≥5x1+2x2≥6x1,x2≥0某市下設(shè)八個區(qū),下表給出救護車從一個區(qū)到另外一個區(qū)的車程時間(min)。該市擬建救護中心，要求各區(qū)離救護中心的車程時間必須在8min之內(nèi)（包括8min），問至少建多少個救護中心，建于何處（只需要建立模型，無需計算）？（10分）參考3合取范式歸約團問題的過程，證明最大獨立集問題是NPC問題。最大獨立集是給一無向圖，找出一個點集，使得任意兩點之間都沒有連邊，這個點集就是獨立集。而點最多的獨立集，就是最大獨立集。(10分)4）簡單描述如何用遺傳算法實現(xiàn)旅行商問題的求解，描述要包含個體（染色體）設(shè)置，適應(yīng)度函數(shù)定義，選擇算子，交叉和變異操作（10分）三、算法設(shè)計題（共15分）裝箱問題:設(shè)有n個物品,其大小為a1,a2,a3,…,an(0<ai<=1),現(xiàn)需要將這n個物品裝入大小為1的箱子,求裝完物品最少的箱子個數(shù)。此問題為NPC問題，請用近似算法求解(給出此算法的思路,并用算法來實現(xiàn)如下具體例子)，還需要計