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