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