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