【MOOC期末】《算法設計與分析》(北京航空航天大學)期末測試慕課答案

【MOOC期末】《算法設計與分析》(北京航空航天大學)期末測試慕課答案算法設計與分析期末考試1.單選題：對某僅包含左右括號的字符串而言，若其中左括號和右括號可以正確的匹配，那么稱其為均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。給定一個長度為n的僅包含左右括號的字符串S，請求出字符串S的最長均衡子序列。換言之，請從S中挑選出盡量多的字符按順序組成新字符串S'，使得S'是一個均衡字符串。例如，對字符串“())(()”而言，我們可以挑選其中第1，2，5，6個字符構成一個長度為4的均衡字符串“()()”。我們用表示字符串的最長均衡子序列長度，則其遞推式應為____

選項：

A、

B、

C、

D、

答案：【】2.單選題：有一串特殊的能量項鏈，上面有N顆能量珠。每顆能量珠上都有兩個正整數作為頭標記和尾標記。對于相鄰的兩顆珠子，保證前一顆珠子的尾標記一定等于后一顆珠子的頭標記。兩顆珠子可以聚合成一顆珠子，同時釋放出能量。如果前一顆能量珠的頭標記為a，尾標記為b，后一顆能量珠的頭標記為b，尾標記為c，則聚合后釋放的能量為，新產生的珠子的頭標記為a，尾標記為c?，F在我們要通過不斷聚合相鄰珠子直到項鏈上只剩1顆珠子來獲取能量。顯然，不同的聚合順序能獲得不同的能量。請你設計聚合順序使得釋放總能量最大。例如：N=4，4顆珠子的頭標記與尾標記依次為(2，3)(3，5)(5，10)(10，2)。應先將第1顆和第4顆合并，然后再依次和第2顆、第3顆合并?？傻玫娇偰芰繛?。則下面給出的偽代碼中空白處應填入

選項：

A、

B、

C、

D、

答案：【】3.單選題：在矩陣鏈乘法問題中，表示計算矩陣鏈所需標量乘法的最小次數，則該問題的遞推式為____

選項：

A、

B、

C、

D、

答案：【】4.單選題：在支持插入、刪除、替換三種操作的最小編輯距離問題中，我們用表示字符串變?yōu)榈淖钚【庉嬀嚯x，則遞推式應為____

選項：

A、

B、

C、

D、

答案：【】5.單選題：在支持插入、刪除、替換三種操作的最小編輯距離問題中，字符串“algorithm”到字符串“altruistic”的最小編輯距離為____

選項：

A、8

B、7

C、6

D、5

答案：【6】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.單選題：隨機化次序選擇算法的期望時間復雜度為____

選項：

A、

B、

C、

D、

答案：【】8.單選題：將一個凸多邊形劃分為多個三角形，且劃分線不交叉，有多少種劃分方法？三角形有1種劃分方法，四邊形有2種劃分方法…該問題是典型的卡特蘭數應用問題，已知卡特蘭數有如下遞推關系：給出計算的偽代碼如下，則該算法時間復雜度為(請選擇最準確項)

選項：

A、

B、

C、

D、

答案：【】9.單選題：給定至少含3個點的有向圖，包含兩點點與點(與無直接連邊)。刪去圖中除兩點以外的一些點，使得與不連通。則最少刪去幾個點？盡管該問題是通過刪點操作使得圖不連通，但與圖問題中“割”的定義仍有相似之處。我們可以通過將點拆分為邊，如下圖上部分所示。通過拆點從而將該問題轉化為最小割問題，如下圖下部分所示。則轉化后，邊的容量應設置為，其余邊的容量應設置為

選項：

A、

B、

C、

D、

答案：【】10.單選題：相等關系具有傳遞性，類似的，大于關系（小于關系）也具有傳遞關系：若有則。給定不等式集合包括個變量，個不等式，每個不等式形式為或。判斷這個不等式是否有矛盾。給出算法偽代碼如下，則空白處應填入

選項：

A、

B、

C、

D、

答案：【】11.單選題：圖是有向無環(huán)圖。s和t是圖G上的兩個頂點。現在設計一個算法來計數從s到t的不同路徑個數。如下圖示例，從s到t共有6條不同路徑。給出算法偽代碼如下，其中空白處應填入

選項：

A、

B、

C、

D、

