算法設(shè)計(jì)與分析考試題及答案

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

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

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

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