算法設(shè)計(jì)和分析復(fù)習(xí)試題目及答案解析

1、范文范例學(xué)習(xí)指導(dǎo)wd完美整理版分治法1、二分搜索算法是利用（分治策略）實(shí)現(xiàn)的算法。9.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（分治策略）27、Strassen矩陣乘法是利用（分治策略）實(shí)現(xiàn)的算法。34實(shí)現(xiàn)合并排序利用的算法是（分治策略）。實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（分治策略）。17實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（分治法）。29、使用分治法求解不需要滿足的條件是（子問題必須是一樣的）。不可以使用分治法求解的是（01背包問題）。動(dòng)態(tài)規(guī)劃下列不是動(dòng)態(tài)規(guī)

2、劃算法基本步驟的是（構(gòu)造最優(yōu)解）下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（子問題重疊性質(zhì)）。下列算法中通常以自底向上的方式求解最優(yōu)解的是（動(dòng)態(tài)規(guī)劃法）備忘錄方法是那種算法的變形。（動(dòng)態(tài)規(guī)劃法）最長公共子序列算法利用的算法是（動(dòng)態(tài)規(guī)劃法）。矩陣連乘問題的算法可由（動(dòng)態(tài)規(guī)劃算法B）設(shè)計(jì)實(shí)現(xiàn)。實(shí)現(xiàn)最大子段和利用的算法是（動(dòng)態(tài)規(guī)劃法）。貪心算法能解決的問題：?jiǎn)卧醋疃搪窂絾栴}，最小花費(fèi)生成樹問題，背包問題，活動(dòng)安排問題，不能解決的問題：N皇后問題，01背包

3、問題是貪心算法的基本要素的是（貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)）?；厮莘ɑ厮莘ń饴眯惺圬泦T問題時(shí)的解空間樹是（排列樹）。剪枝函數(shù)是回溯法中為避免無效搜索采取的策略回溯法的效率不依賴于下列哪些因素（確定解空間的時(shí)間）范文范例學(xué)習(xí)指導(dǎo)wd完美整理版A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）4201背包問題的回溯算法所需的計(jì)算時(shí)間為（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）.47.背包問題的貪心算法所

4、需的計(jì)算時(shí)間為（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）53采用貪心算法的最優(yōu)裝載問題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）56、算法是由若干條指令組成的有窮序列，而且滿足以下性質(zhì)（D）（1）輸入：有0個(gè)或多個(gè)輸入（2）輸出：至少有一個(gè)輸出（3）確定性：指令清晰，無歧義（4）有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時(shí)間

5、有限A(1)(2)(3)B(1)(2)(4)C(1)(3)(4)D(1)(2)(3)(4)57、函數(shù)32n10nlogn的漸進(jìn)表達(dá)式是(B).A.2nB.32nC.nlognD.10nlogn59、用動(dòng)態(tài)規(guī)劃算法解決最大字段和問題，其時(shí)間復(fù)雜性為(B).A.lognB.nC.n2D.nlogn61、設(shè)f(N)g(N)是定義在正數(shù)集上的正函數(shù)如果存在正的常數(shù)C和自然數(shù)N0使得當(dāng)N≥N0時(shí)有f(N)≤Cg(N)則稱函數(shù)f(N)當(dāng)N充分大時(shí)有