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

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