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

1、分治法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)棋盤(pán)覆蓋算法利用的算法是（分治法）。29、使用分治法求解不需要滿(mǎn)足的條件是（子問(wèn)題必須是一樣的）。不可以使用分治法求解的是（01背包問(wèn)題）。動(dòng)態(tài)規(guī)劃下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（構(gòu)造最優(yōu)解

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

3、貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)）?；厮莘ɑ厮莘ń饴眯惺圬泦T問(wèn)題時(shí)的解空間樹(shù)是（排列樹(shù)）。剪枝函數(shù)是回溯法中為避免無(wú)效搜索采取的策略回溯法的效率不依賴(lài)于下列哪些因素（確定解空間的時(shí)間）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）4201背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）.47.背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（B）。A、O（n2n）B、O（nlogn）C

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

5、4)D(1)(2)(3)(4)57、函數(shù)32n10nlogn的漸進(jìn)表達(dá)式是(B).A.2nB.32nC.nlognD.10nlogn59、用動(dòng)態(tài)規(guī)劃算法解決最大字段和問(wèn)題，其時(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)則稱(chēng)函數(shù)f(N)當(dāng)N充分大時(shí)有下界g(N)記作f(N)∈○(g(N))即f(N)的階(A)