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

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

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

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

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

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

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

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

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

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