算法設計與分析復習試題及答案

1、11.一個算法就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運算，此外，算法還應具有以下五個重要特性:_____________________________________________。2.算法的復雜性有_____________和___________之分，衡量一個算法好壞的標準是______________________。3.某一問題可用動態(tài)規(guī)劃算法求解的顯著特征是__________________

2、__________________。4.若序列X=BCADBCD，Y=ACBABDCD，請給出序列X和Y的一個最長公共子序列_____________________________。5.用回溯法解問題時，應明確定義問題的解空間，問題的解空間至少應包含___________。6.動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干____________，先求解___________，然后從這些____________的解得到原問題的解。7

3、.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為_____________。8.01背包問題的回溯算法所需的計算時間為_____________用動態(tài)規(guī)劃算法所需的計算時間為____________。9.動態(tài)規(guī)劃算法的兩個基本要素是___________和___________。10.二分搜索算法是利用_______________實現(xiàn)的算法。二、綜合題二、綜合題（50分）1.寫出設計動態(tài)規(guī)劃算法的主要步驟。2.流水作業(yè)調度問題的johnson

4、算法的思想。32.最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法（設函數(shù)名binarysearchtree)）答案：答案：一、填空一、填空1確定性有窮性可行性0個或多個輸入一個或多個輸出2.時間復雜性空間復雜性時間復雜度高低3.該問題具有最優(yōu)子結構性質4.BABCD或CABCD或CADCD｝5.一個（最優(yōu)）解6.子問題子問題子問題7.回溯法8.o(n2n)o(minnc2n)9.最優(yōu)子結構重疊子問題10.動態(tài)規(guī)劃法二、綜合題二、綜合題1.①問題具有最