PAGEPAGE3共3頁(yè)系系專業(yè)班級(jí)姓名考號(hào)（密封線內(nèi)不準(zhǔn)答題）課程：算法設(shè)計(jì)與分析評(píng)卷人（簽名）：復(fù)核人（簽名）：題號(hào)一二三四五總分得分一、選擇題（每小題3分，共15分）1．算法與程序的主要區(qū)別在于算法具有（）。A．能行性B．確定性C．有限性D．輸入和輸出2．對(duì)一個(gè)有序序列，以比較為基礎(chǔ)的搜索算法的最壞情況時(shí)間復(fù)雜性的下界為（）。A．Ω(n)B．Ω(n2)C.Ω(nlogn)D．Ω(logn)3．0-1背包問(wèn)題：n=6，C=10，V(1:6)=(15，59，21，30，60，5)，W(1:6)=(1，5，2，3，6，1）。該問(wèn)題的最大價(jià)值為（）。A．119B．110C．115D．1204．矩陣連乘積問(wèn)題：M1(5×10),M2(10×4),M3(4×6)。矩陣鏈乘M1M2M3需要的最少乘法次數(shù)為（）。A．348B．328C．720D．3205．用貪心策略設(shè)計(jì)算法的關(guān)鍵是（）。A．將問(wèn)題分解為多個(gè)子問(wèn)題來(lái)分別處理B．選好貪心策略C．獲取各階段間的遞推關(guān)系式D．滿足最優(yōu)性原理二、填空題（每小題4分，共20分）1．某算法的計(jì)算時(shí)間T(n)滿足遞歸關(guān)系式：T(n)=2T(n-1)+O(1)，n>1；T(1)=1。則T(n)=。2．用方法對(duì)狀態(tài)空間樹(shù)進(jìn)行搜索時(shí)，每個(gè)結(jié)點(diǎn)有可能多次成為擴(kuò)展結(jié)點(diǎn)。3．子集和數(shù)問(wèn)題一般陳述如下：已知n+1個(gè)正數(shù)：wi(1≤i≤n)和M，要求找出wi的和數(shù)是M的所有子集。其解可以表示為n-元組(x1,x2,?,xn)，這里xi∈{0,1}，1≤i≤n。如果沒(méi)有選擇wi，則相應(yīng)的xi=0；如果選擇了wi，則xi=1。此解空間的空間樹(shù)有個(gè)葉結(jié)點(diǎn)，共有個(gè)結(jié)點(diǎn)。4．已知將兩個(gè)分別包含n個(gè)和m個(gè)記錄的已分類文件歸并在一起得到一個(gè)分類文件需作n+m次記錄移動(dòng)。現(xiàn)有五個(gè)已分類文件F1,F2,F3,F4,F5，它們的記錄個(gè)數(shù)分別為25,40,15,10,40，將這五個(gè)文件歸并成一個(gè)分類文件最少需要做次記錄移動(dòng)。注：每一歸并步只能歸并兩個(gè)文件。5．兩個(gè)序列A=“xyxxzxyzxy”和B=“zxzyyzxxyxxz”的最長(zhǎng)的公共子序列的長(zhǎng)度為_(kāi)_______。其中一個(gè)最長(zhǎng)公共子序列為。三、問(wèn)答題（每小題5分，共20分）1.快速排序算法是根據(jù)分治策略來(lái)設(shè)計(jì)的，簡(jiǎn)述其基本思想。2．簡(jiǎn)述蒙特卡羅算法的特點(diǎn)及提高蒙特卡羅算法得到的為正確的概率的措施？3．簡(jiǎn)述回溯法的基本思想。4．簡(jiǎn)述最小生成樹(shù)的Kruskal算法的基本思想。四、求解題1．（5分）設(shè)f(N)、g(N)是定義在正數(shù)集上的正函數(shù)。如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)≤Cg(N)，則成函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N))。證明：O(f(N))+O(g(N))=O(max{f(N)，g(N)})。2．（8分）用動(dòng)態(tài)規(guī)劃解決0-1背包問(wèn)題的改進(jìn)算法求解如下實(shí)例：n=4，c=12，v=（18，15，8，12），w=（10，2，3，4）。（要求：先寫出計(jì)算公式，再寫具體的求解過(guò)程，指出最優(yōu)值和最優(yōu)解）3.（10分）用單純性算法求解下面線性規(guī)劃問(wèn)題：maxz=-x2+3x3-2x4s.t.x1+3x2-x3+2x4=7-4x2+3x3+8x4≤102x2-4x3≥-12xi≥0（i=1,2,3,4）要求：（1）步驟描述（2）寫清每一迭代步的選擇，單純形表，可行解及可行解對(duì)應(yīng)的目標(biāo)函數(shù)的值。4.（10分）單源最短路徑問(wèn)題：在下圖實(shí)例上指定源點(diǎn)為1，目標(biāo)點(diǎn)為6，應(yīng)用優(yōu)先隊(duì)列式分支限界法找出1到6的最短路徑。（要求寫明優(yōu)先級(jí)，畫出搜索