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