算法分析與設(shè)計(jì)作業(yè)（三）

本文格式為Word版，下載可任意編輯——算法分析與設(shè)計(jì)作業(yè)（三）《算法分析與設(shè)計(jì)》作業(yè)（三）

本課程作業(yè)由兩部分組成。第一部分為“客觀題部分〞，由15個(gè)選擇題組成，每題1分，共15分。其次部分為“主觀題部分〞，由簡答題和論述題組成，共15分。作業(yè)總分30分，將作為平日成績記入課程總成績。

客觀題部分：

一、選擇題（每題1分，共15題）

1、貪心算法解各個(gè)子問題的方法是：（）A、自底向上B、自頂向下C、隨機(jī)選擇D、自底向上或自頂向下2、用回溯法解旅行售貨員問題時(shí)生成的樹是：（）A、子集樹B、排列樹C、二叉樹D、多叉樹3、在n后問題中任意兩個(gè)皇后能放在：（）A、同一行B、同一列C、同一斜線D、以上都不行4、用回溯法解0-1背包問題時(shí)生成的解空間樹是：（）A、子集樹B、排列樹C、二叉樹D、多叉樹

5、用貪心算法解單源最短路徑問題時(shí)采用的算法是：（）

A、Dijkstra算法B、Prime算法C、Kruskal算法D、蒙特卡羅算法6、在用動(dòng)態(tài)規(guī)劃解流水作業(yè)調(diào)度時(shí)的最優(yōu)調(diào)度法則是：（）A、最優(yōu)子結(jié)構(gòu)B、重疊子問題C、Johnson法則D、最優(yōu)點(diǎn)理時(shí)間作業(yè)優(yōu)先7、算法與程序的區(qū)別在于：（）A、輸入B、輸出C、指令的確定性D、指令的有限性8、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)的程序一般是：（）

A、順序B、選擇C、循環(huán)D、遞歸

9、回溯法的解空間是在探尋過程中：（）A、動(dòng)態(tài)產(chǎn)生B、靜態(tài)產(chǎn)生C、無解空間D、動(dòng)態(tài)或者靜態(tài)產(chǎn)生10、在用貪心法解多機(jī)調(diào)度時(shí)的貪心選擇策略是：（）A、最優(yōu)子結(jié)構(gòu)B、重疊子問題C、Johnson法則D、最優(yōu)點(diǎn)理時(shí)間作業(yè)優(yōu)先11、合并排序和快速排序采用的共同策略是：（）A、分治法B、蒙特卡羅法C、拉斯維加斯法D、單純形法12、用回溯法解最大團(tuán)問題時(shí)生成的解空間樹是：（）

A、子集樹B、排列樹C、二叉樹D、多叉樹

13、用分支限界法解裝載問題的解空間是：（）

A、子集樹B、排列樹C、單向鏈表D、多向鏈表

14、計(jì)算定積分的算法：（）A、隨機(jī)投點(diǎn)法B、舍伍德法C、分治法D、回溯法15、用隨機(jī)化算法解同一實(shí)例兩次得到：（）

A、結(jié)果和時(shí)間都一致B、結(jié)果一致時(shí)間不一致C、結(jié)果和時(shí)間都不一致D、以上都不對

主觀題部分：

二、改錯(cuò)題（每題2.5分，共2題）

下面有兩個(gè)二分探尋算法，請判斷它們的正確性。假使算法不正確，請說明產(chǎn)生錯(cuò)誤的原因；假使算法正確，請給出算法的正確性證明。1publicstaticintbinarySearch(int[]a,intx,intn){

intleft=0;intright=n-1;while(lefta[middle])left=middle;elseright=middle;}

return-1;}

2publicstaticintbina