【MOOC】算法設(shè)計(jì)與分析-北京航空航天大學(xué) 中國(guó)大學(xué)慕課MOOC答案

【MOOC】算法設(shè)計(jì)與分析-北京航空航天大學(xué)中國(guó)大學(xué)慕課MOOC答案第1章單元測(cè)驗(yàn)1、【單選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【】2、【單選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【】3、【單選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【】4、【單選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【】5、【單選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【】6、【單選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【】7、【單選題】下述偽代碼希望求出數(shù)組中數(shù)字出現(xiàn)的次數(shù)，則偽代碼空白處應(yīng)填入______輸入：數(shù)組，數(shù)字輸出：在數(shù)組中出現(xiàn)的次數(shù)fortoifthen________endendreturn本題答案：【】8、【多選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【##】9、【多選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【###】10、【多選題】函數(shù)用記號(hào)可表示為_(kāi)_____本題答案：【#】第2章單元測(cè)驗(yàn)1、【單選題】在歸并排序算法中，若每次分解將長(zhǎng)度為n的數(shù)組分為兩段，長(zhǎng)度分別為n-1和1，此時(shí)歸并排序算法的時(shí)間復(fù)雜度為_(kāi)___本題答案：【】2、【單選題】在歸并排序算法中，若每次分解將長(zhǎng)度為n的數(shù)組分為四段長(zhǎng)度為n/4的子數(shù)組進(jìn)行遞歸，此時(shí)歸并排序算法的時(shí)間復(fù)雜度為_(kāi)___本題答案：【】3、【單選題】歸并排序的最好情況時(shí)間復(fù)雜度為_(kāi)___本題答案：【】4、【單選題】的解為=——本題答案：【】5、【單選題】的解為_(kāi)___本題答案：【】6、【單選題】的解為_(kāi)___本題答案：【】7、【單選題】的解為_(kāi)___本題答案：【】8、【單選題】的解為_(kāi)___本題答案：【】9、【單選題】在最大子數(shù)組問(wèn)題的優(yōu)化枚舉算法中，每次計(jì)算子數(shù)組X[i..j]之和的時(shí)間復(fù)雜度為_(kāi)___本題答案：【】10、【單選題】在最大子數(shù)組問(wèn)題的分治算法中，若可以用O(1)的時(shí)間求得跨越中點(diǎn)的最大子數(shù)組，則該算法的時(shí)間復(fù)雜度為本題答案：【】第3章單元測(cè)驗(yàn)1、【單選題】數(shù)組中的逆序?qū)€(gè)數(shù)為_(kāi)___本題答案：【5】2、【單選題】長(zhǎng)度為的數(shù)組中逆序?qū)€(gè)數(shù)最多為_(kāi)___本題答案：【】3、【單選題】快速排序算法的最壞情況時(shí)間復(fù)雜度為_(kāi)___本題答案：【】4、【單選題】在快速排序算法中，假定存在一個(gè)神奇的黑盒可以在O(1)的時(shí)間內(nèi)給出最好的主元（也就是中位數(shù)），那么使用此神奇黑盒的快速排序算法最差運(yùn)行時(shí)間為_(kāi)___（請(qǐng)選擇最準(zhǔn)確的答案）本題答案：【】5、【單選題】隨機(jī)化快速排序算法的最壞情況時(shí)間復(fù)雜度為_(kāi)___（請(qǐng)選擇最準(zhǔn)確的答案）本題答案：【】6、【單選題】隨機(jī)化快速排序算法的期望時(shí)間復(fù)雜度為_(kāi)___（請(qǐng)選擇最準(zhǔn)確的答案）本題答案：【】7、【單選題】快速排序算法的關(guān)鍵為數(shù)組的劃分，下面給出了一種劃分?jǐn)?shù)組的方法，其中空白處應(yīng)填入____輸入：數(shù)組，起始位置，終止位置輸出：劃分位置whiledowhileanddoendifthenendwhileanddoendifthenendendreturn本題答案：【】8、【單選題】下面給出了計(jì)算Fibonacci數(shù)列第項(xiàng)的偽代碼，該算法的時(shí)間復(fù)雜度為_(kāi)___（請(qǐng)選擇最準(zhǔn)確的答案）輸入：數(shù)字輸出：Fibonacci數(shù)列的第項(xiàng)iforthenreturnelsereturnend本題答案：【】9、【單選題】隨機(jī)化次序選擇算法的最壞情況時(shí)間復(fù)雜度為_(kāi)___（請(qǐng)選擇最準(zhǔn)確的答案）本題答案：【】10、【單選題】隨機(jī)化次序選擇算法的期望時(shí)間復(fù)雜度為_(kāi)___（請(qǐng)選擇最準(zhǔn)確的答案）本題答案：【】第4章單元測(cè)驗(yàn)1、【單選題】在0-1背包問(wèn)題中，若背包容量為20,5個(gè)物品的體積分別為，價(jià)格分別為。則該背包能容納物品的最大總價(jià)格為_(kāi)___本題答案：【25】2、【單選題】在商品個(gè)數(shù)為、背包容量為的0-1背包問(wèn)題中，蠻力枚舉算法和動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度分別為_(kāi)___本題答案：【】3、【單選題】0-1背包問(wèn)題中的遞推式為_(kāi)___本題答案：【】4、【單選題】下面給出了0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法偽代碼，其中空白處應(yīng)分別填入____輸入：商品數(shù)量,各商品價(jià)值，各商品體積，背包容量輸出：商品價(jià)格的最大值，最優(yōu)解方案創(chuàng)建二維數(shù)組fordoendfordoendfordofordoifthenendelseendendendfordoifthenprint選擇商品endelseprint不選擇商品endendreturn,本題答案：【】5、【單選題】設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的一般步驟為_(kāi)___本題答案：【問(wèn)題結(jié)構(gòu)分析→遞推關(guān)系建立→自底向上計(jì)算→最優(yōu)方案追蹤】6、【單選題】最大子數(shù)組問(wèn)題的分治算法和動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度分別為_(kāi)___（請(qǐng)選擇最準(zhǔn)確的答案）本題答案：【】7、【單選題】在最大子數(shù)組問(wèn)題的動(dòng)態(tài)規(guī)劃算法中，給出初始化部分的偽代碼如下，空白處應(yīng)填入____輸入：數(shù)組，數(shù)組長(zhǎng)度輸出：最大子數(shù)組和，子數(shù)組起止位置新建一維數(shù)組和//初始化本題答案：【】8、【單選題】在最大子數(shù)組問(wèn)題的動(dòng)態(tài)規(guī)劃算法中，給出計(jì)算部分的偽代碼如下，空白處應(yīng)填入___輸入：數(shù)組，數(shù)組長(zhǎng)度輸出：最大子數(shù)組和，子數(shù)組起止位置新建一維數(shù)組和對(duì)初始化//動(dòng)態(tài)規(guī)劃fordoifthenendelseendend本題答案：【】9、【單選題】在最大子數(shù)組問(wèn)題的動(dòng)態(tài)規(guī)劃算法中，給出查找解部分的偽代碼如下，空白處應(yīng)填入___輸入：數(shù)組，數(shù)組長(zhǎng)度輸出：最大子數(shù)組和，子數(shù)組起止位置新建一維數(shù)組和對(duì)初始化計(jì)算數(shù)組和數(shù)組//查找解fordoifthenendendreturn本題答案：【】10、【單選題】對(duì)于包含個(gè)正數(shù)元素的數(shù)組，我們希望找出數(shù)組中的一些元素，使得這些元素在數(shù)組中互不相鄰并且元素之和最大。例如在數(shù)組中，應(yīng)當(dāng)選擇和，元素之和為。給出該問(wèn)題的解決算法如下，空白處應(yīng)填入____輸入：正數(shù)數(shù)組，元素個(gè)數(shù)輸出：選擇的元素，最大不相鄰元素之和創(chuàng)建數(shù)組，表示數(shù)組中的最大不相鄰元素之和創(chuàng)建數(shù)組記錄選擇方案ifthenendelseendfordoifthenendelseendendreturn本題答案：【】第5章單元測(cè)驗(yàn)1、【單選題】給定兩個(gè)序列分別為“algorithm”和“glorhythm”。則以下分別為兩序列的最長(zhǎng)公共子序列和最長(zhǎng)公共子串的選項(xiàng)是____本題答案：【gorthmthm】2、【單選題】在最長(zhǎng)公共子序列問(wèn)題中，我們用表示序列和序列的最長(zhǎng)公共子序列長(zhǎng)度，則遞推式應(yīng)為_(kāi)___本題答案：【】3、【單選題】給出最長(zhǎng)公共子序列問(wèn)題的部分偽代碼如下，其中空白處應(yīng)分別填入____輸入：兩個(gè)序列輸出：的最長(zhǎng)公共子序列分別代表的序列長(zhǎng)度//初始化新建二維數(shù)組fordoendfordoendfordofordoifthenendelseifthenendelseendendend本題答案：【】4、【單選題】在最長(zhǎng)公共子串問(wèn)題的遞推式中，表示____本題答案：【和中以和結(jié)尾的最長(zhǎng)公共子串的長(zhǎng)度】5、【單選題】最長(zhǎng)公共子串問(wèn)題的遞推式為本題答案：【】6、【單選題】給定兩個(gè)字符串,需要判斷中有多少個(gè)子序列與相等。例如：則和兩個(gè)子序列都與相等。思考該問(wèn)題，可以用表示的子序列中與相等的個(gè)數(shù)，如上例。則對(duì)應(yīng)的遞推式為_(kāi)__本題答案：【】7、【單選題】在支持插入、刪除、替換三種操作的最小編輯距離問(wèn)題中，我們用表示字符串變?yōu)榈淖钚【庉嬀嚯x，則遞推式應(yīng)為本題答案：【】8、【單選題】在支持插入、刪除、替換三種操作的最小編輯距離問(wèn)題中，用數(shù)組來(lái)記錄編輯方案。則數(shù)組中的L,U,LU分別代表哪種操作___本題答案：【插入刪除替換/空操作】9、【單選題】字符串“algorithm”到字符串“altruistic”的最小編輯距離為_(kāi)__本題答案：【6】10、【單選題】下面給出了最長(zhǎng)公共子序列問(wèn)題中輸出最長(zhǎng)公共子序列的函數(shù)Print-LCS()偽代碼，其中空白處應(yīng)分別填入____輸入：追蹤數(shù)組，序列，當(dāng)前位置和輸出：的最長(zhǎng)公共子序列ifthenreturnendifthenPrint-LCS(,,,)printelseifthenPrint-LCS(,,,)endelsePrint-LCS(,,,)end本題答案：【】第6章單元測(cè)驗(yàn)1、【單選題】在鋼條切割問(wèn)題中，若鋼條長(zhǎng)度為，且長(zhǎng)度從到的鋼條價(jià)格分別為。則切割后鋼條的最大總收益為_(kāi)___本題答案：【】2、【單選題】在矩陣鏈乘法問(wèn)題中，矩陣鏈中矩陣的規(guī)模分別為。則該矩陣鏈所需標(biāo)量乘法的最小次數(shù)為_(kāi)___次本題答案：【】3、【單選題】在鋼條切割問(wèn)題中，表示切割長(zhǎng)度為的鋼條可得最大總收益，表示長(zhǎng)度為的鋼條的價(jià)格，則遞推式為_(kāi)___本題答案：【】4、【單選題】下面給出了鋼條切割問(wèn)題的動(dòng)態(tài)規(guī)劃算法的部分偽代碼，其中空白處應(yīng)分別填入____輸入：鋼條價(jià)格表，鋼條長(zhǎng)度輸出：最大收益，鋼條切割方案//初始化創(chuàng)建一維數(shù)組fordofordoifthenendendend輸出最優(yōu)方案return本題答案：【】5、【單選題】下面給出了鋼條切割問(wèn)題的動(dòng)態(tài)規(guī)劃算法中追蹤最優(yōu)方案部分的偽代碼，其中空白處應(yīng)分別填入____//輸出最優(yōu)方案whiledoprintend本題答案：【】6、【單選題】在矩陣鏈乘法問(wèn)題中，表示計(jì)算矩陣鏈所需標(biāo)量乘法的最小次數(shù)，則該問(wèn)題的遞推式為_(kāi)___本題答案：【】7、【單選題】在矩陣鏈乘法問(wèn)題的動(dòng)態(tài)規(guī)劃算法中，給出初始化部分的偽代碼如下，空白處應(yīng)填入___輸入：矩陣維度數(shù)組，矩陣個(gè)數(shù)輸出：最小標(biāo)量乘法次數(shù)，分割方式追蹤數(shù)組新建二維數(shù)組和//初始化forthenend本題答案：【】8、【單選題】在矩陣鏈乘法問(wèn)題的動(dòng)態(tài)規(guī)劃算法中，給出計(jì)算部分的偽代碼如下，空白處應(yīng)填入輸入：矩陣維度數(shù)組，矩陣個(gè)數(shù)輸出：最小標(biāo)量乘法次數(shù)，分割方式追蹤數(shù)組新建二維數(shù)組和初始化//動(dòng)態(tài)規(guī)劃fordofordofordoifthenendendendendreturn本題答案：【】9、【單選題】在矩陣鏈乘法問(wèn)題的動(dòng)態(tài)規(guī)劃算法中，給出追蹤最優(yōu)方案部分的偽代碼如下，空白處應(yīng)填入____Print-Matrix-Chain()輸入：矩陣鏈,追蹤數(shù)組,位置索引和輸出：矩陣鏈加括號(hào)方式ifthenprintreturnendprint“(”P(pán)rint-Matrix-Chain(,,,)print“)(”P(pán)rint-Matrix-Chain(,,,)print“)”return本題答案：【】10、【單選題】對(duì)某僅包含左右括號(hào)的字符串而言，若其中左括號(hào)和右括號(hào)可以正確的匹配，那么稱(chēng)其為均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。給定一個(gè)長(zhǎng)度為n的僅包含左右括號(hào)的字符串S，請(qǐng)求出字符串S的最長(zhǎng)均衡子序列。換言之，請(qǐng)從S中挑選出盡量多的字符按順序組成新字符串S'，使得S'是一個(gè)均衡字符串。例如，對(duì)字符串“())(()”而言，我們可以挑選其中第1，2，5，6個(gè)字符構(gòu)成一個(gè)長(zhǎng)度為的均衡字符串“()()”。我們用表示字符串的最長(zhǎng)均衡子序列長(zhǎng)度，則其遞推式應(yīng)為_(kāi)___本題答案：【】第7章單元測(cè)驗(yàn)1、【單選題】在部分背包問(wèn)題中，若背包容量為，有個(gè)物品可供選擇。每個(gè)物品價(jià)格分別為，體積分別為。則該背包可容納物品最大總價(jià)格為_(kāi)___本題答案：【】2、【單選題】下面給出了部分背包問(wèn)題的貪心算法的偽代碼，其中空白處應(yīng)分別填入輸入：商品數(shù)量,各商品的價(jià)值,各商品的體積，背包容量輸出：商品價(jià)格的最大值計(jì)算商品性?xún)r(jià)比并按降序排序//分別表示性?xún)r(jià)比第大的商品的性?xún)r(jià)比、價(jià)格和體積//根據(jù)貪心策略求解whiledoifthen選擇商品endelse選擇體積的商品endendreturn本題答案：【】3、【單選題】給出共5個(gè)字符，其出現(xiàn)頻數(shù)(千次)分別為。按照課程中所講左0右1，左小右大的規(guī)則建樹(shù)編碼，則字符串的霍夫曼編碼應(yīng)為_(kāi)___本題答案：【】4、【單選題】下面給出了霍夫曼編碼問(wèn)題的算法的偽代碼，其中空白處應(yīng)分別填入___輸入：各字符頻數(shù)，字符數(shù)輸出：霍夫曼編碼樹(shù)//預(yù)處理將遞增排序新建結(jié)點(diǎn)數(shù)組fordoendfordo新建結(jié)點(diǎn)endreturn本題答案：【】5、【單選題】在活動(dòng)選擇問(wèn)題中，給出6個(gè)活動(dòng)其時(shí)間分別為,則最多能安排活動(dòng)數(shù)為_(kāi)___本題答案：【】6、【單選題】下面給出了活動(dòng)選擇問(wèn)題的算法的偽代碼，其中空白處應(yīng)分別填入____輸入：活動(dòng)集合,每個(gè)活動(dòng)的起止時(shí)間輸出：不沖突活動(dòng)的最大子集將活動(dòng)按照結(jié)束時(shí)間升序排序，使表示結(jié)束時(shí)間第小的活動(dòng)fordoifthenendendreturn本題答案：【】7、【單選題】在加權(quán)活動(dòng)選擇問(wèn)題中，給出個(gè)活動(dòng)其時(shí)間分別為,權(quán)重分別為,則安排權(quán)重最大和為_(kāi)__本題答案：【】8、【單選題】在加權(quán)活動(dòng)選擇問(wèn)題中有個(gè)活動(dòng)組成的集合，令表示集合中不沖突活動(dòng)最大權(quán)重和，為以活動(dòng)開(kāi)始前最后結(jié)束的活動(dòng)，為活動(dòng)的權(quán)重。則遞推式為_(kāi)___本題答案：【】9、【單選題】給出加權(quán)活動(dòng)選擇問(wèn)題部分偽代碼如下，空白處應(yīng)填入___輸入：活動(dòng)集合,每個(gè)活動(dòng)的起止時(shí)間，權(quán)重輸出：不沖突活動(dòng)的最大子集將活動(dòng)按照結(jié)束時(shí)間升序排序，使表示結(jié)束時(shí)間第小的活動(dòng)fordo二分查找求解end新建數(shù)組//動(dòng)態(tài)規(guī)劃fordoifthenendelseendendreturn本題答案：【】10、【單選題】給出加權(quán)活動(dòng)選擇問(wèn)題輸出方案部分偽代碼如下，空白處應(yīng)填入____//輸出方案whiledoifthenprint選擇endelseendend本題答案：【】第8章單元測(cè)驗(yàn)1、【單選題】對(duì)圖深度優(yōu)先搜索（DFS）遍歷該圖的時(shí)間復(fù)雜度為_(kāi)___（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】2、【單選題】圖的生成子圖應(yīng)包含個(gè)頂點(diǎn)，至少條邊本題答案：【】3、【單選題】無(wú)向圖的一個(gè)連通分量包含個(gè)頂點(diǎn)，則該連通分量應(yīng)至少包含____條邊本題答案：【】4、【單選題】已知無(wú)向圖是包含棵樹(shù)的森林，且該圖頂點(diǎn)數(shù)與邊數(shù)相加之和為即。則該森林頂點(diǎn)數(shù)為_(kāi)___本題答案：【42】5、【單選題】已知圖深度優(yōu)先搜索（DFS）的搜索樹(shù)為一棵滿(mǎn)二叉樹(shù)如下圖所示，樹(shù)中有個(gè)點(diǎn)的發(fā)現(xiàn)時(shí)刻和結(jié)束時(shí)刻相差。則根節(jié)點(diǎn)的發(fā)現(xiàn)時(shí)刻和結(jié)束時(shí)刻相差____本題答案：【13】6、【單選題】無(wú)向圖包含7個(gè)頂點(diǎn)，10條邊，其鄰接表和結(jié)構(gòu)如下圖所示。以頂點(diǎn)作為起點(diǎn)執(zhí)行深度優(yōu)先搜索（DFS），搜索時(shí)按照鄰接表順序遍歷某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。得到如下圖所示搜索樹(shù)。其中頂點(diǎn)1、2、3處應(yīng)分別填入____本題答案：【】7、【多選題】在上題中，均不在搜索樹(shù)中的邊有哪些____（多選）本題答案：【#】8、【多選題】在扇形圖(FanGraph)中，其鄰接表和結(jié)構(gòu)如下第一張圖所示。從頂點(diǎn)開(kāi)始進(jìn)行廣度優(yōu)先搜索（BFS），搜索時(shí)按照鄰接表順序遍歷某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。得到搜索樹(shù)如下第二張圖，該搜索樹(shù)并未畫(huà)全，應(yīng)從虛線(xiàn)中選擇____補(bǔ)全。（多選）本題答案：【①#②】9、【多選題】同上題，在扇形圖(FanGraph)中，其鄰接表和結(jié)構(gòu)如下圖所示。從頂點(diǎn)開(kāi)始進(jìn)行廣度優(yōu)先搜索（BFS），搜索時(shí)按照鄰接表順序遍歷某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)得到搜索樹(shù)如下，該搜索樹(shù)并未畫(huà)全，應(yīng)從虛線(xiàn)中選擇____補(bǔ)全。（多選）本題答案：【①#③】10、【多選題】同上題，在扇形圖(FanGraph)中，其鄰接表和結(jié)構(gòu)如下第一張圖所示。從頂點(diǎn)開(kāi)始進(jìn)行深度優(yōu)先搜索（DFS），搜索時(shí)按照鄰接表順序遍歷某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。得到搜索樹(shù)如下第二張圖所示，該搜索樹(shù)并未畫(huà)全，應(yīng)從虛線(xiàn)中選擇____補(bǔ)全。（多選）本題答案：【①#②#④】第9章單元測(cè)試1、【單選題】有向圖上包含個(gè)頂點(diǎn)的強(qiáng)連通分量應(yīng)至少包含____條邊。本題答案：【】2、【單選題】已知有向圖有個(gè)頂點(diǎn)，且所有頂點(diǎn)入度之和與所有頂點(diǎn)出度之和相加為，則該圖有____條邊本題答案：【】3、【單選題】下面有向圖中存在強(qiáng)連通分量，可以將每個(gè)強(qiáng)連通分量看作一個(gè)點(diǎn)，得到新的圖。則中存在個(gè)點(diǎn)本題答案：【】4、【單選題】下面給出了使用深度優(yōu)先搜索(DFS)求強(qiáng)連通分量的部分偽代碼，其中空白處應(yīng)分別填入____本題答案：【】5、【單選題】給出判斷有向圖中是否存在環(huán)的算法偽代碼如下，空白處應(yīng)填入____本題答案：【】6、【單選題】給出深度優(yōu)先搜索（DFS）進(jìn)行拓?fù)渑判虻乃惴ㄈ缦?，則空白處應(yīng)填入____本題答案：【向結(jié)尾追加向結(jié)尾追加】7、【單選題】圖上的哈密頓路徑（Hamiltonianpath）是指將所有頂點(diǎn)恰好包含一次的路徑，如下左圖所示。但并非所有圖中都存在哈密頓路徑，如下右圖所示?，F(xiàn)在希望設(shè)計(jì)一個(gè)算法，判斷有向無(wú)環(huán)圖（DAG）上是否存在哈密頓路徑。給出算法的偽代碼如下，空白處應(yīng)填入____（提示：請(qǐng)思考拓?fù)湫蚝凸茴D路徑的關(guān)系）本題答案：【】8、【單選題】上題中判斷有向無(wú)環(huán)圖（DAG）是否存在哈密頓路徑的算法的時(shí)間復(fù)雜度是____（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】9、【多選題】對(duì)如下所示有向圖，從點(diǎn)開(kāi)始進(jìn)行深度優(yōu)先搜索（DFS），搜索時(shí)按照字典序遍歷某一節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。在得到的深度優(yōu)先搜索樹(shù)中，包含如下哪些類(lèi)別的邊（多選）本題答案：【樹(shù)邊#前向邊#后向邊#橫向邊】10、【多選題】對(duì)如下所示有向圖進(jìn)行拓?fù)渑判?，得到一個(gè)拓?fù)湫蛉缦聢D中所示。其中空白處可以依次填入三個(gè)字母。（多選）本題答案：【#】第10章單元測(cè)試1、【單選題】對(duì)如下所示連通無(wú)向圖，其最小生成樹(shù)的權(quán)重為本題答案：【23】2、【單選題】如下所示帶權(quán)的無(wú)向連通圖，存在割將圖的頂點(diǎn)集劃分為兩個(gè)點(diǎn)集和。則該割有條橫跨邊，有條輕邊。本題答案：【】3、【單選題】同上題所示帶權(quán)的連通無(wú)向圖，從點(diǎn)開(kāi)始使用Prim算法求圖的最小生成樹(shù)。已求得邊集,則接下來(lái)應(yīng)被添加進(jìn)集合的安全邊為。本題答案：【】4、【單選題】同上題所示帶權(quán)的連通無(wú)向圖，使用Kruskal算法求圖的最小生成樹(shù)時(shí)，邊按選項(xiàng)所示次序被選中，其中次序正確的選項(xiàng)是。本題答案：【】5、【單選題】給出求最小生成樹(shù)中時(shí)間復(fù)雜度為的Kruskal算法偽代碼如下，則空白處應(yīng)填入____本題答案：【】6、【單選題】給出求最小生成樹(shù)的Prim算法（不使用優(yōu)先隊(duì)列）偽代碼如下，則空白處應(yīng)填入____本題答案：【】7、【單選題】不使用優(yōu)先隊(duì)列和使用優(yōu)先隊(duì)列的Prim算法的時(shí)間復(fù)雜度分別為（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】8、【單選題】不相交集合的Create-Set操作和Find-Set操作的時(shí)間復(fù)雜度分別為、。Kruskal算法的時(shí)間復(fù)雜度為。（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】9、【單選題】不相交集合的Find-Set操作的時(shí)間復(fù)雜度與樹(shù)的高度有關(guān)。如下圖所示，查詢(xún)節(jié)點(diǎn)時(shí)，圖右的樹(shù)結(jié)構(gòu)顯然較圖左的樹(shù)結(jié)構(gòu)更為高效。我們可以通過(guò)改寫(xiě)Find-Set操作函數(shù)優(yōu)化樹(shù)結(jié)構(gòu)，該技巧也被稱(chēng)為“路徑壓縮”。該技巧主要思想是將查詢(xún)點(diǎn)到根節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)都直接連接在根節(jié)點(diǎn)下，如圖所示將路徑中的節(jié)點(diǎn)都直接連接在節(jié)點(diǎn)下。則改寫(xiě)后算法偽代碼空白處應(yīng)填入。本題答案：【】10、【單選題】對(duì)帶權(quán)的連通無(wú)向圖，將所有點(diǎn)劃分為個(gè)樹(shù)，且個(gè)樹(shù)的總邊權(quán)之和最小,若無(wú)法劃分為棵樹(shù)則輸出“NoAnswer”。如下圖所示，若，則應(yīng)按照?qǐng)D中顏色區(qū)分劃分為棵樹(shù)，邊權(quán)之和為。利用Kruskal算法解決該問(wèn)題的偽代碼如下，則空白處應(yīng)填入____。本題答案：【】第11章單元測(cè)試1、【單選題】下圖存在多條從源點(diǎn)到頂點(diǎn)的最短路徑，在Dijkstra算法運(yùn)行過(guò)程中首先找到的最短路徑是。本題答案：【】2、【單選題】下圖應(yīng)選擇算法求最短路徑，求得從a到z的最短路徑邊權(quán)和為_(kāi)___本題答案：【】3、【單選題】Dijkstra算法(使用優(yōu)先隊(duì)列)和Bellman-ford算法的時(shí)間復(fù)雜度分別是____（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】4、【單選題】給出Dijkstra算法(使用優(yōu)先隊(duì)列)偽代碼如下，空白處應(yīng)填入____本題答案：【】5、【單選題】給出Bellman-Ford算法偽代碼如下，則空白處應(yīng)填入____本題答案：【】6、【單選題】解決所有點(diǎn)對(duì)最短路徑問(wèn)題的Floyd-Warshall算法的時(shí)間復(fù)雜度是，空間復(fù)雜度是。（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】7、【單選題】給定帶權(quán)無(wú)向圖，在所有點(diǎn)對(duì)最短路徑問(wèn)題的Floyd-Warshall算法中，使用表示可從前個(gè)點(diǎn)中選點(diǎn)經(jīng)過(guò)時(shí)到的最短距離。則該算法中的遞推關(guān)系式是。本題答案：【】8、【單選題】給定帶權(quán)無(wú)向圖實(shí)例如下圖所示。使用Floyd-Warshall算法解決所有點(diǎn)對(duì)最短路徑問(wèn)題。在該實(shí)例運(yùn)行過(guò)程中，計(jì)算后的數(shù)組與數(shù)組如下圖所示。則繼續(xù)計(jì)算后,。本題答案：【】9、【單選題】相等關(guān)系是具有傳遞性的，即若,則有。給定變量集合，二元組集合描述其中一些變量的相等關(guān)系，可使用Floyd算法解決判斷任意兩變量間是否相等的問(wèn)題。給出算法偽代碼如下，則空白處應(yīng)填入____。本題答案：【】10、【單選題】給定帶權(quán)無(wú)向圖，定義無(wú)向圖的最小環(huán)為：(1)環(huán)上至少包含3個(gè)點(diǎn)（2）環(huán)上點(diǎn)不重復(fù)（3）環(huán)上所有邊的權(quán)值之和最小。可借鑒Floyd算法解決該問(wèn)題，給出偽代碼如下，空白處應(yīng)填入。本題答案：【】第12章單元測(cè)試1、【單選題】對(duì)如下所示二分圖，其最大匹配數(shù)為本題答案：【】2、【單選題】給定無(wú)向圖，如何判斷該圖是否為二分圖？可以用兩種顏色給圖上頂點(diǎn)染色，若任意相鄰頂點(diǎn)顏色均不相同，則該無(wú)向圖是二分圖。給出判斷無(wú)向圖是否為二分圖的算法偽代碼如下，空白處應(yīng)填入。本題答案：【】3、【單選題】求二分圖最大匹配問(wèn)題的匈牙利算法偽代碼如下，則空白處應(yīng)填入____本題答案：【】4、【單選題】二分圖最大匹配問(wèn)題的匈牙利算法的時(shí)間復(fù)雜度是____（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】5、【單選題】給出一個(gè)矩陣，行數(shù)與列數(shù)均為,其中每個(gè)元素都是0或1?，F(xiàn)在有兩種操作分別是交換任意兩行或交換任意兩列。請(qǐng)判斷是否可以通過(guò)任意次以上兩種操作使得矩陣主對(duì)角線(xiàn)（左上角到右下角）全部為1。觀察符合條件的矩陣，可以發(fā)現(xiàn)在此類(lèi)矩陣中，總能從每一行都挑選一個(gè)為1的元素，且這些元素都分布在不同列。可將該問(wèn)題轉(zhuǎn)換為二分圖的匹配問(wèn)題，給出算法偽代碼如下，則空白處應(yīng)填入____本題答案：【】6、【單選題】給出流網(wǎng)絡(luò)有向圖如下所示，則該流網(wǎng)絡(luò)的最小割為，該最小割的橫跨邊是。本題答案：【】7、【單選題】給出流網(wǎng)絡(luò)有向圖如下所示，將其轉(zhuǎn)換為殘存圖，則邊上空白處①②③④的值分別應(yīng)為，該流網(wǎng)絡(luò)上繼續(xù)尋找增廣路徑，下一條增廣路徑最多可增加流量。本題答案：【】8、【單選題】求最大流問(wèn)題的Ford-Fulkerson算法偽代碼如下，則空白處應(yīng)填入____本題答案：【】9、【單選題】最大流問(wèn)題的Ford-Fulkerson算法的時(shí)間復(fù)雜度是____（請(qǐng)選擇最準(zhǔn)確項(xiàng)）本題答案：【】10、【單選題】現(xiàn)有題庫(kù)包含k種類(lèi)型題目共n道，按要求從其中抽取m道題目組成試卷。已知題庫(kù)表示第道題目覆蓋類(lèi)型。組卷要求表示卷子中第種類(lèi)型題目應(yīng)有道。求符合要求的組卷方案，若不存在解則輸出“NoSolution”。該問(wèn)題可轉(zhuǎn)化為最大流問(wèn)題解決，將題目與題目類(lèi)型分別抽象為兩列點(diǎn)，左側(cè)與右側(cè)添加一源點(diǎn)和匯點(diǎn)，源點(diǎn)與題目連邊，邊權(quán)為1；題目與該題覆蓋類(lèi)型連邊，邊權(quán)為1；類(lèi)型與匯點(diǎn)連邊，邊權(quán)為該類(lèi)型題目所需數(shù)量。如下圖實(shí)例所示。給出算法偽代碼如下，空白處應(yīng)填入本題答案：【】期末考試1、【單選題】的解為_(kāi)___本題答案：【】2、【單選題】歸并排序算法中的合并操作是將2段有序序列通過(guò)不斷比較兩序列首元素大小，合并為1段有序序列。k路歸并排序與合并操作相似，給定k個(gè)有序序列，總長(zhǎng)度為n（）。用優(yōu)先隊(duì)列來(lái)維護(hù)k個(gè)有序序列的首元素，每次從優(yōu)先隊(duì)列中取出列首元素加入整體有序序列。從而將k個(gè)有序序列合并為1個(gè)長(zhǎng)度為n的有序序列。那么k路歸并排序算法的時(shí)間復(fù)雜度為本題答案：【】3、【單選題】給定n天的某支股票價(jià)格，假定第i天的價(jià)格為，為了盡可能多的賺錢(qián)，即尋找且以在第i天買(mǎi)進(jìn)股票，在第j天賣(mài)出股票，使得最大化。給出該問(wèn)題的分治部分算法偽代碼如下，則空白處應(yīng)填入本題答案：【、、，三種方案中使收益最大的方案】4、【單選題】將一個(gè)凸多邊形劃分為多個(gè)三角形，且劃分線(xiàn)不交叉，有多少種劃分方法？三角形有1種劃分方法，四邊形有2種劃分方法…該問(wèn)題是典型的卡特蘭數(shù)應(yīng)用問(wèn)題，已知卡特蘭數(shù)有如下遞推關(guān)系：給出計(jì)算的偽代碼如下，則該算法時(shí)間復(fù)雜度為(請(qǐng)選擇最準(zhǔn)確項(xiàng))本題答案：【】5、【單選題】隨機(jī)化次序選擇算法的期望時(shí)間復(fù)雜度為_(kāi)___本題答案：【】6、【單選題】動(dòng)態(tài)規(guī)劃算法中，最優(yōu)子結(jié)構(gòu)的性質(zhì)是指本題答案：【問(wèn)題的最優(yōu)解可以由子問(wèn)題的最優(yōu)解組合而成，子問(wèn)題可以獨(dú)立求解】7、【單選題】在支持插入、刪除、替換三種操作的最小編輯距離問(wèn)題中，字符串“algorithm”到字符串“altruistic”的最小編輯距離為_(kāi)___本題答案：【6】8、【單選題】在支持插入、刪除、替換三種操作的最小編輯距離問(wèn)題中，我們用表示字符串變?yōu)榈淖钚【庉嬀嚯x，則遞推式應(yīng)為_(kāi)___本題答案：【】9、【單選題】在矩陣鏈乘法問(wèn)題中，表示計(jì)算矩陣鏈所需標(biāo)量乘法的最小次數(shù)，則該問(wèn)題的遞推式為_(kāi)___本題答案：【】10、【單選題】有一串特殊的能量項(xiàng)鏈，上面有N顆能量珠。每顆能量珠上都有兩個(gè)正整數(shù)作為頭標(biāo)記和尾標(biāo)記。對(duì)于相鄰的兩顆珠子，保證前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。兩顆珠子可以聚合成一顆珠子，同時(shí)釋放出能量。如果前一顆能量珠的頭標(biāo)記為a，尾標(biāo)記為b，后一顆能量珠的頭標(biāo)記為b，尾標(biāo)記為c，則聚合后釋放的能量為，新產(chǎn)生的珠子的頭標(biāo)記為a，尾標(biāo)記為c?，F(xiàn)在我們要通過(guò)不斷聚合相鄰珠子直到項(xiàng)鏈上只剩1顆珠子來(lái)獲取能量。顯然，不同的聚合順序能獲得不同的能量。請(qǐng)你設(shè)計(jì)聚合順序使得釋放總能量最大。例如：N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3)(3，5)(5，10)(10，2)。應(yīng)先將第1顆和第4顆合并，然后再依次和第2顆、第3顆合并。可得到總能量為。則下面給出的偽代碼中空白處應(yīng)填入本題答案：【】11、【單選題】對(duì)某僅包含左右括號(hào)的字符串而言，若其中左括號(hào)和右括號(hào)可以正確的匹配，那么稱(chēng)其為均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。給定一個(gè)長(zhǎng)度為n的僅包含左右括號(hào)的字符串S，請(qǐng)求出字符串S的最長(zhǎng)均衡子序列。換言之，請(qǐng)從S中挑選出盡量多的字符按順序組成新字符串S'，使得S'是一個(gè)均衡字符串。例如，對(duì)字符串“())(()”而言，我們可以挑選其中第1，2，5，6個(gè)字符構(gòu)成一個(gè)長(zhǎng)度為4的均衡字符串“()()”。我們用表示字符串的最長(zhǎng)均衡子序列長(zhǎng)度，則其遞推式應(yīng)為_(kāi)___本題答案：【】12、【單選題】在部分背包問(wèn)題中，若背包容量為，有個(gè)物品可供選擇。每個(gè)物品價(jià)格分別為，體積分別為。則該背包可容納物品最大總價(jià)格為_(kāi)___本題答案：【42】13、【單選題】在加權(quán)活動(dòng)選擇問(wèn)題中有n個(gè)活動(dòng)組成的集合，令表示集合中不沖突活動(dòng)最大權(quán)重和，為以活動(dòng)開(kāi)始前最后結(jié)束的活動(dòng)，為活動(dòng)的權(quán)重。則遞推式為_(kāi)___本題答案：【】14、【單選題】老師布置了n個(gè)題目，每個(gè)題目都有相應(yīng)的分?jǐn)?shù)及截止日期。各個(gè)題目的分?jǐn)?shù)及截止日期可能并不相同。對(duì)某題目而言，如果在該題目的截止日期前完成則可獲得對(duì)應(yīng)的分?jǐn)?shù)，否則無(wú)法得分。假設(shè)每個(gè)題目均需要花費(fèi)一天的時(shí)間來(lái)完成，這期間無(wú)法完成其他題目。請(qǐng)你設(shè)計(jì)算法指定題目的完成計(jì)劃，從而使總的得分最大。下面給出一個(gè)包含了7個(gè)題目及相應(yīng)的分?jǐn)?shù)、截止日期的實(shí)例：題目