算法設計與分析試卷

算法設計與分析試卷(A卷)選擇題（選擇1-4個正確的答案,每題2分，共20分）（1）計算機算法的正確描述是：A．一個算法是求特定問題的運算序列。B．算法是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列。C．算法是一個對任一有效輸入能夠停機的圖靈機。D．一個算法，它是滿足5個特性的程序，這5個特性是：有限性、確定性、能行性、有0個或多個輸入且有1個或多個輸出。（2）影響程序執(zhí)行時間的因素有哪些？A．算法設計的策略B．問題的規(guī)模C．編譯程序產(chǎn)生的機器代碼質(zhì)量D．計算機執(zhí)行指令的速度（3）用數(shù)量級形式表示的算法執(zhí)行時間稱為算法的A．時間復雜度B．空間復雜度C．處理器復雜度D．通信復雜度（4）時間復雜性為多項式界的算法有：A．快速排序算法B．n-后問題C．計算值D．prim算法（6）衡量近似算法性能的重要標準有：A．算法復雜度B．問題復雜度C．解的最優(yōu)近似度D．算法的策略（7）分治法的適用條件是，所解決的問題一般具有這些特征：A．該問題的規(guī)?？s小到一定的程度就可以容易地解決；B．該問題可以分解為若干個規(guī)模較小的相同問題；C．利用該問題分解出的子問題的解可以合并為該問題的解D．該問題所分解出的各個子問題是相互獨立的。（8）具有最優(yōu)子結(jié)構(gòu)的算法有：A．概率算法B．回溯法C．分支限界法D．動態(tài)規(guī)劃法（10）適于遞歸實現(xiàn)的算法有：A．并行算法B．近似算法C．分治法D．回溯法三、簡答題（每小題5分，共10分）（13）算法的復雜度分析涉及哪些方面？（14）動態(tài)規(guī)劃法的指導思想是什么？四、計算題（每小題8分，共24分）（15）用動態(tài)規(guī)劃法求A10*30B30*20C20*10D10*200運算量最小的乘積順序。要求寫出求解過程，并將結(jié)果填入數(shù)組(16)用貪心法求下圖的最小生成樹圖16（17）馬步問題：在n*n的方棋盤中，馬只能走“日”字。馬從初始位置（x0,y0）出發(fā)，把棋盤的每一格都走一次，且只走一次（遍歷）。求出n=5時馬的行走路線。五、分析設計題（每小題8分，共16分）（18）有16個選手參加循環(huán)賽，循環(huán)賽一共進行15天，每個選手必須與其他的15個選手各賽一場，每個選手一天只比賽一次；設計一個滿足上述要求的比賽日程表。（19）某市場營銷人員從他所在城市(頂點1)出發(fā)，到其他5個城市去做市場調(diào)查，如下圖19所示。請設計行走路線。圖19西南科技大學試題單（H）計算機學院:課程名稱:《算法分析與設計》課程代碼:西南科技大學試題單（H）計算機學院:課程名稱:《算法分析與設計》課程代碼:14314025命題單位:軟件教研室學院：________專業(yè)班級：_______學號：□□□□□□□□命題共2頁第1頁一、不定項選擇題（每空3分，共60分）：1、以下關(guān)于算法設計問題的敘述中正確的是__________。A、計算機與數(shù)值問題的求解——方程式求根、插值問題、數(shù)值積分、函數(shù)逼近等有關(guān)B、利用計算機無法解決非數(shù)值問題C、計算機在解決分類、語言翻譯、圖形識別、解決高等代數(shù)和組合分析等方面的數(shù)學問題、定理證明、公式推導乃至日常生活中各種過程的模擬等問題中，主要進行的是判斷、比較，而不是算術(shù)運算D、算法設計與分析主要研究對象是非數(shù)值問題，當然也包含某些數(shù)值問題2、算法的特征包括__________。A、有窮性 B、確定性C、輸入和輸出 D、能行性或可行性6、在一個有向連通圖中（如下圖所示），找出點A到點B的一條最短路為__________。A、最短路：1→3→5→8→10，耗費：20B、最短路：1→4→6→9→10，耗費：16C、最短路：1→4→6→9，耗費：12D、最短路：4→6→9→10，耗費：13二、填空（每空2分，共20分）：1、快速排序法的基本思想是重新排列關(guān)鍵字，把一個文件分成兩個文件，使得第一個文件中所有元素均小于第二個文件中的元素；然后再對兩個子文件進行同樣的處理。其算法如下：算法（快速排序是一種遞歸算法）：Qsort(L,k,m)//L待排序序列，k、m是分類文件之首、末關(guān)鍵字(1,n)Beginifk<mthenbeginSplit(L,k,m,i)//將L分組Qsort(L,k,i-1)Qsort(L,i+1,m)endendSplit(L,k,m,i)//將序列L進行分組Begini=k,j=m,x=L(k)while__________dobeginwhile__________doj=j-1ifj<>ithenL(i)=L(j),i=i+1while(L(i)<x)and(i<>j)doi=i+1ifi<>jthenL(j)=L(i),j=j-1end__________End2、有設備更新問題如下所示，五年內(nèi)收益最大的設備更新策略的最大收益為__________。3、已知作業(yè)隊列及其所需要運行的時間為t1=2，t2=5，t3=8，t4=1，t5=5，t6=1），在三臺處理器上運行，按貪心法調(diào)度總運行時間為__________，最佳運行時間為__________。吉普車總裝油量為500L，耗油量為1L/里，要自行設置燃料庫穿越1000里的沙漠，使用倒推法首先應共設置__________個站點，第一個距離起點__________里，存放__________L油，總耗油量達到最少，即__________L。三、解答題（要求給出解答步驟，尤其強調(diào)所用方法；共50分）：1．給定M=45，(P1,P2,P3,P4,P5,P6)=(11,8,15,18,12,6),(W1,W2,W3,W4,W5,W6)=(5,3,2,10,4,2)利用貪心法找出背包問題的最佳解，再用分枝限界法并進行比較。（20分）2．用動態(tài)規(guī)劃算法求以下網(wǎng)絡的最短、最長路徑。（15分）3．算法設計：旅行售貨員問題（即TSP問題）。（15分）要求：1）說明所使用的算法策略；2）寫出算法實現(xiàn)的主要步驟；3）分析算法的時間、空間復雜性。一、填空題(選做5道，10分)四后問題的搜索空間為（）樹；0-1背包問題的搜索空間為（）樹；巡回售貨員問題的搜索空間為（）樹。（）法的求解目標是找出解空間樹中滿足約束條件的所有解，而（）法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解?；厮莘ㄒ话阋裕ǎ﹥?yōu)先的方式搜索解空間樹，而分支限界法則一般以（）優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。二、單項選擇題(10分)下列哪些問題不能用貪心法求解？（）A)霍夫曼編碼問題 B)單源最短路徑問題

