算法設計和分析復習試題目及答案解析

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

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

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

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

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