MOOC 算法設(shè)計(jì)與分析-武漢理工大學(xué) 中國(guó)大學(xué)慕課答案

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