C)0-1背包問題 D)最小生成樹問題在快速排序算法中引入隨機過程的主要目的是什么？（）A)改善確定性算法的平均運行時間

B)保證算法總能在O(nlgn)時間內(nèi)結(jié)束

C)避免了算法最壞情況下的發(fā)生

D)改善了確定性算法最壞情形下的平均運行時間用MonteCarlo方法估計四后問題回溯算法的效率。（）五次實驗結(jié)果分別為<1,4,2>、<2,4,1,3>、<4,2>、<3,1,4,2>、<1,3>，則解空間中的結(jié)點數(shù)估計為？A)16B)16.2流水作業(yè)調(diào)度問題中，作業(yè)不滿足Johnson不等式時，交換它們的加工順序后，加工時間（）（增加、不增加、減少、不減少、不變）。動態(tài)規(guī)劃算法通常以（）的方式解各子問題，而貪心算法通常以（）的方式進行迭代。優(yōu)化問題主要由兩個部分組成（）和（）。貪心算法的核心問題是（）。當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應的解空間樹稱為（ ），通常有（ ）個葉子結(jié)點，遍歷此空間樹需要（ ）的計算時間。按照活結(jié)點表的組織方式的不同，分支限界法包括（ ）和（ ）兩種形式。最大優(yōu)先隊列分支限界法中，優(yōu)先值較（ ）的結(jié)點優(yōu)先級較高，通常用（ ）實現(xiàn)，體現(xiàn)（ ）的原則。算法復雜性依賴于（）、（）、（）。遞歸的兩個基本要素包括（）和（）。用貪心算法求解的問題一般具有兩個重要性質(zhì)（）和（）。背包問題和0－1背包問題中，可以用貪心算法求解的問題是（）。含有n個頂點的連通圖的生成樹含有（ ）條邊。狀態(tài)空間樹的搜索方法主要包括深度優(yōu)先搜索、廣度優(yōu)先搜索和（