【MOOC】《算法設(shè)計(jì)與分析》(東北大學(xué)) 中國大學(xué)慕課答案

【MOOC】《算法設(shè)計(jì)與分析》(東北大學(xué))中國大學(xué)慕課答案

有些題目順序不一致，下載后按鍵盤ctrl+F進(jìn)行搜索第一章算法概述第一章測驗(yàn)1.單選題：按照漸近階從低到高的順序排列以下表達(dá)式：

選項(xiàng)：

A、

B、

C、

D、

答案：【】2.單選題：

選項(xiàng)：

A、

B、

C、

D、

答案：【】3.單選題：

選項(xiàng)：

A、

B、

C、

D、

答案：【】第二章遞歸與分治策略第二章測驗(yàn)1.單選題：跟蹤分治法求解棋盤覆蓋問題的過程，方格（1）內(nèi)應(yīng)填選的的骨牌編號(hào)為？

選項(xiàng)：

A、0

B、1

C、16

D、17

答案：【1】2.單選題：在用分治法求解大整數(shù)的乘法中，如果將一個(gè)大整數(shù)分成三段，則時(shí)間復(fù)雜性為

選項(xiàng)：

A、

B、

C、

D、

答案：【】3.單選題：用分治法求解棋盤覆蓋問題的時(shí)間復(fù)雜性為，空間復(fù)雜性為

選項(xiàng)：

A、

B、

C、

D、

答案：【】4.單選題：如果在合并排序算法的分割步驟中，將數(shù)組劃分為個(gè)子數(shù)組，每個(gè)子數(shù)組中有個(gè)元素，然后遞歸地對分割后的子數(shù)組進(jìn)行排序，最后將所得到的個(gè)排好序的子數(shù)組合并成所要求的排好序的數(shù)組。分析算法的計(jì)算復(fù)雜性

選項(xiàng)：

A、

B、

C、

D、

答案：【】5.單選題：

選項(xiàng)：

A、

B、

C、

D、

答案：【】6.單選題：

選項(xiàng)：

A、

B、

C、

D、

答案：【】7.單選題：跟蹤分治法求解棋盤覆蓋問題的過程，方格（4）內(nèi)應(yīng)填選的的骨牌編號(hào)為？

選項(xiàng)：

A、0

B、1

C、16

D、17

答案：【17】8.單選題：跟蹤分治法求解棋盤覆蓋問題的過程，方格（3）內(nèi)應(yīng)填選的的骨牌編號(hào)為？

選項(xiàng)：

A、0

B、1

C、16

D、17

答案：【16】9.單選題：跟蹤分治法求解棋盤覆蓋問題的過程，方格（2）內(nèi)應(yīng)填選的的骨牌編號(hào)為？

選項(xiàng)：

A、0

B、1

C、16

D、17

答案：【0】[vk-content]第三章動(dòng)態(tài)規(guī)劃第三章測驗(yàn)1.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算矩陣的連乘積所需的最少乘法次數(shù)=____次？

答案：【34400】2.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[2,5]=

答案：【24800】3.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[1,4]=

答案：【32800】4.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[3,5]=

答案：【60000】5.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[2,4]=

答案：【8800】6.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[1,3]=

答案：【5600】7.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：在該圖像壓縮問題的最優(yōu)解中，共有____個(gè)分段？（請?zhí)顚懓⒗當(dāng)?shù)字）

答案：【3】8.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：計(jì)算最優(yōu)分段所需的存儲(chǔ)位數(shù)s[i],其中：s[20]=

答案：【108】9.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：計(jì)算最優(yōu)分段所需的存儲(chǔ)位數(shù)s[i],其中：s[19]=

答案：【103】10.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：計(jì)算最優(yōu)分段所需的存儲(chǔ)位數(shù)s[i],其中：s[18]=

答案：【96】11.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：計(jì)算最優(yōu)分段所需的存儲(chǔ)位數(shù)s[i],其中：s[17]=

答案：【88】12.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：計(jì)算最優(yōu)分段所需的存儲(chǔ)位數(shù)s[i],其中：s[16]=

答案：【80】13.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[4,5]=

答案：【80000】14.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[3,4]=

答案：【20000】15.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[2,3]=

答案：【800】16.計(jì)算矩陣的連乘積時(shí)，需確定最優(yōu)的乘法次序，其中各矩陣的維數(shù)為：根據(jù)書上給出的動(dòng)態(tài)規(guī)劃算法，計(jì)算m[i,j]，其中：m[1,2]=

答案：【2400】17.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：給出最優(yōu)解中分段j的長度l[j]和像素位數(shù)b[j],其中：b[2]=

答案：【8】18.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：給出最優(yōu)解中分段j的長度l[j]和像素位數(shù)b[j],其中：l[2]=

答案：【5】19.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：給出最優(yōu)解中分段j的長度l[j]和像素位數(shù)b[j],其中：b[1]=

答案：【1】20.跟蹤書上給出的圖像壓縮動(dòng)態(tài)規(guī)劃算法，給定像素灰度值序列p[i]如下：給出最優(yōu)解中分段j的長度l[j]和像素位數(shù)b[j],其中：l[1]=

