算法設(shè)計與分析d&k

1、1網(wǎng)絡(luò)學(xué)院算法試題D及答案一填空題：（第小題每題（第小題每題4分，共分，共2020分）分）1.一個算法的優(yōu)劣通常用一個算法的優(yōu)劣通常用_時間復(fù)雜度時間復(fù)雜度和空間復(fù)雜度來度量來度量.2遞歸函數(shù)的兩大基本要素是遞歸函數(shù)的兩大基本要素是__遞歸方程遞歸方程_和邊界條件邊界條件.3對n皇后問題，將問題陳述為：將皇后問題，將問題陳述為：將n個皇后放在個皇后放在nn棋盤的不同行、不同列上，使得棋盤的不同行、不同列上，使得任意兩個皇后均不能處在同一

2、對角線上。則解空間中有任意兩個皇后均不能處在同一對角線上。則解空間中有n！個元素。個元素。4.4.實例特征是指實例特征是指_決定問題規(guī)模的因素，如輸入數(shù)的大小及數(shù)據(jù)的數(shù)量等決定問題規(guī)模的因素，如輸入數(shù)的大小及數(shù)據(jù)的數(shù)量等_____._____.5在回溯法中，一個問題的解空間是指在回溯法中，一個問題的解空間是指一個大的決策可由若干小的決策組成，所有可能一個大的決策可由若干小的決策組成，所有可能的決策序列構(gòu)成該問題的解空間的決策序列構(gòu)成該問

3、題的解空間.二簡答題：（第（第1，2，4小題每題小題每題8分，第分，第3小題小題4分，共分，共2828分）分）1備忘錄的遞歸方法的基本思想是什么？在使用動態(tài)規(guī)劃算法求解問題時，采用備忘錄的備忘錄的遞歸方法的基本思想是什么？在使用動態(tài)規(guī)劃算法求解問題時，采用備忘錄的遞歸較一般遞歸方法有何好處？遞歸較一般遞歸方法有何好處？答：備忘錄的遞歸方法的框架和一般的遞歸方法的框架相同，所不同的是每次將不同子問答：備忘錄的遞歸方法的框架和一般的遞歸方法

4、的框架相同，所不同的是每次將不同子問題的答案保存在一張表中，在以后需要時只要花很少的時間查詢即可，因而在采用備忘錄題的答案保存在一張表中，在以后需要時只要花很少的時間查詢即可，因而在采用備忘錄的遞歸方法時，進入函數(shù)，首先查詢?nèi)羲蟮淖訂栴}是否已有答案，若有只要取回即的遞歸方法時，進入函數(shù)，首先查詢?nèi)羲蟮淖訂栴}是否已有答案，若有只要取回即可，否則遞歸調(diào)用求解新的子問題。在使用動態(tài)規(guī)劃算法求解問題時，采用備忘錄的遞歸可，否則遞歸調(diào)用求

5、解新的子問題。在使用動態(tài)規(guī)劃算法求解問題時，采用備忘錄的遞歸可避免子問題的重復(fù)計算，從而可大大提高算法的效率?？杀苊庾訂栴}的重復(fù)計算，從而可大大提高算法的效率。2簡述一個程序運行所需要的空間由哪幾部分構(gòu)成？各部分存儲的對象分別包括哪些？簡述一個程序運行所需要的空間由哪幾部分構(gòu)成？各部分存儲的對象分別包括哪些？答：一個程序運行所需要的空間由三部分構(gòu)成，分別為指令空間、數(shù)據(jù)空間和環(huán)境?？沾穑阂粋€程序運行所需要的空間由三部分構(gòu)成，分別為指令空

6、間、數(shù)據(jù)空間和環(huán)境?？臻g。間。指令空間指令空間用來存儲經(jīng)過編譯之后的程序指令；數(shù)據(jù)空間用來存儲所有常量和變量的值；用來存儲經(jīng)過編譯之后的程序指令；數(shù)據(jù)空間用來存儲所有常量和變量的值；環(huán)境?？臻g保存函數(shù)調(diào)用返回時恢復(fù)運行所需要的信息。當(dāng)一個函數(shù)被調(diào)用時，下面數(shù)據(jù)環(huán)境?？臻g保存函數(shù)調(diào)用返回時恢復(fù)運行所需要的信息。當(dāng)一個函數(shù)被調(diào)用時，下面數(shù)據(jù)將被保存在環(huán)境棧中：將被保存在環(huán)境棧中：1）返回地址；）返回地址；2）所有局部變量的值、遞歸函數(shù)的傳值

7、形式參數(shù)的）所有局部變量的值、遞歸函數(shù)的傳值形式參數(shù)的值；值；3）所有引用參數(shù)以及常量引用參數(shù)的定義。）所有引用參數(shù)以及常量引用參數(shù)的定義。3算法設(shè)計通常有哪些方法？算法設(shè)計通常有哪些方法？(至少列出至少列出4種)答：算法設(shè)計方法有分治算法，貪心算法，動態(tài)規(guī)劃算法，歸納算法，回溯算法，分支答：算法設(shè)計方法有分治算法，貪心算法，動態(tài)規(guī)劃算法，歸納算法，回溯算法，分支限界算法等。限界算法等。4動態(tài)規(guī)劃算法的基本思想是什么？動態(tài)規(guī)劃算法的基本

8、思想是什么？它和分治法有什么區(qū)別和聯(lián)系？它和分治法有什么區(qū)別和聯(lián)系？答：動態(tài)規(guī)劃算法的基本思想為：該方法的思路也是將待求解的大問題分成規(guī)模較小的答：動態(tài)規(guī)劃算法的基本思想為：該方法的思路也是將待求解的大問題分成規(guī)模較小的子問題，但所得的各子問題之間有重復(fù)子問題，為了避免子問題的重復(fù)計算，可依自底向子問題，但所得的各子問題之間有重復(fù)子問題，為了避免子問題的重復(fù)計算，可依自底向上的方式計算最優(yōu)值，并根據(jù)子問題的最優(yōu)值合并得到更大問題的最優(yōu)值

9、，進而可構(gòu)造出上的方式計算最優(yōu)值，并根據(jù)子問題的最優(yōu)值合并得到更大問題的最優(yōu)值，進而可構(gòu)造出所求問題的最優(yōu)解。所求問題的最優(yōu)解。三分析解答題：（第1212小題每題每題1111分第3434小題每題小題每題1515分，共分，共5252分）1判斷下面的算法是否正確，如果算法不正確，請說明產(chǎn)生錯誤的原因，如果算法正判斷下面的算法是否正確，如果算法不正確，請說明產(chǎn)生錯誤的原因，如果算法正確，請給出算法的正確性證明。確，請給出算法的正確性證明。Te