北師大 2019 算法分析與設(shè)計(jì)作業(yè)（三） 參考答案

1、1《算法分析與設(shè)計(jì)》作業(yè)（三） 《算法分析與設(shè)計(jì)》作業(yè)（三）本課程作業(yè)由兩部分組成。第一部分為“客觀題部分” 本課程作業(yè)由兩部分組成。第一部分為“客觀題部分” ，由 ，由 15 個(gè)選擇題組成，每題 個(gè)選擇題組成，每題 1 分，共 分，共 15 分。 分。第二部分為“主觀題部分” 第二部分為“主觀題部分” ，由簡答題和論述題組成，共 ，由簡答題和論述題組成，共 15 分。作業(yè)總分 分。作業(yè)總分 30 分，將作為平時(shí)成績記入課 分，將作為平

2、時(shí)成績記入課程總成績。 程總成績?？陀^題部分： 客觀題部分：一、 一、選擇題（每題 選擇題（每題 1 分，共 分，共 15 15 題） 題）1、貪心算法解各個(gè)子問題的方法是： 、貪心算法解各個(gè)子問題的方法是： （ B ） A、自底向上 、自底向上 B、自頂向下 、自頂向下 C、隨機(jī)選擇 、隨機(jī)選擇 D、自底向上或自頂向下 、自底向上或自頂向下2、用回溯法解旅行售貨

3、員問題時(shí)生成的樹是： 、用回溯法解旅行售貨員問題時(shí)生成的樹是： （ B ）A、子集樹 、子集樹 B、排列樹 、排列樹 C、二叉樹 、二叉樹 D、多叉樹 、多叉樹3、在 、在 n 后問題中任意兩個(gè)皇后能放在： 后問題中任意兩個(gè)皇后能放在： （ D ）A、同一行 、同一行

4、 B、同一列 、同一列 C、同一斜線 、同一斜線 D、以上都不行 、以上都不行4、用回溯法解 、用回溯法解 0-1 背包問題時(shí)生成的解空間樹是： 背包問題時(shí)生成的解空間樹是： （ A ）A、子集樹 、子集樹 B、排列樹 、排列樹 C、二叉樹 、二叉樹 D、多叉樹 、多叉樹5、用貪心算法解單源最短路徑問題時(shí)采用的算法是： 、用貪心算法解單源最短路徑

5、問題時(shí)采用的算法是： （ A ）A、Dijkstra 算法 算法 B、Prime 算法 算法 C、Kruskal 算法 算法 D、蒙特卡羅算法 、蒙特卡羅算法6、在用動(dòng)態(tài)規(guī)劃解流水作業(yè)調(diào)度時(shí)的最優(yōu)調(diào)度法則是： 、在用動(dòng)態(tài)規(guī)劃解流水作業(yè)調(diào)度時(shí)的最優(yōu)調(diào)度法則是： （ C ）A、最優(yōu)子結(jié)構(gòu) 、最優(yōu)子結(jié)構(gòu) B、重疊子問題 、重疊子問題 C、Johnson 法則 法則

6、D、最長處理時(shí)間作業(yè)優(yōu)先 、最長處理時(shí)間作業(yè)優(yōu)先7、算法與程序的區(qū)別在于： 、算法與程序的區(qū)別在于： （ D ）A、輸入 、輸入 B、輸出 、輸出 C、指令的確定性 、指令的確定性 D、指令的有限性 、指令的有限性8、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)的程序一般是： 、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)的

7、程序一般是： （ D ）A、順序 、順序 B、選擇 、選擇 C、循環(huán) 、循環(huán) D、遞歸 、遞歸9、回溯法的解空間是在搜索過程中： 、回溯法的解空間是在搜索過程中： （ A ） A、動(dòng)態(tài)產(chǎn)生 、動(dòng)態(tài)產(chǎn)生 B、靜態(tài)產(chǎn)生 、靜態(tài)產(chǎn)生 C、無解空間 、無解空間 D、動(dòng)態(tài)或者靜態(tài)產(chǎn)生 、動(dòng)態(tài)或者靜態(tài)產(chǎn)生1

8、0、在用貪心法解多機(jī)調(diào)度時(shí)的貪心選擇策略是： 、在用貪心法解多機(jī)調(diào)度時(shí)的貪心選擇策略是： （ D ）A、最優(yōu)子結(jié)構(gòu) 、最優(yōu)子結(jié)構(gòu) B、重疊子問題 、重疊子問題 C、Johnson 法則 法則 D、最長處理時(shí)間作業(yè)優(yōu)先 、最長處理時(shí)間作業(yè)優(yōu)先11、合并排序和快速排序采用的共同策略是： 、合并排序和快速排序采用的共同策略是： （ A ）A、分治法

9、、分治法 B、蒙特卡羅法 、蒙特卡羅法 C、拉斯維加斯法 、拉斯維加斯法 D、單純形法 、單純形法12、用回溯法解最大團(tuán)問題時(shí)生成的解空間樹是： 、用回溯法解最大團(tuán)問題時(shí)生成的解空間樹是： （ A ）A、子集樹 、子集樹 B、排列樹 、排列樹 C、二叉樹 、二叉樹 D、多叉樹 、多叉樹13、用分支限界法解裝載問題的解空間是： 、用分支限界法解裝

10、載問題的解空間是： （ A ）3輸入文件示例 輸入文件示例 輸出文件示例 輸出文件示例input.txt output.txt6 50 52 3 13 8 80 20 2. 編輯距離問題 編輯距離問題問題描述：設(shè) 問題描述：設(shè) A 和 B 是 2 個(gè)字符串。要用最少的字符操作將字符串 個(gè)字符串。要用最少的

11、字符操作將字符串 A 轉(zhuǎn)化為字符串 轉(zhuǎn)化為字符串 B.這里所說的字 這里所說的字符操作包括： 符操作包括：（1） 刪除一個(gè)字符； 刪除一個(gè)字符；(2)插入一個(gè)字符； 插入一個(gè)字符；(3)將一個(gè)字符改為另一個(gè)字符。 將一個(gè)字符改為另一個(gè)字符。將字符串 將字符串 A 變換為字符串 變換為字符串 B 所用的最少字符操作數(shù)稱為字符串 所用的最少字符操作數(shù)稱為字符串 A 到 B 的編輯距離，記為 的編輯距離，記為 d(A, B)。試設(shè)計(jì)一個(gè)有效算

12、法，對(duì)任給的 試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的 2 個(gè)字符串 個(gè)字符串 A 和 B，計(jì)算出它們的編輯距離 ，計(jì)算出它們的編輯距離 d(A, B)。編程任務(wù)：對(duì)于給定的字符串 編程任務(wù)：對(duì)于給定的字符串 A 和字符串 和字符串 B，編程計(jì)算其編輯距離 ，編程計(jì)算其編輯距離 d(A, B)。數(shù)據(jù)輸入：由文件 數(shù)據(jù)輸入：由文件 input.txt 提供輸入數(shù)據(jù)。文件的第 提供輸入數(shù)據(jù)。文件的第 1 行是字符串 行是字符串 A，文件的第 ，文件的第

13、 2 行是字符串 行是字符串 B。結(jié)果輸出：程序運(yùn)行結(jié)束時(shí)，將編輯距離 結(jié)果輸出：程序運(yùn)行結(jié)束時(shí)，將編輯距離 d(A, B)輸出到文件 輸出到文件 output.txt 的第 的第 1 行中。 行中。輸入文件示例 輸入文件示例 輸出文件示例 輸出文件示例input.txt output.txtfxpimu 5xwrs解: 1. 貪心策略：最短程序優(yōu)先。 貪心