答案：【10】第四章貪心算法第四章測驗(yàn)1.給定一個(gè)有6個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，頂點(diǎn)編號(hào)為V={1,2,3,4,5,6}，其中頂點(diǎn)1是源，圖中的邊與邊上的權(quán)值由下圖數(shù)組給出，給出Dijkstra算法第2次迭代時(shí)：dist[6]=

答案：【53】2.給定一個(gè)有6個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，頂點(diǎn)編號(hào)為V={1,2,3,4,5,6}，其中頂點(diǎn)1是源，圖中的邊與邊上的權(quán)值由下圖數(shù)組給出，給出Dijkstra算法第2次迭代時(shí)：dist[5]=

答案：【13】3.給定一個(gè)有6個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，頂點(diǎn)編號(hào)為V={1,2,3,4,5,6}，其中頂點(diǎn)1是源，圖中的邊與邊上的權(quán)值由下圖數(shù)組給出，給出Dijkstra算法第2次迭代時(shí)：dist[4]=

答案：【105】4.給定一個(gè)有6個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，頂點(diǎn)編號(hào)為V={1,2,3,4,5,6}，其中頂點(diǎn)1是源，圖中的邊與邊上的權(quán)值由下圖數(shù)組給出，給出Dijkstra算法第2次迭代時(shí)：dist[3]=

答案：【65】5.給定一個(gè)有6個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，頂點(diǎn)編號(hào)為V={1,2,3,4,5,6}，其中頂點(diǎn)1是源，圖中的邊與邊上的權(quán)值由下圖數(shù)組給出，給出Dijkstra算法第2次迭代時(shí)：dist[2]=

答案：【45】第五章回溯法第五章測驗(yàn)1.0-1背包問題：給定5個(gè)物品和一個(gè)容量為70的背包，物品的重量依次為{5,18,30,40,45}，價(jià)值依次為{20,60,85,90,100}。選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。跟蹤教材給出的0-1背包問題的回溯算法，給出第二次到第六次計(jì)算限界函數(shù)Bound的值。注:Bound()的結(jié)果為向下取整后的整數(shù)。例如：本題中第一次求出的Bound值向下取整后可得Bound()=202。則：第三次，Bound()=_____

答案：【185】2.0-1背包問題：給定5個(gè)物品和一個(gè)容量為70的背包，物品的重量依次為{5,18,30,40,45}，價(jià)值依次為{20,60,85,90,100}。選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。跟蹤教材給出的0-1背包問題的回溯算法，給出第二次到第六次計(jì)算限界函數(shù)Bound的值。注:Bound()的結(jié)果為向下取整后的整數(shù)。例如：本題中第一次求出的Bound值向下取整后可得Bound()=202。則：第二次，Bound()=_____

答案：【165】3.0-1背包問題：給定5個(gè)物品和一個(gè)容量為70的背包，物品的重量依次為{5,18,30,40,45}，價(jià)值依次為{20,60,85,90,100}。選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。跟蹤教材給出的0-1背包問題的回溯算法，給出第二次到第六次計(jì)算限界函數(shù)Bound的值。注:Bound()的結(jié)果為向下取整后的整數(shù)。例如：本題中第一次求出的Bound值向下取整后可得Bound()=202。則：第六次，Bound()=_____

答案：【80】4.0-1背包問題：給定5個(gè)物品和一個(gè)容量為70的背包，物品的重量依次為{5,18,30,40,45}，價(jià)值依次為{20,60,85,90,100}。選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。跟蹤教材給出的0-1背包問題的回溯算法，給出第二次到第六次計(jì)算限界函數(shù)Bound的值。注:Bound()的結(jié)果為向下取整后的整數(shù)。例如：本題中第一次求出的Bound值向下取整后可得Bound()=202。則：第五次，Bound()=_____

答案：【180】5.0-1背包問題：給定5個(gè)物品和一個(gè)容量為70的背包，物品的重量依次為{5,18,30,40,45}，價(jià)值依次為{20,60,85,90,100}。選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大。跟蹤教材給出的0-1背包問題的回溯算法，給出第二次到第六次計(jì)算限界函數(shù)Bound的值。注:Bound()的結(jié)果為向下取整后的整數(shù)。例如：本題中第一次求出的Bound值向下取整后可得Bound()=202。則：第四次，Bound()=_____

答案：【170】第六章分支限界法第六章測驗(yàn)1.給定4個(gè)頂點(diǎn)的帶權(quán)有向圖，鄰接矩陣如下圖所示，跟蹤教材給出的旅行售貨員問題的分支限界算法，給出前5次加入優(yōu)先隊(duì)列H的結(jié)點(diǎn)N的lcost的值。(第5次)、N.Icost=_____

答案：【35】2.給定4個(gè)頂點(diǎn)的帶權(quán)有向圖，鄰接矩陣如下圖所示，跟蹤教材給出的旅行售貨員問題的分支限界算法，給出前5次加入優(yōu)先隊(duì)列H的結(jié)點(diǎn)N的lcost的值。(第4次)、N.Icost=_____

答案：【45】3.給定4個(gè)頂點(diǎn)的帶權(quán)有向圖，鄰接矩陣如下圖所示，跟蹤教材給出的旅行售貨員問題的分支限界算法，給出前5次加入優(yōu)先隊(duì)列H的結(jié)點(diǎn)N的lcost的值。(第3次)、N.Ico