答案：【】12.單選題：無向連通圖,每條邊的權值均為非負數。為圖的一個最小生成樹。現在向圖中添加一條新的邊，其權值為?，F在設計一個算法測試是否仍為新得到的圖的最小生成樹，若仍是新圖的最小生成樹則返回，否則返回。算法偽代碼如下所示。則空白處應填入

選項：

A、

B、

C、

D、

答案：【】13.單選題：老師布置了n個題目，每個題目都有相應的分數及截止日期。各個題目的分數及截止日期可能并不相同。對某題目而言，如果在該題目的截止日期前完成則可獲得對應的分數，否則無法得分。假設每個題目均需要花費一天的時間來完成，這期間無法完成其他題目。請你設計算法指定題目的完成計劃，從而使總的得分最大。下面給出一個包含了7個題目及相應的分數、截止日期的實例：題目1234567截止日期（天）1133224分數6721451對該實例而言，得分最大的作業(yè)完成方案為花費4天時間依次完成題目2,6,3,7。得分為15。對該問題應選擇如下哪個貪心策略

選項：

A、對題目按截止日期升序考慮，同一截止日期優(yōu)先安排高分題目。

B、對題目按截止日期降序考慮，同一截止日期優(yōu)先安排高分題目。

C、對題目按照分數升序考慮，同一分數優(yōu)先安排早截止題目。

D、對題目按照分數降序考慮，同一分數題目無需考慮截止日期。

答案：【對題目按照分數降序考慮，同一分數題目無需考慮截止日期?！?4.單選題：在加權活動選擇問題中有n個活動組成的集合，令表示集合中不沖突活動最大權重和，為以活動開始前最后結束的活動，為活動的權重。則遞推式為____

選項：

A、

B、

C、

D、

答案：【】15.單選題：在部分背包問題中，若背包容量為，有個物品可供選擇。每個物品價格分別為，體積分別為。則該背包可容納物品最大總價格為____

選項：

A、36

B、39

C、42

D、45

答案：【42】16.單選題：給定n天的某支股票價格，假定第i天的價格為，為了盡可能多的賺錢，即尋找且以在第i天買進股票，在第j天賣出股票，使得最大化。給出該問題的分治部分算法偽代碼如下，則空白處應填入

選項：

A、、、，三種方案中使收益最大的方案

B、、、，三種方案中使收益最大的方案

C、、、，三種方案中使收益最大的方案

D、、、，三種方案中使收益最大的方案

答案：【、、，三種方案中使收益最大的方案】17.單選題：歸并排序算法中的合并操作是將2段有序序列通過不斷比較兩序列首元素大小，合并為1段有序序列。k路歸并排序與合并操作相似，給定k個有序序列，總長度為n（）。用優(yōu)先隊列來維護k個有序序列的首元素，每次從優(yōu)先隊列中取出列首元素加入整體有序序列。從而將k個有序序列合并為1個長度為n的有序序列。那么k路歸并排序算法的時間復雜度為

選項：

A、

B、

C、

D、

答案：【】18.單選題：的解為____

選項：

A、

B、

C、

D、

答案：【】19.多選題：下列無向圖一定是樹的有（多選）

選項：

A、有n個頂點，n-1條邊的圖。

B、無回路的連通圖。

C、連通但刪去任意一條邊則不連通的圖。

D、每對頂點間都連通的圖。

答案：【無回路的連通圖。;連通但刪去任意一條邊則不連通的圖?！?0.多選題：函數用記號可表示為______

選項：

A、

B、

C、

D、

答案：【;;】21.單選題：圖為無向連通圖，則有。

選項：

A、正確

B、錯誤

答案：【正確】22.單選題：貪心算法一定能求得問題的全局最優(yōu)解。

選項：

A、正確

B、錯誤

答案：【錯誤】23.單選題：分治算法將問題劃分為子問題，劃分子問題個數越多則時間復雜度一定越低。

選項：

A、正確

B、錯誤

答案：【錯誤】24.單選題：二分圖中不存在長度為奇數的環(huán)。

選項：

A、正確

B、錯誤

答案：【正確】25.單選題：統(tǒng)一機器性能后，算法運行時間僅依賴于問題輸入規(guī)模。

選項：

A、正確

B、錯誤

答案：【錯誤】26.遞歸式的解為

答案：【n】27.已知無向圖有10條邊，有4個頂點度數為3，其余頂點度數不超過2。則該圖至少有個頂點

答案：【8】28.給出a,b,c,d,e共5個字符，其出現頻數(千次)分別為[40,13,12,8,9]。按照課程中所講左0右1，左小右大的規(guī)則建