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

【MOOC期末】《算法設(shè)計(jì)與分析》(北京航空航天大學(xué))期末測(cè)試慕課答案算法設(shè)計(jì)與分析期末考試1.單選題：對(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)___

選項(xiàng)：

A、

B、

C、

D、

答案：【】2.單選題：有一串特殊的能量項(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)填入

選項(xiàng)：

A、

B、

C、

D、

答案：【】3.單選題：在矩陣鏈乘法問(wèn)題中，表示計(jì)算矩陣鏈所需標(biāo)量乘法的最小次數(shù)，則該問(wèn)題的遞推式為_(kāi)___

選項(xiàng)：

A、

B、

C、

D、

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

選項(xiàng)：

A、

B、

C、

D、

答案：【】5.單選題：在支持插入、刪除、替換三種操作的最小編輯距離問(wèn)題中，字符串“algorithm”到字符串“altruistic”的最小編輯距離為_(kāi)___

選項(xiàng)：

A、8

B、7

C、6

D、5

答案：【6】6.單選題：動(dòng)態(tài)規(guī)劃算法中，最優(yōu)子結(jié)構(gòu)的性質(zhì)是指

選項(xiàng)：

A、問(wèn)題的最優(yōu)解等于子問(wèn)題的最優(yōu)解

B、問(wèn)題的最優(yōu)解可以由子問(wèn)題的最優(yōu)解組合而成，子問(wèn)題可以獨(dú)立求解

C、問(wèn)題的最優(yōu)解影響子問(wèn)題的最優(yōu)解，問(wèn)題的最優(yōu)解可以由子問(wèn)題的最優(yōu)解組合而成

D、問(wèn)題的最優(yōu)解不影響子問(wèn)題的最優(yōu)解，問(wèn)題的最優(yōu)解等于子問(wèn)題的最優(yōu)解

答案：【問(wèn)題的最優(yōu)解可以由子問(wèn)題的最優(yōu)解組合而成，子問(wèn)題可以獨(dú)立求解】7.單選題：隨機(jī)化次序選擇算法的期望時(shí)間復(fù)雜度為_(kāi)___

選項(xiàng)：

A、

B、

C、

D、

答案：【】8.單選題：將一個(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))

選項(xiàng)：

A、

B、

C、

D、

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

選項(xiàng)：

A、

B、

C、

D、

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

選項(xiàng)：

A、

B、

C、

D、

答案：【】11.單選題：圖是有向無(wú)環(huán)圖。s和t是圖G上的兩個(gè)頂點(diǎn)?，F(xiàn)在設(shè)計(jì)一個(gè)算法來(lái)計(jì)數(shù)從s到t的不同路徑個(gè)數(shù)。如下圖示例，從s到t共有6條不同路徑。給出算法偽代碼如下，其中空白處應(yīng)填入

選項(xiàng)：

A、

B、

C、

D、

答案：【】12.單選題：無(wú)向連通圖,每條邊的權(quán)值均為非負(fù)數(shù)。為圖的一個(gè)最小生成樹(shù)?，F(xiàn)在向圖中添加一條新的邊，其權(quán)值為?，F(xiàn)在設(shè)計(jì)一個(gè)算法測(cè)試是否仍為新得到的圖的最小生成樹(shù)，若仍是新圖的最小生成樹(shù)則返回，否則返回。算法偽代碼如下所示。則空白處應(yīng)填入

選項(xiàng)：

A、

B、

C、

D、

答案：【】13.單選題：老師布置了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í)例：題目1234567截止日期（天）1133224分?jǐn)?shù)6721451對(duì)該實(shí)例而言，得分最大的作業(yè)完成方案為花費(fèi)4天時(shí)間依次完成題目2,6,3,7。得分為15。對(duì)該問(wèn)題應(yīng)選擇如下哪個(gè)貪心策略

選項(xiàng)：

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

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

C、對(duì)題目按照分?jǐn)?shù)升序考慮，同一分?jǐn)?shù)優(yōu)先安排早截止題目。

D、對(duì)題目按照分?jǐn)?shù)降序考慮，同一分?jǐn)?shù)題目無(wú)需考慮截止日期。

答案：【對(duì)題目按照分?jǐn)?shù)降序考慮，同一分?jǐn)?shù)題目無(wú)需考慮截止日期?！?4.單選題：在加權(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)___

選項(xiàng)：

A、

B、

C、

D、

答案：【】15.單選題：在部分背包問(wèn)題中，若背包容量為，有個(gè)物品可供選擇。每個(gè)物品價(jià)格分別為，體積分別為。則該背包可容納物品最大總價(jià)格為_(kāi)___

選項(xiàng)：

A、36

B、39

C、42

D、45

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

選項(xiàng)：

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

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

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

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

答案：【、、，三種方案中使收益最大的方案】17.單選題：歸并排序算法中的合并操作是將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ù)雜度為

選項(xiàng)：

A、

B、

C、

D、

答案：【】18.單選題：的解為_(kāi)___

選項(xiàng)：

A、

B、

C、

D、

答案：【】19.多選題：下列無(wú)向圖一定是樹(shù)的有（多選）

選項(xiàng)：

A、有n個(gè)頂點(diǎn)，n-1條邊的圖。

B、無(wú)回路的連通圖。

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

D、每對(duì)頂點(diǎn)間都連通的圖。

答案：【無(wú)回路的連通圖。;連通但刪去任意一條邊則不連通的圖?！?0.多選題：函數(shù)用記號(hào)可表示為_(kāi)_____

選項(xiàng)：

A、

B、

C、

D、

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

選項(xiàng)：

A、正確

B、錯(cuò)誤

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

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】23.單選題：分治算法將問(wèn)題劃分為子問(wèn)題，劃分子問(wèn)題個(gè)數(shù)越多則時(shí)間復(fù)雜度一定越低。

選項(xiàng)：

A、正確

B、錯(cuò)誤

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

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】25.單選題：統(tǒng)一機(jī)器性能后，算法運(yùn)行時(shí)間僅依賴(lài)于問(wèn)題輸入規(guī)模。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】26.遞歸式的解為

答案：【n】27.已知無(wú)向圖有10條邊，有4個(gè)頂點(diǎn)度數(shù)為3，其余頂點(diǎn)度數(shù)不超過(guò)2。則該圖至少有個(gè)頂點(diǎn)

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