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