MOOC 算法設計與分析-武漢理工大學 中國大學慕課答案

MOOC算法設計與分析-武漢理工大學中國大學慕課答案“算法設計基礎”算法實現(xiàn)題“算法設計基礎”單元測驗1、問題：下列關于算法的說法中正確的有（）。選項：A、求解某一類問題的算法是唯一的B、算法必須在有限步操作之后停止C、算法的每一步操作必須是明確的，不能有歧義或含義模糊D、算法執(zhí)行后一定產生確定的結果正確答案:【算法必須在有限步操作之后停止#算法的每一步操作必須是明確的，不能有歧義或含義模糊#算法執(zhí)行后一定產生確定的結果】2、問題：以下哪些是算法的基本特點（）。選項：A、至少有1個輸入和1個輸出B、有窮性C、確定性D、可行性正確答案:【有窮性#確定性#可行性】“算法分析基礎”測試題1、問題：以下關于漸近記號的性質，正確的有（）選項：A、B、C、D、正確答案:【】2、問題：以下關于記號的定義，正確的是（）選項：A、存在正常數(shù)和使得對所有有：B、C、存在正常數(shù)和使得對所有有：對于任何正常數(shù)對于任何正常數(shù)，存在正數(shù)和使得對所有使得對所有有：有：有：D、，存在正數(shù)和正確答案:【存在正常數(shù)和使得對所有】3、問題：若一個算法的遞歸方程為）選項：，則其時間復雜度為（A、B、C、D、正確答案:【】4、問題：選項：表示當輸入規(guī)模為時的算法效率，以下算法效率最優(yōu)的是（）A、B、C、D、正確答案:【】“分治法”算法實現(xiàn)題“分治法”單元測試1、問題：分治法的設計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題（）。選項：A、問題規(guī)模相同，問題性質相同B、問題規(guī)模相同，問題性質不同C、問題規(guī)模不同，問題性質相同D、問題規(guī)模不同，問題性質不同正確答案:【問題規(guī)模不同，問題性質相同】2、問題：在尋找n個元素中第k小元素問題中，如快速排序算法思想，運用分治算法對n個元素進行劃分，如何選擇劃分基準？下面（）答案解釋最合理。選項：A、隨機選擇一個元素作為劃分基準B、取子序列的第一個元素作為劃分基準C、用中位數(shù)的中位數(shù)方法尋找劃分基準D、以上皆可行。但不同方法，算法復雜度上界可能不同正確答案:【以上皆可行。但不同方法，算法復雜度上界可能不同】3、問題：減少子問題個數(shù)，就是減少時間復雜度函數(shù)T(n)=aT(n/b)+f(n)中的（）值。選項：A、nB、aC、bD、f(n)正確答案:【a】4、問題：使用分治法求解不需要滿足的條件是（）。選項：A、子問題不能夠重復B、子問題必須具有相同的性質C、子問題的解可以合并D、原問題和子問題使用相同的方法求解正確答案:【子問題不能夠重復】5、問題：改進分治算法的方法有（）。選項：A、減少子問題的個數(shù)B、減少合并的時間C、減少問題的規(guī)模D、改進分治的均衡度正確答案:【減少子問題的個數(shù)#減少合并的時間#改進分治的均衡度】6、填空題：閱讀以下代碼:intFun(intn){if(n=1)return1;intFirst=Fun(n-1);intSecond=Fun(n-2);intiSum=First+Second;returniSum;}調用該函數(shù)，假設輸入?yún)?shù)n值為5，當程序第二次執(zhí)行語句iSum=First+Second時，iSum的值為（）。正確答案:【3】“動態(tài)規(guī)劃法”算法實現(xiàn)題“回溯法”算法實現(xiàn)題“分枝限界法”算法實現(xiàn)題“貪心法”算法實現(xiàn)題算法設計與分析考試題1、問題：分治法的設計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題（）。選項：A、問題規(guī)模相同，問題性質相同B、問題規(guī)模相同，問題性質不同C、問題規(guī)模不同，問題性質相同D、問題規(guī)模不同，問題性質不同正確答案:【問題規(guī)模不同，問題性質相同】2、問題：下面問題（）不能使用貪心法解決。選項：A、單源最短路徑問題B、n皇后問題C、最小生成樹問題D、背包問題正確答案:【n皇后問題】3、問題：對于0－1背包問題和背包問題的解法，下面（）答案解釋正確。選項：A、0－1背包問題和背包問題都可用貪心算法求得最優(yōu)解B、0－1背包問題可用貪心算法求解，但背包問題則不能用貪心算法求解C、0－1背包問題不能用貪心算法求最優(yōu)解，但可以使用動態(tài)規(guī)劃或搜索算法求解，而背包問題則可以用貪心算法求解D、因為0－1背包問題不具有最優(yōu)子結構性質，所以不能用貪心算法求解正確答案:【0－1背包問題不能用貪心算法求最優(yōu)解，但可以使用動態(tài)規(guī)劃或搜索算法求解，而背包問題則可以用貪心算法求解】4、問題：常見的兩種分支限界法為（）。選項：A、廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法B、隊列式（FIFO）分支限界法與堆棧式分支限界法C、排列樹法與子集樹法D、隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法正確答案:【隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法】5、問題：T(n)表示當輸入規(guī)模為n時的算法效率，以下算法效率最優(yōu)的是（）。選項：A、B、C、D、正確答案:【】6、問題：算法分析中，記號Θ表示（）。選項：A、漸近下界B、漸近上界C、非緊上界D、漸近緊界正確答案:【漸近緊界】7、問題：采用最大效益優(yōu)先搜索方式的算法是（）。選項：A、分支限界法B、動態(tài)規(guī)劃法C、貪心法D、回溯法正確答案:【分支限界法】8、問題：在尋找n個元素中第k小元素問題中，如快速排序算法思想，運用分治算法對n個元素進行劃分，如何選擇劃分基準？下面（）答案解釋最合理。選項：A、隨機選擇一個元素作為劃分基準B、取子序列的第一個元素作為劃分基準C、用中位數(shù)作為劃分基準D、以上皆可行。但不同方法，算法復雜度上界可能不同正確答案:【以上皆可行。但不同方法，算法復雜度上界可能不同】9、問題：回溯法在問題的解空間樹中，按（）策略，從根結點出發(fā)搜索解空間樹。選項：A、廣度優(yōu)先B、活結點優(yōu)先C、擴展結點優(yōu)先D、深度優(yōu)先正確答案:【深度優(yōu)先】10、問題：優(yōu)先隊列式分支限界法選取擴展結點的原則是（）。選項：A、先進先出B、后進先出C、結點的優(yōu)先級D、隨機正確答案:【結點的優(yōu)先級】11、問題：歸并排序算法是利用（）實現(xiàn)的算法選項：A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法正確答案:【分治策略】12、問題：（）是回溯法中為避免無效搜索采取的策略。選項：A、遞歸函數(shù)B、剪枝函數(shù)C、隨機數(shù)函數(shù)D、限界函數(shù)正確答案:【剪枝函數(shù)】13、問題：找n個元素的中位數(shù)的分治算法的時間復雜度為()。選項：A、B、C、D、正確答案:【】14、問題：回溯法的算法框架按照問題的解空間一般分為子集樹算法框架與（）算法框架。選項：A、深度優(yōu)先生成樹B、二叉樹C、廣度優(yōu)先生成樹D、排列樹正確答案:【排列樹】15、問題：矩陣連乘問題的算法可由（）設計實現(xiàn)選項：A、貪心算法B、回溯算法C、動態(tài)規(guī)劃算法D、分支界限算法正確答案:【動態(tài)規(guī)劃算法】16、問題：算法是由若干條指令組成的有窮序列，而且滿足以下性質（）。選項：A、輸入：有0個或多個輸入B、輸出：至少有一個輸出C、確定性：指令清晰，無歧義D、有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時間有限正確答案:【輸入：有0個或多個輸入#輸出：至少有一個輸出#確定性：指令清晰，無歧義#有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時間有限】17、問題：求解遞歸方程使用的方法有（）。選項：A、迭代法B、代入法C、主定理D、遞歸樹正確答案:【迭代法#代入法#主定理#遞歸樹】18、問題：分治法所能解決的問題一般具有（）特征。選項：A、問題可以分解為規(guī)模較小的子問題B、子問題可合并為原問題的解C、小規(guī)模子問題可解D、子問題不相互獨立正確答案:【問題可以分解為規(guī)模較小的子問題#子問題可合并為原問題的解#小規(guī)模子問題可解】19、問題：回溯法的效率依賴于下列哪些因素（）。選項：A、滿足顯式約束的值的個數(shù)B、計算限界函數(shù)的時間C、確定解空間的時間D、計算約束函數(shù)的時間正確答案:【滿足顯式約束的值的個數(shù)#計算限界函數(shù)的時間#計算約束函數(shù)的時間】20、問題：改進分治算法的方法有（）。選項：A、改進分治的均衡度B、減少合并的時間C、減少子問題的個數(shù)D、減少問題的規(guī)模正確答案:【改進分治的均衡度#減少合并的時間#減少子問題的個數(shù)】21、問題：無論在何種情況下，分治法總能產生效率最高的算法。選項：A、正確B、錯誤正確答案:【錯誤】22、問題：一個算法是正確的，那么它就是