【MOOC】算法初步-北京大學(xué) 中國(guó)大學(xué)慕課MOOC答案

【MOOC】算法初步-北京大學(xué)中國(guó)大學(xué)慕課MOOC答案1.5單元測(cè)驗(yàn)1、【單選題】本節(jié)反復(fù)用的一個(gè)例子是用無(wú)刻度桶的量水問(wèn)題?，F(xiàn)在還是假設(shè)有A（7升）、B（5升）兩個(gè)桶。有人給出了一個(gè)算法，請(qǐng)問(wèn)它的執(zhí)行將導(dǎo)致的結(jié)果。本題答案：【A=3,B=0】2、【單選題】許多人小時(shí)候都做過(guò)“農(nóng)夫，狼、羊和白菜”過(guò)河的智力題。這里就假設(shè)大家都是知道規(guī)則的?，F(xiàn)在我們虛構(gòu)一個(gè)農(nóng)夫和5樣動(dòng)物（稱它們?yōu)锳，B，C，D，E）過(guò)河的題目。假設(shè)沒(méi)農(nóng)夫在場(chǎng)的時(shí)候，A要吃B，B要吃C，C要吃D，D要吃E；沒(méi)有其他吃的關(guān)系了。同時(shí)還假設(shè)那條船上除了農(nóng)夫外，還可以容納最多2個(gè)動(dòng)物。有人設(shè)計(jì)了一個(gè)讓它們過(guò)河的算法如下：此題有三問(wèn)：（1）這個(gè)算法是否成功地將它們都帶過(guò)河了？（2）如果那條小船除農(nóng)夫外，最多還只能容納1個(gè)動(dòng)物，有可能設(shè)計(jì)一個(gè)成功的算法嗎？（3）假設(shè)小船除農(nóng)夫外，最多還可以容納2個(gè)動(dòng)物，但總共有6個(gè)動(dòng)物（還是那種鏈?zhǔn)匠躁P(guān)系），有可能設(shè)計(jì)一個(gè)成功的算法嗎？本題答案：【（1）是（2）不可能（3）不可能】3、【單選題】變量及其賦值，是討論計(jì)算機(jī)算法和程序的一個(gè)最基本的概念。在算法描述的表達(dá)中，有時(shí)用箭頭，例如x1，表示讓變量x的值為1，而xx+1則表示將x的當(dāng)前值加上1后再放到x中。很多時(shí)候，人們也用等號(hào)（=），例如x=1，x=x+1，分別與x1，xx+1是相同的意思。也就是說(shuō)，這里的等號(hào)不同于數(shù)學(xué)中的等號(hào)。算法描述中為了表示數(shù)學(xué)意義上的“相等”，則常常用符號(hào)“==”，不相等就用“!=”。這些描述算法操作的符號(hào)對(duì)于初學(xué)者，剛開(kāi)始可能會(huì)有些困惑，習(xí)慣就好了?？紤]下面的算法，該算法執(zhí)行輸出的前3個(gè)數(shù)為:本題答案：【10，5，16】4、【單選題】在上一題中的第2條語(yǔ)句，寫起來(lái)比較啰嗦，常常用所謂“while循環(huán)”來(lái)表示。第3條語(yǔ)句，則用所謂條件語(yǔ)句“ifthenelse”來(lái)表示。于是，上面的算法也可以描述為：現(xiàn)在的問(wèn)題是，一共會(huì)輸出幾個(gè)數(shù)，該算法就結(jié)束了。也就是問(wèn)循環(huán)執(zhí)行的次數(shù)。本題答案：【7個(gè)】5、【單選題】根據(jù)算法的描述，估計(jì)某些語(yǔ)句（操作）的執(zhí)行次數(shù)，是算法效率分析的要求，其中主要是對(duì)循環(huán)結(jié)構(gòu)的理解。分析下面這個(gè)三重循環(huán)構(gòu)成的算法，指出其中語(yǔ)句4的執(zhí)行次數(shù)。做完了這一題，你一定也能按序列出其中print語(yǔ)句輸出的所有三元組了。本題答案：【10次】6、【單選題】除了準(zhǔn)確數(shù)出語(yǔ)句的執(zhí)行次數(shù)，在算法學(xué)習(xí)和應(yīng)用中更多的是采用所謂“大O記法”來(lái)大致估計(jì)算法的效率（復(fù)雜性）。對(duì)于下面的算法進(jìn)行分析：（1）指出正確的“大O記法”；（2）設(shè)n=3，算法結(jié)束時(shí)x和y那一個(gè)較大。本題答案：【O(n^3)，xy】7、【單選題】在講到算法類型的時(shí)候，我們提到一種區(qū)別的維度是“數(shù)值計(jì)算”和“非數(shù)值計(jì)算”。數(shù)值計(jì)算通常體現(xiàn)出“迭代收斂”的特征。例如下面的算法（牛頓法求的根）就是一個(gè)典型的樣式。設(shè)x=5，e=0.01，問(wèn)該算法循環(huán)將會(huì)執(zhí)行多少次（提示：可編程或用excel驗(yàn)證）。本題答案：【在5次和10次之間】8、【多選題】我們回到前面的第5題。那題看起來(lái)沒(méi)什么實(shí)際意義，但基于對(duì)它的理解，可以很容易構(gòu)造一個(gè)解“真問(wèn)題”的算法：求哪些整數(shù)（三元組，a,b,c）滿足勾股定律。我們知道a=3，b=4和c=5是滿足的?，F(xiàn)在的問(wèn)題就是，給定一個(gè)上限n，有哪些小于n的整數(shù)a，b和c會(huì)滿足勾股定理呢？要求是，如果有的話，一個(gè)也不能漏。稍微想一下，可知滿足等式的a、b和c中不可能有相等的，因而總有個(gè)大小順序，設(shè)a最小，c最大，這樣就等價(jià)于我們要求0abcn，滿足。對(duì)前面第5題的算法稍作修改（將其循環(huán)體中的簡(jiǎn)單輸出改成一個(gè)條件輸出），就有了下面這個(gè)很實(shí)用的求直角三角形整數(shù)勾股弦的算法：現(xiàn)在關(guān)心算法中的第5句會(huì)被執(zhí)行的次數(shù)（盡管不一定每次都有輸出）。顯然這是一個(gè)與n有關(guān)的量。下面哪一種或幾種說(shuō)法是正確的。本題答案：【(n-1)*(n-2)*(n-3)/6次#O(n^3)】2.4單元測(cè)驗(yàn)1、【單選題】利用歐幾里得擴(kuò)展式中系數(shù)的關(guān)系式：，，（其中q為當(dāng)前a除以b取整，設(shè)ab），試用手工計(jì)算求解整數(shù)34和21擴(kuò)展式中系數(shù)的回推過(guò)程。采用輾轉(zhuǎn)相除計(jì)算gcd(34,21)，當(dāng)余數(shù)為0時(shí)，取，，利用上述關(guān)系式，可得，。試計(jì)算。本題答案：【x4=2，y4=-3】2、【單選題】設(shè)a、b為兩個(gè)正整數(shù)，整數(shù)x0、y0滿足a*x0+b*y0=gcd(a,b)，即x0、y0是（a,b）歐幾里得擴(kuò)展式的一組解。對(duì)于以下關(guān)于求解滿足a*x+b*y=gcd(a,b)，x、y通解的描述，請(qǐng)選擇正確的選項(xiàng)，k為整數(shù)。本題答案：【x=x0-(b/gcd(a,b))*k，y=y0+(a/gcd(a,b))*k】3、【多選題】設(shè)a、b為兩個(gè)正整數(shù)，且ab,請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【若a、b均為偶數(shù)，則gcd(a，b)=2gcd(a/2，b/2)#若a為偶數(shù)，b為奇數(shù)，則gcd(a，b)=gcd(a/2，b)#gcd(a，b)=gcd(a-b,b)#gcd(a，b)=gcd(a-b,a)】4、【多選題】?jī)蓚€(gè)整數(shù)a，b分別為55，34，采用擴(kuò)展歐幾里得算法得出一組解（x，y）為（13，-21），滿足等式ax+by=gcd(a,b)。請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【13是滿足ax+by=gcd(a,b)，x絕對(duì)值最小的整數(shù)#21是滿足ax+by=gcd(a,b)，y絕對(duì)值最小的整數(shù)】5、【多選題】設(shè)a、b為兩個(gè)正整數(shù)，請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【gcd(a/m,b/m)=gcd(a，b)/m，其中，m為整數(shù)，且能被a、b整除#lcm(a,b)=a*b/gcd(a,b),（lcm(a,b)為a和b的最小公倍數(shù)）#gcd(ab,m)=gcd(a,m)*gcd(b,m)，m為整數(shù)】6、【多選題】可以采用蠻力法（枚舉法）求滿足ax+by=d的整數(shù)x和y，設(shè)a、b為正整數(shù)。先用歐幾里德算法求出d=gcd(a,b)，然后按下表所示的方法，x從1開(kāi)始，逐步嘗試y=-1、-2、......，每次y絕對(duì)值增1，計(jì)算ax+by，若ax+byd，則x+1，y不變，繼續(xù)按上述方法改變y值并計(jì)算ax+by，直到最終滿足ax+by=d，得到一組滿足擴(kuò)展式的x和y。請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【此方法得到的x，y值不一定是所有滿足擴(kuò)展式中絕對(duì)值最小的#采用這個(gè)蠻力法計(jì)算a=7，b=5，得到的x、y值為3、-4】3.3單元測(cè)驗(yàn)1、【單選題】有序列表list如下圖所示，含10個(gè)元素。用如下二分法搜索算法搜索目標(biāo)對(duì)象（1）x=15，（2）x=45。設(shè)變量low、high初值為0、9。以下選項(xiàng)是算法結(jié)束時(shí)變量low、high的值，請(qǐng)選擇正確的選項(xiàng)。本題答案：【（1）low=5，high=4；（2）low=10，high=9】2、【單選題】采用習(xí)題1所述的二分搜索算法在一個(gè)有序列表中搜索目標(biāo)對(duì)象x，如果查找成功就返回對(duì)應(yīng)的序號(hào)。如果沒(méi)有找到該目標(biāo)對(duì)象，就把x插入到列表中，使得結(jié)果仍保持有序(假設(shè)序列中沒(méi)有重復(fù)數(shù)據(jù))。當(dāng)x不在列表中，打破循環(huán)條件時(shí)，對(duì)應(yīng)邊界值仍保存在low、mid、high變量中，應(yīng)該將x插入到什么位置（忽略越界問(wèn)題）？本題答案：【x應(yīng)該插入到結(jié)束循環(huán)時(shí)low值所指的位置】3、【單選題】采用二分法求解方程F(x)=0的一個(gè)實(shí)根，有時(shí)很難快速獲得滿足F(a)*F(b)0的兩個(gè)端點(diǎn)(a,b)。如果函數(shù)F(x)能寫成兩個(gè)簡(jiǎn)單函數(shù)差的形式，F(xiàn)(x)=f(x)-g(x)，例如，求方程：的解，，，一種求端點(diǎn)(a,b)的方法是畫出f(x)、g(x)的函數(shù)圖，兩條曲線相交的點(diǎn)即為方程F(x)=0的解。在圖中找到這些相交的點(diǎn)，就可以估測(cè)出對(duì)應(yīng)相交點(diǎn)兩側(cè)的端點(diǎn)。利用這個(gè)方法估測(cè)方程實(shí)數(shù)根的兩個(gè)端點(diǎn)a和b，選擇以下選項(xiàng)中與實(shí)根最接近的區(qū)間。本題答案：【[3.5，4]】4、【多選題】假設(shè)有序列表中可能會(huì)有某些重復(fù)的元素，要求采用二分搜索查找目標(biāo)對(duì)象時(shí)，找到后能定位到重復(fù)元素的第一個(gè)。以下給出了（a）、（b）、（c）、（d）四個(gè)算法（循環(huán)體外部分省略），希望在while循環(huán)結(jié)束時(shí)，若列表中包含搜索對(duì)象x，low值指向與x匹配的第一個(gè)元素。請(qǐng)選擇正確的選項(xiàng)。本題答案：【(a)滿足要求#（c）滿足要求】4.4單元測(cè)驗(yàn)1、【單選題】假設(shè)5個(gè)符號(hào)出現(xiàn)的頻次分別為：12，13，20，25，30，下圖是對(duì)應(yīng)這5個(gè)符號(hào)產(chǎn)生編碼樹(shù)，根據(jù)哈夫曼編碼算法回答哪棵是最優(yōu)編碼樹(shù)。（方便起見(jiàn)，節(jié)點(diǎn)中直接標(biāo)注了對(duì)應(yīng)的頻次）本題答案：【（b）、（d）是最優(yōu)編碼樹(shù)】2、【多選題】某信源有8種符號(hào)X={A1,A2,A3,A4,A5,A6,A7,A8}，在數(shù)據(jù)中出現(xiàn)的概率為P=(0.28,0.18,0.17,0.11,0.10,0.08,0.06,0.02)，請(qǐng)構(gòu)建哈夫曼編碼樹(shù)，并選擇以下正確的選項(xiàng)。本題答案：【碼位均值為2.78#得到的哈夫曼編碼，2個(gè)2位碼，3個(gè)3位碼，1個(gè)4位碼，2個(gè)5位碼】3、【多選題】關(guān)于哈夫曼編碼算法，請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【哈夫曼編碼算法得到的編碼樹(shù)是一個(gè)最優(yōu)編碼樹(shù)#哈夫曼編碼樹(shù)一定是一棵滿二叉樹(shù)（除葉節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)）】4、【多選題】下圖（a）是本節(jié)給出的哈夫曼編碼樹(shù)算法，樹(shù)節(jié)點(diǎn)可以采用二維數(shù)組node[][]描述，設(shè)需要為s0~s4共計(jì)5個(gè)字符編碼，其對(duì)應(yīng)的出現(xiàn)頻次分別為1，3，4，5，7。節(jié)點(diǎn)node[i][j]，i表示節(jié)點(diǎn)ID，j對(duì)應(yīng)節(jié)點(diǎn)的不同屬性，依次為對(duì)應(yīng)的符號(hào)，頻率，左右子節(jié)點(diǎn)，用“-1”表示對(duì)應(yīng)的屬性為空。運(yùn)行算法1~3行后，形成葉節(jié)點(diǎn)如下圖（b）所示，繼續(xù)運(yùn)行算法構(gòu)建哈夫曼樹(shù)中其他節(jié)點(diǎn)，選擇以下正確的選項(xiàng)。本題答案：【算法結(jié)束時(shí)，node[5][:]=[-1,4,0,1]#算法結(jié)束時(shí)，node[8][:]=[-1,20,6,7]】5、【填空題】一棵哈夫曼樹(shù)有59個(gè)節(jié)點(diǎn)，則其葉子節(jié)點(diǎn)的個(gè)數(shù)是幾個(gè)？本題答案：【30】5.4單元測(cè)驗(yàn)1、【單選題】本課程中談到的“圖”是由一些節(jié)點(diǎn)和邊構(gòu)成結(jié)構(gòu)。若一個(gè)圖有n個(gè)節(jié)點(diǎn)，每?jī)蓚€(gè)節(jié)點(diǎn)之間最多有1條邊，那么它最多有多少條邊？本題答案：【n(n-1)/2】2、【單選題】“連通圖”是一類很重要的圖。它的直觀含義是從任何一個(gè)節(jié)點(diǎn)都可以經(jīng)由邊到達(dá)任何一個(gè)其他節(jié)點(diǎn)。若一個(gè)連通圖有n個(gè)節(jié)點(diǎn)，那么它最少有多少條邊？（有最少邊數(shù)的連通圖有個(gè)“昵稱”——“樹(shù)”）。本題答案：【n-1】3、【單選題】下圖是一個(gè)連通圖（4個(gè)節(jié)點(diǎn)，5條邊），可以通過(guò)刪去若干條邊留下一棵樹(shù)（這樣的樹(shù)稱為原圖的“生成樹(shù)”）。此題兩問(wèn)。（1）你認(rèn)為從中需要?jiǎng)h除多少條邊才能留下一棵生成樹(shù)？（2）一共有多少種可能的刪法？本題答案：【（1）2條；（2）8種可能】4、【單選題】“最小生成樹(shù)”是針對(duì)加權(quán)連通圖而言的。下面是一個(gè)加權(quán)圖（最左邊）和它的幾個(gè)生成樹(shù)（每條邊附近的數(shù)字為權(quán)值）。哪個(gè)（哪些）是最小生成樹(shù)呢？本題答案：【圖（4）】5、【單選題】考慮一個(gè)加權(quán)圖有5個(gè)節(jié)點(diǎn)（a,b,c,d,e）和8條邊（見(jiàn)下表）。按照本節(jié)課介紹的算法，應(yīng)該是涉及到節(jié)點(diǎn)d和e的(d,e)邊被選中，然后以此為基礎(chǔ)一條條選后續(xù)的邊，每一條邊將帶來(lái)一個(gè)新節(jié)點(diǎn)，形象上看就是一棵樹(shù)慢慢長(zhǎng)出來(lái)，最后包括了所有節(jié)點(diǎn)。試給出節(jié)點(diǎn)“長(zhǎng)出來(lái)”的順序。本題答案：【d,e,c,b,a】6、【單選題】在本課介紹的最小生成樹(shù)算法中，每次為了決定選哪條邊，都要把邊集合看一遍。如果一個(gè)圖有m條邊，相當(dāng)于每次都要做m次判斷“是這條邊嗎？”。為了減少這種判斷的次數(shù)，提高算法的效率，將圖的邊按照權(quán)值大小順序排列是一個(gè)辦法（假設(shè)不考慮順序的產(chǎn)生）。以前面一題的圖為例，將它的邊集以兩種方式（數(shù)據(jù)組織方式）給出如下，（1）是隨機(jī)順序的，（2）是從小到大順序的。我們關(guān)心采用不同的數(shù)據(jù)組織方式對(duì)效率的影響。例如，對(duì)于方式（1），為了得到最開(kāi)始的邊（d,e），一共要問(wèn)8次“是這條邊嗎？”。對(duì)于方式（2），則只需要問(wèn)2次，一次是（d,e），一次是（c,d），發(fā)現(xiàn)它的權(quán)值大于（d,e）的權(quán)值，就知道不用看下面的了。此題要回答的是，在兩種方式下，分別總共問(wèn)了多少次。（假設(shè)一條邊被選取后依然留在表中，于是后面還會(huì)看到它）本題答案：【（1）32；（2）17】6.4單元測(cè)驗(yàn)1、【單選題】采用遞歸法計(jì)算Fib(6)，一共發(fā)生了幾次加法運(yùn)算？本題答案：【12次】2、【單選題】采用如下課程介紹的快速冪算法計(jì)算矩陣C的44次冪，試問(wèn)共發(fā)生了幾次矩陣相乘運(yùn)算？（忽略矩陣內(nèi)部元素的運(yùn)算）本題答案：【8次】3、【單選題】繼續(xù)第4題，下圖是基于習(xí)題4所述的思路計(jì)算其中圖（a）得到的部分結(jié)果，請(qǐng)?zhí)顚憽?？”?duì)應(yīng)的路徑值。本題答案：【dist[2,0]=8，dist[1,2]=9，dist[2,1]=8，dist[2,2]=9，dist[4,4]=18】4、【多選題】采用課程介紹的快速冪算法（如習(xí)題2所示）計(jì)算矩陣C的n次冪，算法運(yùn)行過(guò)程中用power_matrix存放矩陣C的奇數(shù)次冪，coef_matrix存放矩陣C的自乘結(jié)果，設(shè)冪次n=11，下圖給出了算法循環(huán)第1輪和第2輪后，power_matrix和coef_matrix的運(yùn)行結(jié)果，請(qǐng)給出第3輪和第4輪后，power_matrix和coef_matrix的運(yùn)行結(jié)果。（即，填寫表中紅色“？”對(duì)應(yīng)的內(nèi)容）本題答案：【第3輪后，power_matrix=,coef_matrix=#第4輪后,power_matrix=,coef_matrix=】5、【多選題】通過(guò)一個(gè)走棋子的游戲進(jìn)一步理解動(dòng)態(tài)規(guī)劃的設(shè)計(jì)思想。下圖是一個(gè)m*n的網(wǎng)格grid[m,n]，每個(gè)格子中的數(shù)字可以理解為跨越這個(gè)格子的距離，求從左上角grid[0,0]到右下角grid[m-1,n-1]距離之和最短的路徑，要求從起點(diǎn)只能向右或向下走一格。圖（a）中灰色標(biāo)記是一條路徑，總距離和為29，顯然不是最短路徑。通過(guò)每個(gè)網(wǎng)格可選路徑的關(guān)系式可用遞歸法計(jì)算grid[0,0]到右下角grid[m-1,n-1]的最短路徑，但效率會(huì)非常低。試想如果只有一行網(wǎng)格，則只含一條路徑，起點(diǎn)到每個(gè)格子的最短距離即每個(gè)格子的值累計(jì)相加，如圖（b）所示。如果有兩行網(wǎng)格，起點(diǎn)到第二行每個(gè)格子的最短距離是，同列上一行的值，或者同行前一列的值，二者中較小者加上當(dāng)前格子的值，多行網(wǎng)格路徑以此類推。計(jì)算grid[0,0]到grid[m-1,n-1]的最短路徑問(wèn)題，就是從左到右，從上到下填寫一張m*n的二維路徑表，表中的值代表起點(diǎn)到當(dāng)前格子的最短路徑，表的右下角對(duì)應(yīng)的結(jié)果就是我們要求的最短路徑。這是一個(gè)典型的動(dòng)態(tài)規(guī)劃過(guò)程?；谏鲜鏊悸?，二維數(shù)組grid[i,j]表示網(wǎng)格[i,j]的路徑值，dist[i,j]存放起點(diǎn)到每個(gè)網(wǎng)格的最短距離，對(duì)于dist[i,j]的路徑更新規(guī)則，請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【dist[0,0]=grid[0,0]#if(0im)，dist[i,0]=dist[i-1,0]+grid[i,0]#if(0imand0jn),dist[i,j]=min(dist[i-1,j],dist[i,j-1])+grid[i,j]】7.4單元測(cè)驗(yàn)1、【單選題】此題是7.1題的繼續(xù)。用相同的例子數(shù)據(jù)，我們看課上介紹的動(dòng)態(tài)規(guī)劃算法的執(zhí)行過(guò)程。這里只考慮最優(yōu)回報(bào)的計(jì)算過(guò)程，暫不考慮具體的投資組合形式。我們已經(jīng)知道，動(dòng)態(tài)規(guī)劃算法的執(zhí)行過(guò)程可以用逐項(xiàng)填一張表的過(guò)程來(lái)形象地展示。我們的例子是總投資額6萬(wàn)，要考慮在3個(gè)項(xiàng)目的分配，因此要填一個(gè)7行，3列的表，對(duì)應(yīng)下表的左邊3列（右邊3列此題用不到）。現(xiàn)在看到的是大多數(shù)表項(xiàng)已經(jīng)有的結(jié)果。試按照算法流程，給出所標(biāo)識(shí)的F1(1)，F(xiàn)2(3)和F3(5)的值，其中Fi(x)是在前i個(gè)項(xiàng)目上投資x可以獲得的最大回報(bào)。（提示：采用上題給出的三個(gè)項(xiàng)目的回報(bào)函數(shù)，結(jié)合表中已有部分?jǐn)?shù)據(jù)計(jì)算）本題答案：【2，7，11】2、【單選題】這一題是7.2題的繼續(xù)。設(shè)想在決定投資方案前臨時(shí)增加了第4個(gè)項(xiàng)目，它的回報(bào)函數(shù)是f4(x)=2*x。于是你在前面算的基礎(chǔ)上繼續(xù)計(jì)算第4列的數(shù)據(jù)（也就是對(duì)應(yīng)F4()的數(shù)據(jù)）就可以了。試給出F4(2)，F(xiàn)4(4)和F4(6)。本題答案：【F4(2)=5；F4(4)=9；F4(6)=13】3、【單選題】這一題是7.3題的繼續(xù)。要考慮具體的投資組合了。下面給出的是一張?zhí)詈玫臄U(kuò)充后的表，包括了xi，第i個(gè)項(xiàng)目在對(duì)應(yīng)Fi()時(shí)的投入。試給出該表數(shù)據(jù)對(duì)應(yīng)的最優(yōu)投資組合。（注：在確定Fi()的時(shí)候，可能有多種符合的情況，給出的xi只是代表其中一種。也就是說(shuō)，實(shí)現(xiàn)最大總回報(bào)的最優(yōu)投資組合可能有多種，但從這樣的表中只會(huì)得到其中一種。）本題答案：【x1=1，x2=2，x3=2，x4=1】4、【多選題】?jī)?yōu)化投資組合問(wèn)題一般來(lái)說(shuō)是很復(fù)雜的，本課中介紹的是一個(gè)相對(duì)簡(jiǎn)化的版本。此題在于對(duì)這種版本投資組合問(wèn)題的理解。設(shè)想你有6萬(wàn)元，要在3個(gè)項(xiàng)目上做投資安排。三個(gè)項(xiàng)目的投資回報(bào)函數(shù)如下表所示。試目測(cè)判斷下列給出的哪些是最佳投資組合。本題答案：【在項(xiàng)目1上投2，在項(xiàng)目2上投2，在項(xiàng)目3上投2#在項(xiàng)目1上投1，在項(xiàng)目2上投2，在項(xiàng)目3上投3】8.5單元測(cè)驗(yàn)1、【單選題】下圖是一個(gè)4節(jié)點(diǎn)的有向圖，利用Floyd多源最短路徑算法依次經(jīng)過(guò)節(jié)點(diǎn)A、B、C、D中轉(zhuǎn)后，得到最短路徑矩陣。編程實(shí)現(xiàn)多源最短路徑算法，并列出A-D、B-D的路徑值在經(jīng)過(guò)中轉(zhuǎn)點(diǎn)A、B、C、D后的更新值。本題答案：【A-D的更新過(guò)程：-10-9-9，B-D的更新過(guò)程過(guò)程：9-9-8-8】2、【多選題】下圖是一個(gè)7節(jié)點(diǎn)連通圖，權(quán)值如圖所示。嘗試?yán)肈ijkstra算法思路手工計(jì)算源點(diǎn)A到其他點(diǎn)的最短路徑，并選擇以下正確的選項(xiàng)。本題答案：【當(dāng)節(jié)點(diǎn)集S={A,C,F,B}，時(shí)，下一個(gè)進(jìn)入S的節(jié)點(diǎn)是E#A-G最短路徑的前驅(qū)節(jié)點(diǎn)是D】3、【多選題】下圖是采用課程介紹的多源路徑算法得到最短路徑前驅(qū)點(diǎn)矩陣，利用該矩陣選擇如下正確的最短路徑。本題答案：【A-B的最短路徑是，A-C-B#E-C的最短路徑是，E-D-B-C#E-D的最短路徑是，E直接連接到D】4、【多選題】下圖中，i-j的路徑是經(jīng)過(guò)單源路徑算法（Dijkstra）或多源路徑算法（Floyd）得到的最短路徑，中間節(jié)點(diǎn)包含節(jié)點(diǎn)v1，v2，…vk。對(duì)于單源路徑算法，i表示源點(diǎn)（s），對(duì)于多源路徑算法，i可以是任意節(jié)點(diǎn)。請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【采用Floyd算法，能保證點(diǎn)i-j間的中間節(jié)點(diǎn)v1，v2，…vk，包括i，j中任意節(jié)點(diǎn)對(duì)之間都是最短路徑#采用Dijkstra算法，能保證源點(diǎn)i-j間的中間節(jié)點(diǎn)v1，v2，…vk，包括i，j中任意節(jié)點(diǎn)對(duì)之間都是最短路徑】5、【多選題】繼續(xù)采用題4的題干和圖示。選擇以下正確的選項(xiàng)。本題答案：【采用Floyd算法，i-j路徑中所有相鄰節(jié)點(diǎn)之間一定都是直接連接的，即i-v1，v1-v2，……vk-j都是直接連接#采用Dijkstra算法，i-j路徑中所有相鄰節(jié)點(diǎn)之間一定都是直接連接的，即i-v1，v1-v2，……vk-j都是直接連接】9.4單元測(cè)驗(yàn)1、【多選題】“聚類”，也是一個(gè)日常生活中的用語(yǔ)，在交談中用它，人們基本也知道是什么意思。但在討論算法的語(yǔ)境下（或者說(shuō)作為一個(gè)技術(shù)專用術(shù)語(yǔ)），它有特定的含義。下面這些陳述句中所體現(xiàn)的情況是否屬于“聚類”的范疇？試在算法的背景下指出哪些不屬于聚類的范疇。本題答案：【如果把人們的受教育程度分為“受過(guò)高等教育”和“沒(méi)有受過(guò)高等教育”兩類，張三剛從大學(xué)畢業(yè)了，因此他應(yīng)該屬于“受過(guò)高等教育”類別的。#幼兒園舉辦親子活動(dòng)，午餐的時(shí)候，為了便于交流，特意安排家長(zhǎng)們聚在一起，小朋友們聚在一起。#產(chǎn)品經(jīng)過(guò)自動(dòng)檢測(cè)的流水線，就被分成了次品和正品兩類?！?、【多選題】課上我們以城市群建設(shè)問(wèn)題為背景，學(xué)習(xí)了層次聚類法。我們知道了，層次聚類法的一個(gè)核心問(wèn)題是在合并兩個(gè)類的時(shí)候，如何確定合并成的新類與其他類的距離。課上用的是“較大值”。這一題我們還是用課上的例子（數(shù)據(jù)稍微有點(diǎn)修改），見(jiàn)下圖左?？紤]用“平均值”作為確定距離的依據(jù)，也就是說(shuō)，當(dāng)兩個(gè)類合并的時(shí)候，它們形成的新類與其他類的距離等于合并前它們兩個(gè)距離的均值。下圖右是經(jīng)過(guò)了一次合并的結(jié)果，6個(gè)類變成了5個(gè)類。請(qǐng)理解其中新類“南京合肥”與其他類的距離。試?yán)^續(xù)做兩次合并，達(dá)到3個(gè)類。下列說(shuō)法哪些是正確的。本題答案：【在結(jié)果的3個(gè)類中，上海與南京合肥屬于同一類#在結(jié)果的3個(gè)類中，上海與杭州屬于同一類】3、【多選題】此題考慮K-means聚類方法。類似于課程中的例子，假設(shè)有如下16個(gè)數(shù)據(jù)點(diǎn)：1,2,5,11,15,18,19,21,25,27,29,32,33,37,40,57。要聚成3類（從左到右，分別稱為第一類，第二類，第三類），初始中心為10，20，30。試根據(jù)算法流程完成聚類。根據(jù)你的聚類結(jié)果，下面哪些說(shuō)法是正確的。本題答案：【根據(jù)初始中心，最開(kāi)始1,2,5,11,15同屬第一類，但后來(lái)15屬于第二類了#聚類結(jié)束時(shí)，第二類最大，有7個(gè)數(shù)#聚類結(jié)束時(shí)，第三類的中心大于35】4、【多選題】本節(jié)課最后我們特別介紹了如何將層次聚類和K-means聚類結(jié)合起來(lái)，優(yōu)勢(shì)互補(bǔ)的問(wèn)題。下面哪些說(shuō)法是合適的。本題答案：【層次聚類的效率低，K-means聚類的質(zhì)量和效率都和初始中心的選取很有關(guān)系#結(jié)合的方式是先在少部分?jǐn)?shù)據(jù)上運(yùn)行層次聚類，為后續(xù)K-means聚類產(chǎn)生較好的初始中心#結(jié)合的方式是先在少部分?jǐn)?shù)據(jù)上運(yùn)行層次聚類，為后續(xù)K-means聚類產(chǎn)生較好的初始中心】10.3單元測(cè)驗(yàn)1、【單選題】假設(shè)一門課將一部分內(nèi)容安排成了線上內(nèi)容，包括課程相關(guān)的視頻和集中討論兩部分。對(duì)于線上內(nèi)容學(xué)生可以自愿選擇是否參加，不影響總成績(jī)。學(xué)期結(jié)束時(shí)，老師希望對(duì)學(xué)生在線上的學(xué)習(xí)情況用KNN進(jìn)行分析，老師能夠統(tǒng)計(jì)到每個(gè)學(xué)生線上收看視頻的時(shí)間，以及參與集中討論的時(shí)間?，F(xiàn)在老師希望做兩個(gè)分類工作：（1）根據(jù)學(xué)生看視頻和參與討論的時(shí)間，將學(xué)生分成“自主學(xué)習(xí)型”（看視頻較多）和“集中學(xué)習(xí)型”（參與討論較多）兩類。（2）根據(jù)學(xué)生參與線上內(nèi)容的程度，將學(xué)生分成“課堂學(xué)習(xí)型”和“課堂+線上學(xué)習(xí)型”。試問(wèn)對(duì)于上述兩個(gè)分類工作，如果考慮歐式距離和余弦相似度，應(yīng)該選擇哪種距離函數(shù)比較合適？本題答案：【（1）選擇余弦相似度，（2）選歐式距離】2、【多選題】采用KNN分類，表中列出了與被測(cè)對(duì)象距離最近的5個(gè)結(jié)果，采用歐式距離，有2個(gè)類別“0”、“1”。請(qǐng)選擇以下正確的選項(xiàng)。本題答案：【采用多數(shù)表決法，K=3時(shí)，結(jié)果為“0”類，K=5時(shí)為“1”類#用加權(quán)多數(shù)表決法，直接用距離倒數(shù)作為權(quán)值。K=3和K=5時(shí)，結(jié)果均為“0”類】3、【多選題】如下圖所示，樣本中有三個(gè)類別C1、C2、C3，采用KNN分類算法，圖中給出了被測(cè)數(shù)據(jù)對(duì)象X和Y在特征空間中的映射點(diǎn)，以X、Y為中心的圓表示對(duì)應(yīng)K個(gè)與X、Y最相近點(diǎn)的分布情況。依據(jù)KNN的多數(shù)表決規(guī)則，X歸為C3類，Y歸為C2類，但感覺(jué)這個(gè)分類結(jié)果與圖示有些偏差，直觀上X和Y都比較接近C1。你覺(jué)得可以采取哪些措施來(lái)改進(jìn)算法以避免這種情況發(fā)生？本題答案：【Y的分類問(wèn)題可能是由于樣本數(shù)不平衡造成，可以考慮壓縮C2類別的樣本數(shù)量#Y的問(wèn)題可以考慮用加權(quán)多數(shù)表決法解決#X的問(wèn)題可能是C3類含比較異常的樣本，去除異常樣本數(shù)據(jù)可以提高分類準(zhǔn)確度】4、【填空題】K近鄰算法也可以用于做回歸預(yù)測(cè)。通過(guò)某種距離度量關(guān)系找出樣本集中與被測(cè)對(duì)象最相近的K個(gè)樣本，分類任務(wù)是選擇K個(gè)樣本中占比最高的類別，來(lái)推斷被測(cè)對(duì)象的類別；回歸任務(wù)是，對(duì)K個(gè)樣本某個(gè)被關(guān)注的屬性計(jì)算均值，作為被測(cè)對(duì)象的預(yù)測(cè)值。回歸同樣可以進(jìn)行加權(quán)計(jì)算，例如，以距離的倒數(shù)為權(quán)值計(jì)算均值。以下是一個(gè)利用KNN算法預(yù)測(cè)房屋出租價(jià)格的回歸問(wèn)題，每個(gè)樣本包含一些房屋屬性（建筑面積，臥室數(shù)，洗手間數(shù)，建造年代，距公交站距離，出租價(jià)格），如下表1所示。被預(yù)測(cè)對(duì)象提供房屋屬性（建筑面積，臥室數(shù)，洗手間數(shù)，建造年代，距公交站距離）。表2是K=5時(shí)計(jì)算得到的與被預(yù)測(cè)對(duì)象距離最近的5個(gè)樣本及對(duì)應(yīng)的租價(jià)。試問(wèn)，如果用近鄰樣本租金直接取均值，被測(cè)對(duì)象的房屋租金為多少？（租金取整數(shù)）本題答案：【4880】5、【填空題】繼續(xù)上題，采用距離倒數(shù)加權(quán)計(jì)算均值，房屋租金為多少？（租金取整數(shù)）本題答案：【4907】11.4單元測(cè)驗(yàn)1、【單選題】下圖是本課開(kāi)始例子的一個(gè)簡(jiǎn)化，其中的數(shù)據(jù)表示對(duì)應(yīng)兩個(gè)城市之間的旅行花費(fèi)（比如機(jī)票價(jià)格），例如北京和上海之間是1000。本題有兩問(wèn)（1）試給出從北京出發(fā)，依次到上海、烏魯木齊、杭州、哈爾濱，返回北京所需的旅行花費(fèi)；（2）試目測(cè)給出在這5個(gè)城市之間做一次巡回推銷（即從一個(gè)城市出發(fā)，經(jīng)過(guò)其他每個(gè)城市恰好一次，返回原地）的最少花費(fèi)。（注：這里的目測(cè)給出，本質(zhì)上就是要枚舉所有可能的排列，一個(gè)個(gè)檢查對(duì)應(yīng)的代價(jià)，找出最小的。）本題答案：【（1）9400（2）5900】2、【單選題】這一題關(guān)于求解推銷員問(wèn)題的遺傳算法。講課中提到對(duì)于每一個(gè)樣本基因（即節(jié)點(diǎn)排列實(shí)例），要做三種變異（變換）操作：交換，反轉(zhuǎn)，循環(huán)。然后看變換后的結(jié)果的代價(jià)如何，留下其中優(yōu)勝的。如此循環(huán)往復(fù)多次。現(xiàn)在考慮一個(gè)排列：0,1,2,3,4,5,6,7,8,9，并假設(shè)隨機(jī)產(chǎn)生的位點(diǎn)指向2和6。試判斷下面的選項(xiàng)哪個(gè)是正確的。本題答案：【交換：0,1,6,3,4,5,2,7,8,9；反轉(zhuǎn)：0,1,6,5,4,3,2,7,8,9；循環(huán)：0,1,6,2,3,4,5,7,8,9】3、【多選題】這一課我們學(xué)了三種求解推銷員問(wèn)題的算法，蠻力法（枚舉法），遺傳算法，以及基于最小生成樹(shù)的算法。它們各有優(yōu)勢(shì)和劣勢(shì)。下述斷言中有哪些是錯(cuò)的。本題答案：【三個(gè)算法都能給出最優(yōu)解，差別在于效率#三個(gè)算法效率差不多，差別在于給出的解的質(zhì)量】4、【多選題】基于最小生成樹(shù)算法。下圖是某完全圖的一棵最小生成樹(shù)，假設(shè)該圖任何3個(gè)節(jié)點(diǎn)之間的權(quán)值關(guān)系滿足嚴(yán)格的三角不等式（即設(shè)任意兩邊之和至少比第3邊大1）。試指出在該圖上推銷員行走的代價(jià)肯定不超過(guò)120的路線。本題答案：【h,i,e,c,d,b,f,g,a,h#a,g,h,i,e,c,d,b,f,a】綜合考試1、【單選題】考慮有一袋硬幣，設(shè)其中有2分和5分的共41枚，總值為154分。人們用符號(hào)表示這些量，a=2，b=5，m=41，s=154，并基于這些量設(shè)計(jì)了一個(gè)算法如下。最后的結(jié)果n有什么意義嗎？本題答案：【錢袋中5分硬幣的個(gè)數(shù)】2、【單選題】《九章算術(shù)》是中國(guó)古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”可以用來(lái)求兩個(gè)數(shù)的最大公約數(shù)。操作過(guò)程為，1）先對(duì)兩個(gè)整數(shù)用2約簡(jiǎn)；2）以較大的數(shù)減較小的數(shù)；3）以減數(shù)和差做為新的兩個(gè)數(shù)，重復(fù)2），直到減數(shù)和差相等為止。則1）中約掉的若干個(gè)2與3）結(jié)束時(shí)的減數(shù)乘積為最大公約數(shù)。下圖給出一個(gè)對(duì)應(yīng)的算法，采用該算法求gcd(165，24)，選擇以下正確的選項(xiàng)。本題答案：【算法3~7循環(huán)14次結(jié)束，第3次循環(huán)后，a，b=93，24】3、【單選題】在有序列表list中搜索目標(biāo)元素x，list中可能有重復(fù)元素，也有可能搜索對(duì)象x不在list中。采用如下算法進(jìn)行搜索，算法結(jié)束時(shí)返回low值，請(qǐng)選擇以下關(guān)于low所指元素的描述（忽略越界問(wèn)題）。（注意：紅色“####”所標(biāo)記的代碼行與課程學(xué)習(xí)的二分搜索有所不同，注意體會(huì)其中的變化原因）本題答案：【low所指是第一個(gè)等于或者大于x的元素】4、【單選題】一個(gè)字符串含8種字符，每個(gè)字符出現(xiàn)的頻次分別為19，15，10，8，6，3，2，1。采用Huffman編碼對(duì)這8個(gè)字符進(jìn)行編碼，形成的碼串總位數(shù)是多少？碼位均值是多少？本題答案：【碼位總長(zhǎng)度為167，碼位均值為2.61】5、【單選題】按照講課中介紹的最小生成樹(shù)算法，某人在下面的加權(quán)圖上做了一次模擬執(zhí)行，給出的邊的順序?yàn)椋?a,b)，(d,e)，(b,e)，(b,c)。試考慮下面認(rèn)識(shí)的正確性。本題答案：【結(jié)果錯(cuò)誤，雖然這些邊對(duì)應(yīng)一棵最小生成樹(shù)，但順序不對(duì)】6、【單選題】在課程所介紹的投資組合算法中，如下圖所示，體現(xiàn)動(dòng)態(tài)規(guī)劃工作表的填寫是從左到右一列列進(jìn)行的。是否也可以從上到下一行行填寫呢？本題答案：【可以，只要調(diào)換講課中給出的偽代碼中第4和第5句的順序就行了】7、【多選題】設(shè)a、b是兩個(gè)大于0的整數(shù)，選擇以下關(guān)于gcd(a,b)正確的選項(xiàng)。本題答案：【設(shè)，gcd(a,b)=d，a=m·d，b=n·d，則，m、n互為質(zhì)數(shù)#設(shè)，a=k·x，b=k·y，x，y，k均為整數(shù)，則，gcd(a，b)=k·gcd(x，y)#設(shè)ab，且a，b均為奇數(shù)，則，gcd(a，b)=gcd((a+b)/2，(a-b)/2)】8、【多選題】繼續(xù)采用上題所描述的算法，選擇以下正確的選項(xiàng)。本題答案：【算法結(jié)束時(shí)，并不能確定list中是否包含x#將x插入到算法結(jié)束時(shí)low所指的位置，仍能保持list中元素的有序排列】9、【多選題】下圖是一個(gè)有n個(gè)層的三角形數(shù)字塔，第1層（頂層）1個(gè)數(shù)，第2層2個(gè)數(shù)，……，第n層n個(gè)數(shù)，這些數(shù)字可以理解為對(duì)應(yīng)的路徑消耗。從頂層開(kāi)始逐層向下走，每一步只能從當(dāng)前位置向左下或右下方移動(dòng)一層，直到到達(dá)最底層。求自頂層到底層的最短路徑，下圖（a）標(biāo)記了一條路徑，但顯然不是最短的。解答該問(wèn)題有兩個(gè)基本的方法，一是采用遞歸法自上而下逐級(jí)調(diào)用，再回推最終得到最優(yōu)解。另一種是記憶法，自下而上從最底層開(kāi)始逐層計(jì)算出每個(gè)位置向下走的最短路徑并保存結(jié)果為上一層計(jì)算使用，最終計(jì)算出最頂層位置到底層的最短路徑。以下圖（b）為例，倒數(shù)第二層數(shù)字16的位置到底層的最短路徑，取其左下（25）和右下（28）二者中較小的（25），加上自身的數(shù)字（16），就是該位置到底層的最短路徑41，這是一個(gè)動(dòng)態(tài)規(guī)劃的過(guò)程。對(duì)于這兩種算法思想，思考其對(duì)應(yīng)的算法效率。本題答案：【遞歸法（自上而下）的時(shí)間效率是2^n#記憶法（自下而上）的時(shí)間效率是n^2】10、【多選題】繼續(xù)上題。采用一個(gè)n*n的二維數(shù)組cost[][]保存上述三角形數(shù)字塔，如下圖所示。利用上述自下而上的記憶法計(jì)算每個(gè)位置的最短路徑，并保存在二維數(shù)組dist[][]中，如上題圖（b）中，cost[4][4]=16，dist[4][4]=41,則算法結(jié)束時(shí)dist[0][0]就是求得的最短路徑值?；谶@樣的數(shù)據(jù)結(jié)構(gòu)，選擇以下正確的路徑更新規(guī)則。本題答案：【第n-1行元素更新規(guī)則,dist[n-1