PAGE1《算法設計與分析》試卷1一、多項選擇題（每空2分，共20分）：1、以下關于算法設計問題的敘述中正確的是__________。A、計算機與數值問題的求解——方程式求根、插值問題、數值積分、函數逼近等有關B、利用計算機無法解決非數值問題C、計算機在解決分類、語言翻譯、圖形識別、解決高等代數和組合分析等方面的數學問題、定理證明、公式推導乃至日常生活中各種過程的模擬等問題中，主要進行的是判斷、比較，而不是算術運算D、算法設計與分析主要研究對象是非數值問題，當然也包含某些數值問題2、算法的特征包括_________。A、有窮性 B、確定性C、輸入和輸出 D、能行性或可行性3、以下描述是有關算法設計的基本步驟：①問題的陳述 ②算法分析 ③模型的擬制 ④算法的實現⑤算法的詳細設計 ⑥文檔的編制，應與其它環節交織在一起其中正確的順序是__________。A、①②③④⑤⑥ B、①③⑤②④⑥C、②④①③⑤⑥ D、⑥①③⑤②④4、以下說法正確的是__________。A、數學歸納法可以證明算法終止性B、良序原則是證明算法的正確性的有力工具C、x=小于或等于x的最大整數（x的低限）D、x=小于或等于x的最大整數（x的高限）5、漢諾塔（Hanoi）問題中令h（n）為從A移動n個金片到C上所用的次數，則遞歸方程為__________，其初始條件為__________，將n個金片從A柱移到C柱上的移動次數是__________；設菲波那契（Fibonacci）數列中Fn為第n個月時兔子的對數，則有遞歸方程為__________，其中F1=F2=__________。A、Fn=Fn-1+Fn-2 B、h（n）=2h（n-1）+1C、1 D、h（1）=1E、h（n）=2n-1 F、06、在一個有向連通圖中（如下圖所示），找出點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、快速排序法的基本思想是重新排列關鍵字，把一個文件分成兩個文件，使得第一個文件中所有元素均小于第二個文件中的元素；然后再對兩個子文件進行同樣的處理。其算法如下：算法（快速排序是一種遞歸算法）：Qsort(L,k,m)//L待排序序列，k、m是分類文件之首、末關鍵字(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、有設備更新問題如下所示，五年內收益最大的設備更新策略的最大收益為__________。3、已知作業隊列及其所需要運行的時間為t1=2，t2=5，t3=8，t4=1，t5=5，t6=1），在三臺處理器上運行，按貪心法調度總運行時間為__________，最佳運行時間為__________。4、吉普車總裝油量為500L，耗油量為1L/里，要自行設置燃料庫穿越1000里的沙漠，使用倒推法首先應共設置__________個站點，第一個距離起點__________里，存放__________L油，總耗油量達到最少，即_________L。三、應用及問答題：1、用氣泡法元素序列（3，1，4，1，5，9，6，5，3，5，8，9，7）分類，并分析比較次數。2、把輸入元素3，20，5，9，2，30，25，18，16，19，3構造成堆，并用歸并分類法進行分類。3、求生成樹和最小耗費生成樹：4、求s到t的最短路5、給定模式P為babaabbb，計算P的Next、Next[a[i]]函數值

《算法設計與分析》試卷1答案一、多項選擇題（每空2分，共20分）：1、ABC2、ABCD3、B4、D5、B、D、E、A、C6、B二、填空（每空2分，共20分）：1、i<j(L(j)>x)and(