MOOC 算法初步-北京大學 中國大學慕課答案

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