



下載本文檔
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
算法設(shè)計(jì)與分析知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋蘇州大學(xué)第一章單元測(cè)試
下列對(duì)算法的理解不正確的是()。
A:算法要求是一步步執(zhí)行,每一步都能得到唯一的結(jié)果B:算法一般是機(jī)械的,有時(shí)要進(jìn)行大量重復(fù)的計(jì)算,它的優(yōu)點(diǎn)是一種通法C:算法有一個(gè)共同特點(diǎn)就是對(duì)一類(lèi)問(wèn)題都有效(而不是個(gè)別問(wèn)題)D:任何問(wèn)題都可以用算法來(lái)解決
答案:任何問(wèn)題都可以用算法來(lái)解決算法漸近時(shí)間復(fù)雜度的分析主要關(guān)注哪一方面?()
A:低階項(xiàng)和常系數(shù)的精確計(jì)算B:最高次項(xiàng)的系數(shù)C:實(shí)際運(yùn)行時(shí)間的精確測(cè)量D:最高次項(xiàng)并忽略常系數(shù)
答案:最高次項(xiàng)并忽略常系數(shù)漸近時(shí)間復(fù)雜度分析中,通常認(rèn)為哪種情況對(duì)算法選擇更重要?()
A:最壞情況B:最好情況C:最佳和最壞情況的平均D:平均情況
答案:最壞情況使用漸近符號(hào)的函數(shù)通常刻畫(huà)算法的運(yùn)行時(shí)間,但是漸近符號(hào)也可以適用于刻畫(huà)算法的某個(gè)其他方面的函數(shù),甚至可以適用于和算法沒(méi)有任何關(guān)系的函數(shù)。()
A:錯(cuò)B:對(duì)
答案:對(duì)在算法分析中,常用大O記號(hào)限制算法的()。
A:平均情況運(yùn)行時(shí)間B:最好情況運(yùn)行時(shí)間C:最壞情況運(yùn)行時(shí)間
答案:最壞情況運(yùn)行時(shí)間
第二章單元測(cè)試
下面關(guān)于NP問(wèn)題說(shuō)法正確的是()
A:NP問(wèn)題都是不可能解決的問(wèn)題B:NP完全問(wèn)題是P類(lèi)問(wèn)題的子集C:NP類(lèi)問(wèn)題包含在P類(lèi)問(wèn)題中D:P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中
答案:P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中下面關(guān)于NPC問(wèn)題說(shuō)法不正確的是()
A:所有的NPC問(wèn)題之間可相互歸約B:非確定性多項(xiàng)式時(shí)間不可解決C:如果一個(gè)NPC問(wèn)題在多項(xiàng)式時(shí)間可解,則所有NP問(wèn)題在多項(xiàng)式時(shí)間可解D:所有的NP類(lèi)問(wèn)題可歸約成該問(wèn)題
答案:非確定性多項(xiàng)式時(shí)間不可解決假設(shè)存在兩個(gè)問(wèn)題X、Y,問(wèn)題X可以在多項(xiàng)式時(shí)間內(nèi)歸約為問(wèn)題Y,下面說(shuō)法正確的是()
A:如果問(wèn)題X是NPC,那么問(wèn)題Y是NP-hard的B:如果問(wèn)題X是NP-hard,那么問(wèn)題Y也是NP難的C:如果問(wèn)題X是NP-hard,那么問(wèn)題Y是NPCD:如果Y是易處理的(多項(xiàng)式時(shí)間可解),那么問(wèn)題X也是易處理的
答案:如果問(wèn)題X是NP-hard,那么問(wèn)題Y也是NP難的;如果Y是易處理的(多項(xiàng)式時(shí)間可解),那么問(wèn)題X也是易處理的假設(shè)集合I是圖G的獨(dú)立集,集合C是圖G的頂點(diǎn)覆蓋集,下面說(shuō)法不正確的是()
A:對(duì)于圖G中任意一條邊(u,v),有u∈I或v∈IB:對(duì)于圖G中任意一條邊(u,v),有u∈C且v∈CC:假設(shè)V為圖G的頂點(diǎn)集合,則有I=V-CD:對(duì)于圖G中任意一條邊(u,v),有u∈C或v∈C
答案:對(duì)于圖G中任意一條邊(u,v),有u∈I或v∈I下列關(guān)于CNF-SAT問(wèn)題的說(shuō)法中,正確的是()
A:對(duì)于任意的CNF都存在使得表達(dá)式為真的賦值B:CNF-SAT是一個(gè)P問(wèn)題C:3-CNF可滿(mǎn)足性問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)被歸約到圖的獨(dú)立集問(wèn)題D:對(duì)于一個(gè)CNF-SAT問(wèn)題,可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解的正確性
答案:3-CNF可滿(mǎn)足性問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)被歸約到圖的獨(dú)立集問(wèn)題;對(duì)于一個(gè)CNF-SAT問(wèn)題,可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解的正確性
第三章單元測(cè)試
以下哪些算法或問(wèn)題是基于分治算法設(shè)計(jì)的或者能通過(guò)分治算法解決?()。
A:歸并排序B:快速排序C:二分查找D:漢諾塔
答案:歸并排序;快速排序;二分查找;漢諾塔分治法求解平面最接近點(diǎn)對(duì)問(wèn)題的時(shí)間復(fù)雜度是()。
A:
O(1)
B:
O(n)C:D:O(nlgn)E:F:G:O(n2)H:
答案:O(nlgn);快速傅里葉變換求解大整數(shù)乘法利用了插值計(jì)算的思想,通過(guò)將兩個(gè)大整數(shù)分別表示為多項(xiàng)式形式,利用FFT求解點(diǎn)值對(duì),最后利用離散傅里葉變換求解出系數(shù)向量。()
A:對(duì)B:錯(cuò)
答案:錯(cuò)在計(jì)算矩陣乘法時(shí),Strassen算法提升性能的主要策略是什么?()
A:使用隨機(jī)化技術(shù)選擇子矩陣B:應(yīng)用快速傅里葉變換C:增加矩陣分解的級(jí)別D:將8個(gè)子問(wèn)題減少到7個(gè)
答案:將8個(gè)子問(wèn)題減少到7個(gè)在快速排序的隨機(jī)化版本中,對(duì)于所有輸入數(shù)據(jù),排序的時(shí)間復(fù)雜度始終保持不變。()
A:對(duì)B:錯(cuò)
答案:錯(cuò)
第四章單元測(cè)試
在使用動(dòng)態(tài)規(guī)劃求解最長(zhǎng)公共子序列問(wèn)題時(shí),下列哪個(gè)步驟描述了問(wèn)題的遞推過(guò)程?()
A:根據(jù)dp[m][n]的值,構(gòu)造最長(zhǎng)公共子序列。B:通過(guò)遞推關(guān)系式dp[i][j]=max(dp[i-1][j],dp[i][j-1]),填充dp數(shù)組。C:初始化邊界條件,即當(dāng)i或j為0時(shí),dp[i][j]=0。D:定義二維數(shù)組dp,其中dp[i][j]表示序列A的前i個(gè)元素和序列B的前j個(gè)元素的最長(zhǎng)公共子序列長(zhǎng)度。
答案:通過(guò)遞推關(guān)系式dp[i][j]=max(dp[i-1][j],dp[i][j-1]),填充dp數(shù)組。在0-1背包問(wèn)題中,動(dòng)態(tài)規(guī)劃的主要目的是什么?()
A:找到最輕的物品組合B:最大化背包中物品的總價(jià)值C:平衡背包中物品的重量和價(jià)值D:最小化背包中物品的數(shù)量
答案:最大化背包中物品的總價(jià)值在0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃求解方法中,遞歸式計(jì)算的是什么?()
A:確定哪些物品被選中B:判斷是否超過(guò)背包容量C:計(jì)算每個(gè)物品的價(jià)值D:計(jì)算達(dá)到當(dāng)前容量下的最大價(jià)值
答案:計(jì)算達(dá)到當(dāng)前容量下的最大價(jià)值矩陣鏈乘實(shí)質(zhì)上是一個(gè)最優(yōu)括號(hào)化問(wèn)題。()
A:錯(cuò)B:對(duì)
答案:對(duì)在動(dòng)態(tài)規(guī)劃問(wèn)題中,最優(yōu)子結(jié)構(gòu)要素描述了問(wèn)題的最優(yōu)解可以通過(guò)子問(wèn)題的最優(yōu)解來(lái)構(gòu)造。()
A:對(duì)B:錯(cuò)
答案:對(duì)
第五章單元測(cè)試
多機(jī)調(diào)度問(wèn)題是用貪心算法求最優(yōu)解的一個(gè)例子,貪心策略是每次從剩余任務(wù)中選擇一個(gè)花費(fèi)時(shí)間最長(zhǎng)的任務(wù),安排在占用時(shí)間最少的機(jī)器上。()
A:對(duì)B:錯(cuò)
答案:對(duì)下列問(wèn)題中不能用貪心算法求得最優(yōu)解的是()。
A:單源最短路徑問(wèn)題B:0-1背包問(wèn)題C:霍夫曼編碼問(wèn)題D:最小生成樹(shù)問(wèn)題
答案:0-1背包問(wèn)題所有可以用貪心法求出最優(yōu)解的問(wèn)題都可以形式化為在一個(gè)加權(quán)擬陣中找到一個(gè)權(quán)值最大的獨(dú)立子集。()
A:對(duì)B:錯(cuò)
答案:錯(cuò)若一應(yīng)用問(wèn)題能被抽象為在加權(quán)擬陣中尋找最優(yōu)子集,那么一定能用加權(quán)擬陣上的通用貪心算法求出其最優(yōu)解。()
A:錯(cuò)B:對(duì)
答案:對(duì)0-1背包問(wèn)題中每個(gè)物品有固定的重量和價(jià)值,要求不能將物品部分放入,需求解放入物品使得總價(jià)值最大。對(duì)于此問(wèn)題,以下哪種算法可以獲得最優(yōu)解?()
A:動(dòng)態(tài)規(guī)劃B:兩者均可C:無(wú)法確定D:貪心算法
答案:動(dòng)態(tài)規(guī)劃
第六章單元測(cè)試
下列不屬于放寬實(shí)際問(wèn)題求解中對(duì)時(shí)間性能要求的方法的是()
A:近似算法B:引入不確定性的算法C:超多項(xiàng)式時(shí)間啟發(fā)D:啟發(fā)式概率分析
答案:引入不確定性的算法下列問(wèn)題中,具有絕對(duì)近似算法的問(wèn)題是()
A:圖的邊著色問(wèn)題B:團(tuán)問(wèn)題C:圖的頂點(diǎn)著色問(wèn)題D:0-1背包問(wèn)題
答案:圖的邊著色問(wèn)題;圖的頂點(diǎn)著色問(wèn)題。()
A:對(duì)B:錯(cuò)
答案:錯(cuò)FPTAS算法的時(shí)間復(fù)雜度是()
A:多項(xiàng)式時(shí)間B:指數(shù)時(shí)間C:不確定,取決于輸入規(guī)模D:對(duì)數(shù)時(shí)間
答案:多項(xiàng)式時(shí)間FPTAS算法的第一步是對(duì)0-1背包問(wèn)題中的什么進(jìn)行適當(dāng)?shù)目s放,以確保算法的多項(xiàng)式性質(zhì)?()
A:價(jià)值B:重量C:物品數(shù)量D:容量
答案:價(jià)值
第七章單元測(cè)試
在使用數(shù)字型概率算法求解定積分的時(shí)候,為達(dá)到一定的精度,假設(shè)一維積分需要1000個(gè)采樣點(diǎn)才能達(dá)到一定精度,那么三維積分需要的采樣點(diǎn)數(shù)量可能為()。
A:1000^2B:1000C:1000^3D:任意數(shù)目的點(diǎn)都可以
答案:1000^3在計(jì)算π值的問(wèn)題中,Crude算法的方差和精度都優(yōu)于HitorMiss算法,因此它總是更優(yōu)的。()
A:錯(cuò)B:對(duì)
答案:錯(cuò)在使用有回放抽樣并統(tǒng)計(jì)第一次重復(fù)抽樣所用的實(shí)驗(yàn)次數(shù)的方法來(lái)估計(jì)集合的勢(shì)的時(shí)候,這種算法的時(shí)間復(fù)雜度和空間復(fù)雜度均為θ(√n)(n為集合的勢(shì))
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 第12課+近代西方民族國(guó)家與國(guó)際法的發(fā)展+教學(xué)設(shè)計(jì)-2024-2025學(xué)年高二上學(xué)期歷史統(tǒng)編版(2019)選擇性必修1國(guó)家制度與社會(huì)治理
- 2025年河南聽(tīng)力測(cè)試試題及答案
- 2025年農(nóng)場(chǎng)紅袋子測(cè)試題及答案
- 2025年動(dòng)畫(huà)制作員考試題及答案
- 2025年專(zhuān)項(xiàng)驗(yàn)收測(cè)試題及答案
- 2025年非你莫屬面試題及答案
- 2025年供熱鍋爐筆試試題及答案
- 2025年丹陽(yáng)轉(zhuǎn)學(xué)考試試題及答案
- 2025年蕪湖事業(yè)編面試題及答案
- 2025年圍棋考試題材分析及答案
- 全民族抗戰(zhàn)山西記憶教學(xué)課件
- 小型玉米脫粒機(jī)設(shè)計(jì)畢業(yè)設(shè)計(jì)論文
- 青蛙賣(mài)泥塘話(huà)劇稿子
- 化學(xué)中常用的實(shí)驗(yàn)方法(第一課時(shí)物質(zhì)的制備)課件 【核心知識(shí)精講精研】 上學(xué)期高一滬科版(2020)必修第一冊(cè)
- 江西省宜春市高職單招2022-2023學(xué)年醫(yī)學(xué)綜合真題及答案
- 砌體結(jié)構(gòu)教案
- 煤礦崗位作業(yè)流程標(biāo)準(zhǔn)化手冊(cè)2021
- 《入團(tuán)志愿書(shū)》填寫(xiě)說(shuō)明
- 分式方程有增根和無(wú)解
- 外傷急救知識(shí)外傷急救包扎技術(shù)培訓(xùn)PPT教學(xué)課件
- 2022年山西職業(yè)技術(shù)學(xué)院?jiǎn)握忻嬖囋囶}及答案解析
評(píng)論
0/150
提交評(píng)論