【MOOC】算法設(shè)計(jì)與分析-青島大學(xué) 中國大學(xué)慕課MOOC答案

【MOOC】算法設(shè)計(jì)與分析-青島大學(xué)中國大學(xué)慕課MOOC答案第一章單元測(cè)試1、【單選題】下面列出了算法的四個(gè)性質(zhì)，哪個(gè)性質(zhì)是程序不一定具備的？本題答案：【有窮性】2、【單選題】在算法設(shè)計(jì)與分析過程中，有算法設(shè)計(jì)，算法的正確性證明，算法的復(fù)雜性分析,程序設(shè)計(jì)等幾個(gè)重要步驟，下面哪種順序是正確的？本題答案：【算法設(shè)計(jì)-算法的正確性證明-算法的復(fù)雜性分析-程序設(shè)計(jì)】3、【單選題】下面哪些內(nèi)容不是算法設(shè)計(jì)之前要完成的內(nèi)容?本題答案：【使用何種計(jì)算機(jī)語言設(shè)計(jì)程序】4、【單選題】下面是快速冪算法求的代碼，這里n≥0,a是實(shí)數(shù)。對(duì)該算法的時(shí)間復(fù)雜性描述不準(zhǔn)確的是哪個(gè)？douleexp2(doublea,intn){inti;doubleb,s=1.0；i=n；b=a;while（i0）{if(i%2)s*=b；i/=2;b*=b;}returns;}本題答案：【】5、【單選題】下面哪個(gè)算法在最壞情況下的時(shí)間復(fù)雜性最低本題答案：【歸并排序】6、【單選題】有時(shí)間復(fù)雜性,時(shí)間復(fù)雜性從低到高的順序是？本題答案：【】7、【單選題】有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是?本題答案：【】8、【單選題】有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是？本題答案：【】9、【單選題】有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是？本題答案：【】10、【單選題】有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是?本題答案：【】11、【單選題】A公司處理器速度是B公司的100倍。對(duì)于復(fù)雜性為O()的算法，B公司的計(jì)算機(jī)可以在1小時(shí)內(nèi)處理規(guī)模為n的問題，A公司的計(jì)算機(jī)在1小時(shí)內(nèi)能處理的問題規(guī)模是多少？本題答案：【10n】12、【多選題】關(guān)于算法的正確性，下面哪些說法是正確的？本題答案：【若算法是正確的，則算法一定能結(jié)束（運(yùn)行時(shí)間是有限的）#若算法是正確的，則對(duì)于問題的任何實(shí)例，算法都能得到正確的結(jié)果。#對(duì)于問題的一個(gè)實(shí)例，如果算法不能獲得正確的結(jié)果，就證明算法是不正確的。】13、【判斷題】解決同一個(gè)問題的算法策略可能有多個(gè)，使用不同算法策略設(shè)計(jì)的算法，其算法時(shí)間復(fù)雜性可能有顯著差異。本題答案：【正確】14、【判斷題】學(xué)習(xí)主定理和遞歸樹等求解遞歸方程方法，主要目的是解決求遞歸算法的時(shí)間復(fù)雜性問題本題答案：【正確】15、【判斷題】自然語言、偽代碼都可以描述算法，而流程圖不能描述算法本題答案：【錯(cuò)誤】第二章單元測(cè)試1、【單選題】分治法解決問題分為三步走，即分、治、合。下面列出了幾種操作，請(qǐng)按分、治、合順序選擇正確的表述。（1）將各個(gè)子問題的解合并為原問題的解，（2）將問題分解為各自獨(dú)立的多個(gè)子問題，（3）將多個(gè)子問題合并為原問題。（4）求各個(gè)子問題的解，（5）將問題分解為可重復(fù)的多個(gè)子問題。本題答案：【(2)(4)(1)】2、【單選題】分治法的時(shí)間復(fù)雜性分析，通常是通過分析得到一個(gè)關(guān)于時(shí)間復(fù)雜性T(n)的一個(gè)遞歸方程，然后解此方程可得T(n)的結(jié)果。T(n)的遞歸定義如下：關(guān)于該定義中k，n/m,f(n)的解釋準(zhǔn)確的是本題答案：【k是子問題個(gè)數(shù)，n/m是子問題的規(guī)模，f(n)是分解為子問題的時(shí)間復(fù)雜性與合并子問題的解的時(shí)間復(fù)雜性之和】3、【單選題】已知斐波那契數(shù)列中第n個(gè)斐波那契數(shù)F(n)=F(n-1)+F(n-2),問能不能使用分治策略求第n個(gè)斐波那契數(shù)，從下面選項(xiàng)中選取答案。本題答案：【不能，因?yàn)樗粷M足分治法的第四個(gè)適應(yīng)條件（子問題是相互獨(dú)立的，也就是沒有重復(fù)子問題）】4、【單選題】快速冪算法求，其時(shí)間復(fù)雜性為O(logn)，a是實(shí)數(shù)，n為非負(fù)整數(shù)。下面是一同學(xué)用c語言編寫的求的代碼doubleexp2(doublea,intn){if(a==0)return0;if(n==0)return1;else{if(n%2)returna*exp2(a,n/2)*exp2(a,n/2);elsereturnexp2(a,n/2)*exp2(a,n/2);}}對(duì)該同學(xué)的算法評(píng)價(jià)正確的是？本題答案：【運(yùn)行結(jié)果正確，時(shí)間復(fù)雜性為O(n)】5、【單選題】快速排序和歸并排序是常用的排序算法，也都是采用分治法解決的問題?？焖倥判虻臅r(shí)間復(fù)雜性為O(),而歸并排序的時(shí)間復(fù)雜性為O(nlogn),究其原因，下面的解釋你認(rèn)為哪個(gè)正確？本題答案：【因?yàn)闅w并排序把問題劃分為兩個(gè)子問題時(shí)其規(guī)模大致相等，是原來規(guī)模的n/2，而快速排序劃分為子問題是使用partition()函數(shù)，劃分為子問題時(shí)不能保證二個(gè)子問題的規(guī)模大致相同，在極端狀況下，每次都只劃分為1個(gè)子問題，其規(guī)模為原問題規(guī)模n-1，因此快速排序在極端狀況下的時(shí)間復(fù)雜性的遞歸定義為T(n)=T(n-1)+O(n)】6、【單選題】猜數(shù)游戲：隨機(jī)選擇一個(gè)0~100內(nèi)的整數(shù)，讓你猜。猜對(duì)了，你贏了，游戲結(jié)束。如果沒有猜對(duì)，會(huì)告訴你猜大了，還是猜小了。當(dāng)然，越早猜對(duì)越好。問最少需要猜多少次，就能保證一定能猜對(duì)？本題答案：【7】7、【單選題】對(duì)于一個(gè)采用字符數(shù)組存放的長度為n的字符串str，下面是用分治策略的遞歸算法去判斷字符串str是否為回文，如是回文，函數(shù)返回true，否則返回false。比如：“abcba”、“abba”是回文，“abc”則不是回文。boolisPal(char*str,intn){if(n==0||【（1）】)returntrue;if(str[0]!=【（2）】)returnfalse;returnisPal(【（3）】,【（4）】);}算法中【】處缺少語句，請(qǐng)分析算法，從如下選項(xiàng)中選擇語句補(bǔ)齊算法。本題答案：【(1)n==1(2)str[n-1](3)str+1(4)n-2】8、【單選題】對(duì)于一個(gè)采用字符數(shù)組存放的長度為n的字符串str，下面是判斷是否回文的不完整算法。比如：“abcba”、“abba”是回文，“abc”則不是回文boolisPal(char*str,intn){if(n==0||【（1）】)returntrue;if(str[0]!=【（2）】)returnfalse;returnisPal(【（3）】,【（4）】);}請(qǐng)補(bǔ)齊代碼后分析算法的時(shí)間復(fù)雜性，回答如下問題本題答案：【該算法時(shí)間復(fù)雜性的遞歸定義為：T(n)=T(n-2)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(1)】9、【單選題】棋盤nxn（）的覆蓋問題，其中一個(gè)點(diǎn)已經(jīng)被覆蓋，用L型模塊將其余完全覆蓋的分治算法。關(guān)于該算法時(shí)間復(fù)雜性描述不正確的是本題答案：【T(n)=O(n^4)】10、【單選題】棋盤8X8的覆蓋問題，其中一個(gè)點(diǎn)已經(jīng)被覆蓋，用L型模塊將其余完全覆蓋的分治策略。約定解決四個(gè)子問題的順序?yàn)橛蚁?，左?左上，右上。用數(shù)字標(biāo)識(shí)法填寫覆蓋方案（如3個(gè)相連的整數(shù)值i構(gòu)成的L塊，代表是第i個(gè)被放入棋盤中的L型塊）。使用分治策略的算法有三種形式：1使用遞歸算法實(shí)現(xiàn)，2使用隊(duì)列存取分解出的子棋盤的非遞歸算法3.使用棧存取分解出的子棋盤的非遞歸算法。下圖中有三個(gè)覆蓋圖案（只標(biāo)出了前7塊L型模塊位置），問自左至右分別是哪種算法實(shí)現(xiàn)的覆蓋方案？本題答案：【遞歸算法，隊(duì)列算法，棧算法】11、【單選題】下面哪些不是遞歸算法的特點(diǎn)本題答案：【遞歸算法耗費(fèi)的時(shí)間和占用的內(nèi)存空間要比解決同一問題的非遞歸算法要少】12、【單選題】給定n個(gè)正整數(shù)組成的無序序列，要找到該序列的中位數(shù)，解決該問題的最優(yōu)算法的時(shí)間復(fù)雜性是？本題答案：【O（n）】13、【單選題】將一個(gè)遞歸算法改造為非遞歸算法，常用的數(shù)據(jù)結(jié)構(gòu)是？本題答案：【?！?4、【判斷題】分治法解決問題時(shí)，平衡子問題思想是指：當(dāng)問題劃分出的子問題規(guī)?；疽恢聲r(shí)，算法計(jì)算效率高本題答案：【正確】15、【判斷題】遞歸程序代碼簡短，結(jié)構(gòu)清晰，易讀性強(qiáng)，相比解決同一問題的非遞歸程序，遞歸程序運(yùn)行時(shí)間短。本題答案：【錯(cuò)誤】第三單元測(cè)試1、【單選題】求第n個(gè)斐波那契數(shù)的問題，根據(jù)動(dòng)態(tài)規(guī)劃的二要素分析，是可以用動(dòng)態(tài)規(guī)劃算法去解決的，下面是用備忘錄方法（遞歸）解決的求第n個(gè)斐波那契數(shù)f[n]的程序.這里N是一個(gè)較大的正整數(shù)常量，注意備忘錄方法的設(shè)計(jì)要點(diǎn)（也就是，對(duì)于一個(gè)問題，首先判斷是否該問題已被解決過，如果解決，不再重復(fù)。另外，解決過的問題，答案要記?。﹊ntf[N]={0,1,1};intfib(intn){if(【1】)returnf[n];elsereturn【2】;}代碼中【1】和【2】位置代碼缺失，請(qǐng)從下列選項(xiàng)中選出合適的語句補(bǔ)齊算法。本題答案：【【1】f[n]0【2】f[n]=fib(n-1)+fib(n-2)】2、【單選題】動(dòng)態(tài)規(guī)劃解題的步驟分為四步（1）分析最優(yōu)解的結(jié)構(gòu)（2）建立遞歸關(guān)系（3）計(jì)算最優(yōu)值（4）構(gòu)造最優(yōu)解。關(guān)于這四個(gè)步驟的內(nèi)容描述不正確的是哪個(gè)？本題答案：【計(jì)算最優(yōu)值：以自頂往下的方法計(jì)算問題的最優(yōu)值，也就是先求解規(guī)模較大的問題的最優(yōu)值。】3、【單選題】矩陣連乘問題：下圖是動(dòng)態(tài)規(guī)劃算法計(jì)算6個(gè)矩陣A1A2A3A4A5A6連乘所生成的信息表.（a）表描述了計(jì)算順序，（b）表是m[i][j]的最優(yōu)值表，（c）表是輔助信息表（斷開位置）。分析表格，給出A2A3A4A5A6五個(gè)矩陣連乘所需要的最少數(shù)乘次數(shù)，并用加括號(hào)的方法表示出其乘法順序。從如下選項(xiàng)中選擇。本題答案：【10500,(A2A3)((A4A5)A6)】4、【單選題】凸多邊形的三角剖分問題。用動(dòng)態(tài)規(guī)劃算法求解最優(yōu)三角剖分，首先要分析最優(yōu)解的結(jié)構(gòu)，也就是將問題分解為子問題，并具有最優(yōu)子結(jié)構(gòu)性質(zhì)。下圖是一凸6邊形(ABCDEF)的二種不同劃分為子問題的方法，哪種是正確的將問題劃分為子問題的方案？正確的劃分方案共有幾種不同方式？本題答案：【左圖正確，4種】5、【單選題】游艇租賃問題：長江游艇俱樂部在長江上設(shè)置了n個(gè)游艇出租站1~n，游客可在這些游艇出租站租用游艇，并在下游的任何出租站歸還游艇，限制只能從上游往下游行進(jìn)，游艇出租站i到出租站j直達(dá)的租金為r(i,j)（1=ij=n），計(jì)算從游艇出租站1到出租站n的最小費(fèi)用。該問題可有二種最優(yōu)解的結(jié)構(gòu)形式，如圖所示：如下描述中錯(cuò)誤的是哪個(gè)？本題答案：【圖2是將從1站到i站的最小費(fèi)用問題劃分為2個(gè)子問題即從第1站到第k站的最小費(fèi)用問題和從k站到i站的最小費(fèi)用問題?！?、【單選題】0-1背包問題：現(xiàn)有一背包容量c=5，n=4。4個(gè)物品分別為：(Wi,Vi)|(1,3),(3,6),(4,9),(2,7)。如下m表中m[i][j]是前i個(gè)物品裝背包容量為j時(shí)的最優(yōu)值。其中第四行的數(shù)據(jù)沒有填寫，分析問題，將第四行的數(shù)據(jù)從如下選項(xiàng)中找出。本題答案：【037101013】7、【單選題】最長公共子序列問題：現(xiàn)有兩個(gè)字符序列X和Y,下面c矩陣和b矩陣是算法填寫出的信息表。c[i][j]是X序列的前i個(gè)字符和Y序列的前j個(gè)字符的最長公共子序列的長度，b[i][j]是輔助信息表。已知X=”ABC”根據(jù)表格內(nèi)容，回答X和Y的最長公共子序列長度及最長公共子序列包含的符號(hào)本題答案：【長度2“AC”】8、【單選題】下面是求最長公共子序列長度和構(gòu)造最優(yōu)解的算法?！尽恐械恼Z句缺失，請(qǐng)從如下選項(xiàng)中找到正確的答案補(bǔ)齊算法。voidLCSLength(intm,intn,char*x,char*y,int**c,int**b){inti，j;for(i=1;i=m;i++)c[i][0]=0;for(j=1;j=n;i++)c[0][j]=0;for(i=1;i=m;i++)for(j=1;j=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){【1】;b[i][j]=2;}else{【2】;b[i][j]=3;}}}voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);coutx[i];}elseif(b[i][j]==2)【3】;else【4】;}本題答案：【(1)c[i][j]=c[i-1][j](2)c[i][j]=c[i][j-1](3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)】9、【單選題】操場(chǎng)上擺放一行共n堆石頭，從左到右方向編號(hào)為1~n，石子的數(shù)目分別為p[1],……,p[n]，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過n-1次合并，最終合并為一堆。計(jì)算這n堆石子合并為一堆的最小得分。分析該問題，從如下選項(xiàng)中找出用動(dòng)態(tài)規(guī)劃解決該問題的時(shí)間復(fù)雜性和空間復(fù)雜性本題答案：【T（n）=O（）S(n)=O()】10、【多選題】可用動(dòng)態(tài)規(guī)劃算法解決的問題需要滿足幾個(gè)基本要素，從下面選項(xiàng)中找出這些基本要素本題答案：【最優(yōu)子結(jié)構(gòu)性質(zhì)#重復(fù)子問題】11、【多選題】0-1背包問題：給定n種物品和一背包，物品i的重量wi，價(jià)值vi，背包容量為c，如何選擇裝入背包中的物品，使得裝入背包中的物品總價(jià)值最大。設(shè)m[i][j]是前i個(gè)物品裝入背包容量為j的背包所能獲得的最大價(jià)值，下面是關(guān)于最優(yōu)值的遞歸定義，從中選出正確的關(guān)于最優(yōu)值m[i][j]的遞歸定義。本題答案：【#】12、【多選題】操場(chǎng)上擺放一行共n堆石頭，從左到右方向編號(hào)為1~n，石子的數(shù)目分別為p[1],……,p[n]，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過n-1次合并，最終合并為一堆。計(jì)算這n堆石子合并為一堆的最小得分。請(qǐng)根據(jù)題目要求，從如下選項(xiàng)中找出關(guān)于從第i堆到第j堆合并為一堆的最小得分m[i][j]的遞歸定義.本題答案：【m[i][j]=0,if(i==j)#if（ij）m[i][j]=min(m[i][k]+m[k+1][j])+sum(i,j)這里i=kj，sum（i，j）是i堆到j(luò)堆石子的累加和?！?3、【填空題】操場(chǎng)上擺放一行共4堆石頭，從左到右方向編號(hào)為1~4，各堆石子的數(shù)目分別為7,10,3,5，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過5次合并，最終合并為一堆。計(jì)算這6堆石子合并為一堆的最小得分本題答案：【50】14、【填空題】現(xiàn)有一樓梯共8級(jí)臺(tái)階，有一小朋友一步可以邁出1、2或3級(jí)臺(tái)階，問小朋友有多少種不同的爬樓梯的方法本題答案：【81】第四單元測(cè)試1、【單選題】一個(gè)問題，針對(duì)某個(gè)貪心策略，可通過找反例的方法快速判斷出其使用貪心算法不能構(gòu)造出最優(yōu)解。下面是關(guān)于0-1背包問題，貪心策略是優(yōu)先選擇單位重量價(jià)值大的物品裝入背包，有二個(gè)同學(xué)分別找到一個(gè)反例，證明貪心算法不能構(gòu)造出0-1背包問題的最優(yōu)解。（1）背包容量4，三個(gè)物品的重量和價(jià)值（wi，vi）:（2，4）,（2，3）,（2，2）（2）背包容量5，三個(gè)物品的重量和價(jià)值（wi，vi）:（1，2）,（2，3）,（4，4）分析判定哪個(gè)反例是對(duì)的，哪個(gè)反例是錯(cuò)的，從如下選項(xiàng)中找到你的答案。本題答案：【（1）錯(cuò)（2）對(duì)】2、【單選題】一個(gè)n位的10進(jìn)制正整數(shù)，使得刪除k位（kn）后剩余數(shù)字組成的正整數(shù)最小，用貪心算法實(shí)現(xiàn)該算法，問該問題的貪心策略是什么？也就是每次要?jiǎng)h除哪個(gè)數(shù)字？本題答案：【每次從整數(shù)中找包含最高位的從左至右的一個(gè)最長的非遞減序列，將該序列的最后一位刪除】3、【單選題】某中學(xué)有一個(gè)開水房，只有一個(gè)供熱水龍頭，課間時(shí)，會(huì)有很多同學(xué)去排隊(duì)打開水，同學(xué)們的水瓶大小不一，每個(gè)同學(xué)打水時(shí)都會(huì)將自己的水瓶裝滿。管理開水房的師傅是個(gè)聰明人，他想到了一個(gè)排隊(duì)方案，也就是同學(xué)們按照他給出的排隊(duì)方法，可以使同學(xué)們的平均等待時(shí)間最短。你分析一下，給出這個(gè)排隊(duì)的方法，假定有n個(gè)人，第i個(gè)同學(xué)打水所需要的時(shí)間為ti，并給出平均等待時(shí)間的計(jì)算公式。（注意：第i個(gè)同學(xué)的等待時(shí)間包含前i-1個(gè)的打水時(shí)間和+自己打水的時(shí)間ti）本題答案：【按照打水時(shí)間從小到大排隊(duì)，假定排隊(duì)后第i個(gè)人的打水時(shí)間是ti,平均等待時(shí)間T=∑(n-i+1)ti/n1=i=n】4、【單選題】哈夫曼編碼樹是用貪心算法解決的典型問題，分析該算法，回答如下問題，假定有n個(gè)字符生成的編碼樹，問編碼樹中的結(jié)點(diǎn)總數(shù)是多少？可能的最長的字符編碼是多少位？本題答案：【2n-1個(gè)結(jié)點(diǎn)n-1位編碼】5、【單選題】下圖中A~F頂點(diǎn)分別代表6個(gè)村莊，圖中的邊代表村莊之間的距離，為了滿足這六個(gè)村莊相互通信的需要（任意兩個(gè)村莊有線路可達(dá)），需要架設(shè)通信線路，這里要求代價(jià)最小化（即線路總長度最?。?，請(qǐng)你分析問題找到代價(jià)最小的方案，并計(jì)算出線路總長度，從如下選項(xiàng)中找出答案。本題答案：【線路總長度21】6、【多選題】一個(gè)問題，確定了某個(gè)貪心策略，如果用貪心算法能夠構(gòu)造出問題的最優(yōu)解，需要該問題具備哪兩個(gè)條件？本題答案：【最優(yōu)子結(jié)構(gòu)性質(zhì)#貪心選擇性質(zhì)】7、【多選題】給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，給定V中的一個(gè)頂點(diǎn)A，稱為源，求從源頂點(diǎn)A出發(fā)到其他各頂點(diǎn)的最短路徑長度稱為單源最短路徑長度問題。關(guān)于單源最短路徑問題的Dijkstra算法，下面哪些描述是正確的？本題答案：【設(shè)定一個(gè)頂點(diǎn)集合S，初始時(shí)，S={A}，每次從V-S中選擇頂點(diǎn)加入S，直到全部加入，算法結(jié)束。#每次選擇加入S集合的頂點(diǎn)是從A頂點(diǎn)出發(fā)的最短路徑長度已知的頂點(diǎn)，也就是V-S集合中最短特殊路徑長度最小的頂點(diǎn)，通常算法中用dist[]數(shù)組記錄各頂點(diǎn)的最短特殊路徑長度。#每次選擇一個(gè)頂點(diǎn)加入S集合后，都要檢查是否需要更新dist[]數(shù)組元素的值】8、【判斷題】一個(gè)問題，可能有多個(gè)最優(yōu)解，但是使用貪心算法最多只能找到一個(gè)最優(yōu)解。本題答案：【正確】9、【判斷題】教材例題：多機(jī)調(diào)度問題，是用貪心算法求最優(yōu)解的一個(gè)例子，貪心策略是每次從剩余任務(wù)中選擇一個(gè)花費(fèi)時(shí)間最長的任務(wù)，安排在占用時(shí)間最少的機(jī)器上。本題答案：【錯(cuò)誤】10、【判斷題】貪心算法中常包含排序算法，也就是排序是貪心算法的伴隨算法，有人這樣解釋其原因：貪心算法是根據(jù)貪心策略一步一步地選擇去構(gòu)造問題的解，排序就是按照要選擇的順序排列好，選擇時(shí)只需按照排好的順序選擇就可以了。主要目的就是方便選擇。該說法是否正確？本題答案：【正確】11、【判斷題】貪心算法是以自底向上的方式構(gòu)造問題的最優(yōu)解本題答案：【錯(cuò)誤】12、【填空題】我國的貨幣單位是100元，50元，20元、10元、5元、2元、1元。有人到超市買了32元的商品，交給收銀員100元，問收銀員最少需要幾張貨幣就能完成找零錢？本題答案：【5】13、【填空題】最優(yōu)分解問題：一個(gè)正整數(shù)分解為若干互不相同的自然數(shù)的和，使其乘積最大。使用貪心算法求將22這個(gè)數(shù)最優(yōu)分解后，取得的最大乘積是多少？本題答案：【1008】第五章單元測(cè)試1、【單選題】下面關(guān)于回溯法的描述中，不正確的是哪個(gè)?本題答案：【回溯法，從解空間樹的根結(jié)點(diǎn)開始，當(dāng)搜索至葉子結(jié)點(diǎn)時(shí)，就找到了問題的解，算法結(jié)束?！?、【單選題】下面描述不正確的是？本題答案：【當(dāng)解空間樹是子集樹時(shí)，約束函數(shù)對(duì)0分支剪枝，限界函數(shù)對(duì)1分支剪枝?！?、【單選題】n皇后問題是可用回溯法解決的問題。下面描述不正確的是？本題答案：【兩種不同解空間樹的算法效率比較，排列樹的時(shí)間耗費(fèi)高于n叉樹】4、【單選題】0-1背包問題的回溯算法，下面的解釋不正確的是本題答案：【右（0）分支的剪枝：已裝入背包內(nèi)的物品價(jià)值和+剩余物品裝剩余背包容量所能獲得的最大價(jià)值（物品可分割，即用背包問題的貪心算法求得的最大價(jià)值）當(dāng)前最優(yōu)值bestp,就剪枝.】5、【單選題】n個(gè)城市的旅行售貨商問題的回溯法中，r[i][j]是鄰接矩陣，表示i城市到j(luò)城市的距離，x[]是路徑信息,有A、B兩段描述A.該問題的解空間樹，第一層只有一個(gè)分支，也就是指定第一個(gè)城市作為出發(fā)城市，因?yàn)槭黔h(huán)路的原因，指定哪個(gè)城市出發(fā)結(jié)果是一樣的，這樣做相當(dāng)于在樹的第一層剪掉了其他的n-1個(gè)分支，主要目的是提高搜索效率。自第二層開始往下是一顆排列樹。B.該算法將第n-1層的結(jié)點(diǎn)看做是葉子結(jié)點(diǎn)，當(dāng)搜索至該葉子結(jié)點(diǎn)時(shí)，整個(gè)環(huán)路(如果存在的話)長度就是路徑x[1..n-1]的長度cc+r[n-1][n]+r[n][1]。根據(jù)A,B描述的正確與否，從如下選項(xiàng)中找到正確答案本題答案：【A對(duì)，B錯(cuò)】6、【單選題】符號(hào)三角形問題的回溯算法如下half=（n+1）*n/4;//(n+1)*n/2是偶數(shù)voidbacktrack(intt){if((counthalf)||(t*(t-1)/2-counthalf))return;if(tn)sum++;elsefor(inti=0;i2;i++){p[1][t]=i;count+=i;for(intj=2;j=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}【】backtrack(t+1);for(intj=2;j=t;j++)count-=p[j][t-j+1];count-=i;}}現(xiàn)要求將紅色代碼去掉，保持算法功能不改變，需在【】添加下面哪段代碼？本題答案：【if((count=half)(t*(t+1)/2-count=half))】7、【單選題】子集和問題：給定n個(gè)不同的正整數(shù)，已知其和大于c，問有多少個(gè)不同的其和等于c的子集？下面給出的算法，解空間樹是子集樹，且n個(gè)數(shù)已按從小到大有序存放于a數(shù)組中。voidbacktrack(inti){if(sum==c)count++;elseif(i=n){if(sum+a[i]=c){sum+=a[i];backtrack(i+1);【】}}}請(qǐng)將【】位置缺失的代碼補(bǔ)齊，從下面選項(xiàng)中找到答案。本題答案：【sum-=a[i];backtrack(i+1);】8、【單選題】給定n個(gè)可能含有重復(fù)的元素存放于x[1:n]，輸出去掉重復(fù)的全排列，這里swap是實(shí)現(xiàn)兩個(gè)變量值的交換，下面是算法描述注意：紅色代碼部分【1】【2】【3】位置有代碼缺失。voidbacktrack(intt){if(tn){for(inti=1;i=n;i++)printf(%d,x[i]);printf(\n);}else{for(inti=t;i=n;i++){intok=1;for(intj=【1】;j【2】;j++)if(x[j]==x[i])｛【3】;break；｝if(ok){swap(x[t],x[i]);backtrack(t+1);swap(x[t],x[i]);}}}}上面的算法中，紅色代碼部分【1】【2】【3】位置代碼缺失，請(qǐng)從如下選項(xiàng)中找到合適的代碼。本題答案：【【1】t，【2】i，【3】ok=0】9、【單選題】符號(hào)三角形問題，其解空間樹是哪種？本題答案：【n叉樹（這里n=2）】10、【多選題】子集和問題：給定n個(gè)不同的正整數(shù)，已知其和大于c，要求找出一個(gè)子集使其和等于c。該問題除解空間樹是子集樹的回溯法外，還有解空間樹是排列樹的回溯算法，思考該問題，從如下選項(xiàng)中找到關(guān)于該算法設(shè)計(jì)的正確的描述。本題答案：【當(dāng)解空間樹是排列樹時(shí)，搜索時(shí)，可以將從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑上的數(shù)看成是一個(gè)子集。#剪枝條件:當(dāng)路徑上的數(shù)之和c時(shí)剪枝】11、【多選題】回溯法的算法效率跟哪些因素有關(guān)？這里x【k】是分支上的取值。本題答案：【滿足隱約束函數(shù)和限界函數(shù)約束的所有x【k】的個(gè)數(shù)#計(jì)算隱約束函數(shù)值的時(shí)間#計(jì)算限界函數(shù)值的時(shí)間#滿足顯約束的x【k】的個(gè)數(shù)。】12、【判斷題】回溯法是在一顆已經(jīng)建立起來的解空間樹中實(shí)現(xiàn)深度優(yōu)先搜索的算法。本題答案：【錯(cuò)誤】13、【判斷題】回溯法中，剪枝函數(shù)能夠剪掉的分支越多，算法效率就越高。因此，我們?cè)谠O(shè)計(jì)回溯法時(shí)，就要設(shè)計(jì)剪枝函數(shù)能夠剪掉盡量多的分支。本題答案：【錯(cuò)誤】第六單元測(cè)試1、【單選題】分支限界法與回溯法的不同點(diǎn)體現(xiàn)在哪些方面？（1）求解目標(biāo)不同，分支限界法可求最優(yōu)解或滿足條件的一個(gè)解，而回溯法可求最優(yōu)解或滿足條件的所有解（2）搜索方式不同，回溯法是以深度優(yōu)先狀態(tài)生成樹法搜索解空間樹，分支限界法則以廣度優(yōu)先或最小耗費(fèi)（最大效益）優(yōu)先的狀態(tài)生成樹法搜索解空間樹。（3）同一個(gè)問題在使用回溯法或分支限界法時(shí)，該問題的解空間樹的結(jié)構(gòu)不同（4）回溯法與分支限界法，構(gòu)造最優(yōu)解的方式不同。從上述選項(xiàng)中找出答案。本題答案：【（1）（2）（4）】2、【單選題】分支限界法中，擴(kuò)展出的孩子結(jié)點(diǎn)在入隊(duì)時(shí)，存儲(chǔ)該孩子結(jié)點(diǎn)的父結(jié)點(diǎn)的地址和左孩子標(biāo)志。其目的是什么？本題答案：【為了構(gòu)造最優(yōu)解】3、【單選題】在隊(duì)列式分支限界法解決裝載問題時(shí)，為什么在其改進(jìn)算法中，每次進(jìn)入左分支都要檢查更新bestw，而不是等搜索到達(dá)葉子結(jié)點(diǎn)時(shí)才去更新bestw，其目的是什么？本題答案：【為了及早使右（0）分支剪枝函數(shù)生效?！?、【單選題】在隊(duì)列式分支限界法中，葉子結(jié)點(diǎn)不加入隊(duì)列。而在優(yōu)先隊(duì)列式分支限界法中，葉子結(jié)點(diǎn)通常要加入到優(yōu)先隊(duì)列中。有下列2個(gè)解釋：（1）隊(duì)列式分支限界法，活結(jié)點(diǎn)在隊(duì)列中的順序是按照搜索解空間樹時(shí)擴(kuò)展出該結(jié)點(diǎn)的先后順序存放，每次從隊(duì)首取出一個(gè)活結(jié)點(diǎn)成為新的擴(kuò)展結(jié)點(diǎn)。擴(kuò)展結(jié)點(diǎn)擴(kuò)展出的兒子結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，會(huì)將該葉子結(jié)點(diǎn)的值同當(dāng)前最優(yōu)值比較，檢查更新最優(yōu)值，葉子結(jié)點(diǎn)并不進(jìn)入隊(duì)列，等隊(duì)列為空時(shí)，搜索結(jié)束，記錄的當(dāng)前最優(yōu)值就是問題最優(yōu)值。（2）優(yōu)先隊(duì)列式分支限界法中，當(dāng)優(yōu)先級(jí)的定義是限界函數(shù)時(shí)，擴(kuò)展出的葉子結(jié)點(diǎn)進(jìn)入隊(duì)列，這種做法主要是為了讓搜索過程提前結(jié)束。也就是當(dāng)從優(yōu)先隊(duì)列中取出一個(gè)活結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)，意味著現(xiàn)在優(yōu)先隊(duì)列中剩余的所有活結(jié)點(diǎn)其優(yōu)先級(jí)都不大于該葉子結(jié)點(diǎn)的優(yōu)先級(jí)，葉子結(jié)點(diǎn)的優(yōu)先級(jí)等于最優(yōu)值，算法結(jié)束，無論優(yōu)先隊(duì)列是否為空。根據(jù)其正確與否，給出答案本題答案：【（1）正確，（2）正確】5、【單選題】下面是優(yōu)先隊(duì)列式分支限界算法解0-1背包問題的部分主代碼，分析代碼將【】內(nèi)的代碼補(bǔ)齊。TempleteclassTypew,classTypepTypepknapTypew,Typep::MaxKnapsack(){//優(yōu)先隊(duì)列分支限界法，返回最大價(jià)值，最優(yōu)解bestxH=newMaxHeapHeapNodeTypep,Typew(1000);//定義最大堆的容量為1000bestx=newint[n+1];inti=1;E=0;cw=cp=0;Typepbestp=0;Typepup=Bound(1）；while(【1】){Typewwt=cw+w[i];if(wt=c){if(cp+p[i]bestp)【2】；AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);if(upbestp)AddLiveNode(up,cp,cw,false,i+1);//從優(yōu)先隊(duì)列中取下一個(gè)擴(kuò)展節(jié)點(diǎn)HeapNodeTypep,TypewN;H-DeleteMax(N);E=NNaNr;cw=N.weight;cp=N.profit;up=N.upprofit;i=N.level;}//構(gòu)造最優(yōu)解for（intj=n;j0;j--）{bestx[j]=E-lchild;E=E-parent;}returncp;}本題答案：【【1】in+1,【2】besp=cp+p[i]】6、【單選題】閱讀該單元測(cè)試中關(guān)于0-1背包問題的優(yōu)先隊(duì)列分支限界算法代碼，問左分支的剪枝條件是什么？右分支的剪枝條件是什么？從代碼中找到命令行，使用原代碼回答問題。本題答案：【左分支：wt=c,右分支：upbestp】7、【多選題】優(yōu)先隊(duì)列式分支限界法解決0-1背包問題時(shí)，下面描述正確的是本題答案：【左孩子結(jié)點(diǎn)的優(yōu)先級(jí)等于父結(jié)點(diǎn)的優(yōu)先級(jí)#右孩子結(jié)點(diǎn)相應(yīng)的背包內(nèi)物品的價(jià)值等于父結(jié)點(diǎn)相應(yīng)的背包內(nèi)的物品價(jià)值】8、【判斷題】回溯法與分支限界法的空間復(fù)雜度是相同的，都是O(h(n)),h(n)是解空間樹的深度。本題答案：【錯(cuò)誤】9、【判斷題】在隊(duì)列式分支限界法解決裝載問題時(shí)，在隊(duì)列中加入一個(gè)-1標(biāo)志，該標(biāo)志所起的作用是表示其后的活結(jié)點(diǎn)在解空間樹中的層數(shù)比-1之前的活結(jié)點(diǎn)更深一層，或者說是同層活結(jié)點(diǎn)的結(jié)束標(biāo)志。本題答案：【正確】10、【填空題】下面是一個(gè)布線問題,S表示布線的起點(diǎn)，O表示布線的終點(diǎn)，假定布線只能垂直、或水平布線，從一個(gè)點(diǎn)按照上、下、左、右的優(yōu)先順序可往四個(gè)方向布線，“#是障礙不能通過。已知從一個(gè)位置向其上、下、左、右四個(gè)相鄰位置布線的線路長度為1。使用隊(duì)列式分支限界法解決該問題，問從S到O的最短布線長度？###S##o#######本題答案：【8】第七單元測(cè)試1、【單選題】有這樣一種算法，運(yùn)行一次可能找不到問題的解，運(yùn)行多次就一定能找到問題的解，且運(yùn)行次數(shù)有界，這種算法是？本題答案：【拉斯維加斯算法】2、【單選題】有這樣一種算法，運(yùn)行一次一定能找到問題的解，有時(shí)不知其是否正確，可以確定的是該解高概率（大于50%）是正確的。這種算法是？本題答案：【蒙特卡洛算法】3、【單選題】有一個(gè)問題的蒙特卡洛算法，給定一個(gè)實(shí)例，已知運(yùn)行一次其答案是錯(cuò)誤的概率是1/8,現(xiàn)運(yùn)行k次該算法，其答案一直不變，問該答案的正確率是？本題答案：【1-(1/8)^k】4、【單選題】一致的p正確的偏y0的蒙特卡洛算法，下面解釋不正確的是?本題答案：【運(yùn)行蒙特卡洛算法p次，至少有一次是正確的?！?、【單選題】pollard算法找到一個(gè)整數(shù)因子的時(shí)間復(fù)雜性是？本題答案：【O()】6、【單選題】n=12皇后問題的三種不同的解決方案：回溯法、拉斯維加斯算法、拉斯維加斯算法+回溯法。對(duì)于給定的一個(gè)實(shí)例，(1)平均耗費(fèi)時(shí)間最少的是那種方案？，(2)平均耗費(fèi)時(shí)間最多的是那種方案？本題答案：【(1)拉斯維加斯+回溯(2)回溯法】7、【單選題】在分治法中講到快速排序，如果每次使用partion函數(shù)導(dǎo)致分組出現(xiàn)嚴(yán)重不平衡情況下，算法效率不高，最壞情況下的時(shí)間復(fù)雜度為O（n^2）,通過改造partition函數(shù)，也就是每次隨機(jī)選擇一個(gè)元素作為劃分基準(zhǔn)，這樣會(huì)很好地改善算法的性能，這種算法思想是？本題答案：【舍伍德算法】8、【多選題】舍伍德算法思想是通過引入隨機(jī)化策略將確定性算法改造為隨機(jī)算法，打破原來確定性算法在某些實(shí)例情況下，其時(shí)間復(fù)雜性必然遠(yuǎn)高于平均時(shí)間復(fù)雜性的規(guī)律。下面哪些算法可以應(yīng)用舍伍德算法思想？本題答案：【快速排序算法#線性時(shí)間選擇算法#跳躍表】9、【判斷題】計(jì)算機(jī)中的隨機(jī)數(shù)是偽隨機(jī)的，因?yàn)樗蔷哂幸欢ㄒ?guī)律的，是按公式計(jì)算出來的。該說法正確嗎？本題答案：【正確】10、【判斷題】素?cái)?shù)測(cè)試問題的蒙特卡洛算法，n是一個(gè)待判定正整數(shù)。當(dāng)n是素?cái)?shù)時(shí)，有時(shí)會(huì)被判定為非素?cái)?shù)。該說法正確嗎?本題答案：【錯(cuò)誤】11、【判斷題】有人說可以設(shè)計(jì)蒙特卡洛算法去猜硬幣的反正面問題，該說法是否正確？本題答案：【錯(cuò)誤】12、【填空題】數(shù)值概率算法求π的算法，是用半徑為1的圓外接一個(gè)正方形，然后模擬向正方形中隨機(jī)投放n個(gè)點(diǎn)，計(jì)數(shù)落在圓內(nèi)的點(diǎn)的個(gè)數(shù)為k，則π的近似值為本題答案：【4k/n##%_YZPRLFH_%##4*k/n】第八單元測(cè)試1、【單選題】下面哪個(gè)問題不是NPC問題本題答案：【最小生成樹問題】2、【單選題】請(qǐng)從下列選項(xiàng)中找出正確的P問題與NP問題的關(guān)系本題答案：【】3、【判斷題】NP問題是確定性算法不能在多項(xiàng)式時(shí)間復(fù)雜性解決的可判定問題本題答案：【錯(cuò)誤】4、【判斷題】一個(gè)NPC問題，首先是NP問題，另外所有的其他NP問題都能在多項(xiàng)式時(shí)間復(fù)雜性規(guī)約為該問題本題答案：【正確】5、【判斷題】研究NPC問題的意義，一旦一個(gè)NPC問題找到了多項(xiàng)式時(shí)間復(fù)雜性的確定性算法，那么所有的NPC問題都找到了多項(xiàng)式時(shí)間復(fù)雜性的確定性算法。本題答案：【正確】6、【判斷題】NP難問題未必是NP問題本題答案：【正確】7、【判斷題】一個(gè)人正站在門口，讓你猜他（她）是否要出門？，該問題是不可判定問題，該觀點(diǎn)是否正確？本題答案：【正確】客觀題試卷1、【單選題】如下哪種表示不是歸并排序算法時(shí)間復(fù)雜性本題答案：【o(nlogn)】2、【單選題】最優(yōu)子結(jié)構(gòu)性質(zhì)是本題答案：【問題的最優(yōu)解可通過性質(zhì)相同的子問題的最優(yōu)解合并而成】3、【單選題】有一算法的時(shí)間復(fù)雜性遞歸定義:T(n)=8T(n/2)+nlognifn1,T(1)=1;問T(n)=？本題答案：【】4、【單選題】哈夫曼編碼樹算法中用優(yōu)先隊(duì)列（堆）存儲(chǔ)生成的結(jié)點(diǎn)，n個(gè)字符的哈夫曼編碼樹算法時(shí)間復(fù)雜性為本題答案：【】5、【單選題】下列哪些問題不能用貪心算法求最優(yōu)解本題答案：【最優(yōu)二叉搜素樹】6、【單選題】在下列算法中，可求解n皇后問題的算法是本題答案：【拉斯維加斯算法】7、【單選題】爬樓梯問題：有一樓梯共n級(jí)臺(tái)階，有一小朋友一次可以邁1，2或3級(jí)臺(tái)階，求共有多少不同的走法走完這n級(jí)臺(tái)階?；卮鹪搯栴}最適合使用哪種算法？本題答案：【動(dòng)態(tài)規(guī)劃】8、【單選題】給定n個(gè)任務(wù)接受同一臺(tái)機(jī)器加工,任務(wù)i有服務(wù)時(shí)間和要求截止時(shí)間(ti,di),找出最小延遲方案，即所有任務(wù)延遲時(shí)間最大值的最小化問題。如3個(gè)任務(wù)1、2、3，服務(wù)時(shí)間和截至?xí)r間為（2，4）（1，2）（7，7），如按照1-2-3順序安排，各任務(wù)的延遲為0，1，3，延遲的最大值為3。使用貪心算法，如下哪種貪心策略可得到最優(yōu)解？本題答案：【以截止時(shí)間di從小到大安排】9、【單選題】有n個(gè)正整數(shù)組成的數(shù)組a，兩端的數(shù)不能刪除，中間每刪除一個(gè)數(shù)，其得分為其本身同其兩側(cè)的數(shù)的乘積，求其中間n-2個(gè)數(shù)逐個(gè)刪除后的最大得分。設(shè)m[i][j]為從a[i]到a[j]的子數(shù)組，將中間數(shù)全部刪除后的最大得分。從如下公式中選擇正確的m[i][j]的遞歸定義本題答案：【m[i][j]=max(m[i][k]+m[k][j]+a[i]*a[k]*a[j]),ikj,if(j-i1).m[i][j]=0;if(j-i==1)】10、【單選題】下面哪些不是隊(duì)列式分支限界法的特點(diǎn)本題答案：【葉子結(jié)點(diǎn)要加入隊(duì)列】11、【多選題】回溯法和分支限界法的主要區(qū)別是本題答案：【搜素方式不同#求解目標(biāo)不同】12、【多選題】P問題、NP問題、NPC問題，下列哪些解釋是正確的？本題答案：【P問題是確定性算法多項(xiàng)式時(shí)間復(fù)雜性解決的可判定問題#PíNP】13、【多選題】快速排序算法，其時(shí)間復(fù)雜性是，而其平均時(shí)間復(fù)雜性是，下面哪些方法可以改善快速排序算法的性能？本題答案：【洗牌算法#舍伍德算法】14、【多選題】下面哪些算法是解決單源最短路徑問題的有效算法？本題答案：【貪心算法#優(yōu)先隊(duì)列分支限界法】15、【多選題】一個(gè)含有n個(gè)元素的有序數(shù)組A,將其循環(huán)右移動(dòng)c個(gè)位置得到新的數(shù)組B,則B為循環(huán)有序的，如有5個(gè)元素的數(shù)組：12345，每個(gè)元素循環(huán)右移3個(gè)位置得到新數(shù)組：34512，是循環(huán)有序的，B[i]=A[(i+c)%n】?，F(xiàn)給定一個(gè)含有n個(gè)元素的循環(huán)有序序列，要找到其最小值。給定方法是分治策略，將數(shù)組一分為二，B[0..n/2-1]和B[n/2..n-1],從下列選項(xiàng)中找到正確的描述本題答案：【將一個(gè)規(guī)模為n的問題分解為一個(gè)子問題#該算法的時(shí)間復(fù)雜度是O（log（n）)】16、【多選題】現(xiàn)有n個(gè)字符，在一份報(bào)文中出現(xiàn)的次數(shù)構(gòu)成斐波那契數(shù)列，即1,1,2,3,5，，，..問這n個(gè)字符的哈夫曼編碼，具有如下哪些特點(diǎn)？本題答案：【編碼長度為n-1位的有二個(gè)字符#編碼長度為1到n-2的字符都只有一個(gè)】17、【多選題】1、最大團(tuán)問題是指求無向圖中任意兩個(gè)頂點(diǎn)都有連接邊的子圖，且頂點(diǎn)個(gè)數(shù)最多?，F(xiàn)有回溯法算法如下。將【】內(nèi)缺失的代碼補(bǔ)齊。這里a是鄰接矩陣，a[i][j]=0表示i和j頂點(diǎn)沒有連接關(guān)系。voidbacktrack(inti){if(in){for(intj=1;j=n;j++)bestx[j]=x[j];bestn=cn;return;}booleanok=true;for(intj=1;ji;j++)if(!a[i][j]){ok=false;break;}if(ok){x[i]=1;【1】;backtrack(i+1);cn--;}if(【2】){x[i]=0;backtrack(i+1);}}請(qǐng)從如下4個(gè)選項(xiàng)中找出適合填入【1】【2】的兩個(gè)選項(xiàng)本題答案：【cn=cn+1；#cn+n-i】18、【填空題】爬樓梯問題：一樓梯共6級(jí)臺(tái)階，有一小朋友一次可以邁1，2或3級(jí)臺(tái)階，問共有多少不同的走法走完6級(jí)臺(tái)階？本題答案：【24】19、【填空題】下面是優(yōu)先隊(duì)列式分支限界算法解裝載問題（n個(gè)集裝箱裝船）的部分代碼，分析下面代碼1TempleteclassType2TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//返回最大裝載量Ew，最優(yōu)解bestx3MaxHeapHeapNodeTypeH(1000);//定義最大堆的容量為10004Type*r=newType[n+1];5r[n]=0;6for(intj=n-1;j0;j--)r[j]=r[j+1]+w[j+1];7inti=1;8bbnode*E=0;9TypeEw=0;10while(i!=【1】){//搜索子集樹11if(Ew+w[i]=c)AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);12AddLiveNode(H,E,Ew+r[i],false,i+1);13HeapNodeTypeN;14H.DeleteMax(N);15i=N.level;16E=NNaNr;17Ew=N.uweight-【2】;18}19for（intj=n;j0;j--）{20bestx[j]=E-lchild;E=E-parent;｝21returnEw;22}該題目中有二個(gè)位置【1】【2】代碼缺失，請(qǐng)補(bǔ)齊【1】的代碼本題答案：【n+1##%_YZPRLFH_%##1+n】20、【填空題】下面是優(yōu)先隊(duì)列式