MOOC算法設(shè)計(jì)與分析-青島大學(xué)中國大學(xué)慕課答案第一章單元測試1、問題：下面列出了算法的四個(gè)性質(zhì)，哪個(gè)性質(zhì)是程序不一定具備的？選項(xiàng)：A、有輸入B、有輸出C、確定性D、有窮性正確答案:【有窮性】2、問題：在算法設(shè)計(jì)與分析過程中，有算法設(shè)計(jì)，算法的正確性證明，算法的復(fù)雜性分析,程序設(shè)計(jì)等幾個(gè)重要步驟，下面哪種順序是正確的？選項(xiàng)：A、算法的正確性證明-算法設(shè)計(jì)-算法的復(fù)雜性分析-程序設(shè)計(jì)B、算法的正確性證明-算法的復(fù)雜性分析-算法設(shè)計(jì)-程序設(shè)計(jì)C、算法設(shè)計(jì)-算法的正確性證明-算法的復(fù)雜性分析-程序設(shè)計(jì)D、算法設(shè)計(jì)-算法的復(fù)雜性分析-算法的正確性證明-程序設(shè)計(jì)正確答案:【算法設(shè)計(jì)-算法的正確性證明-算法的復(fù)雜性分析-程序設(shè)計(jì)】3、問題：下面哪些內(nèi)容不是算法設(shè)計(jì)之前要完成的內(nèi)容?選項(xiàng)：A、是求精確解還是近似解B、確定合適的數(shù)據(jù)結(jié)構(gòu)C、確定合適的算法策略D、使用何種計(jì)算機(jī)語言設(shè)計(jì)程序正確答案:【使用何種計(jì)算機(jī)語言設(shè)計(jì)程序】4、問題：下面是快速冪算法求的代碼，這里n≥0,a是實(shí)數(shù)。對該算法的時(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;}選項(xiàng)：A、B、C、D、正確答案:【】5、問題：下面哪個(gè)算法在最壞情況下的時(shí)間復(fù)雜性最低選項(xiàng)：A、歸并排序B、插入排序C、快速排序D、冒泡排序正確答案:【歸并排序】6、問題：有時(shí)間復(fù)雜性選項(xiàng)：,時(shí)間復(fù)雜性從低到高的順序是？A、B、C、D、正確答案:【】7、問題：有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是?選項(xiàng)：A、B、C、D、正確答案:【】8、問題：有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是？選項(xiàng)：A、B、C、D、正確答案:【】9、問題：有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是？選項(xiàng)：A、B、C、D、正確答案:【】10、問題：有一個(gè)算法，它的時(shí)間復(fù)雜性T(n)的遞歸定義如下，問T（n）是?選項(xiàng)：A、B、C、D、正確答案:【】11、問題：A公司處理器速度是B公司的100倍。對于復(fù)雜性為O()的算法，B公司的計(jì)算機(jī)可以在1小時(shí)內(nèi)處理規(guī)模為n的問題，A公司的計(jì)算機(jī)在1小時(shí)內(nèi)能處理的問題規(guī)模是多少？選項(xiàng)：A、nB、10nC、100nD、正確答案:【10n】12、問題：關(guān)于算法的正確性，下面哪些說法是正確的？選項(xiàng)：A、若算法是正確的，則算法一定能結(jié)束（運(yùn)行時(shí)間是有限的）B、若算法是正確的，則對于問題的任何實(shí)例，算法都能得到正確的結(jié)果。C、對于問題的一個(gè)實(shí)例，如果算法能夠獲得正確的結(jié)果，就證明算法是正確的。D、對于問題的一個(gè)實(shí)例，如果算法不能獲得正確的結(jié)果，就證明算法是不正確的。正確答案:【若算法是正確的，則算法一定能結(jié)束（運(yùn)行時(shí)間是有限的）#若算法是正確的，則對于問題的任何實(shí)例，算法都能得到正確的結(jié)果。#對于問題的一個(gè)實(shí)例，如果算法不能獲得正確的結(jié)果，就證明算法是不正確的?！?3、問題：解決同一個(gè)問題的算法策略可能有多個(gè)，使用不同算法策略設(shè)計(jì)的算法，其算法時(shí)間復(fù)雜性可能有顯著差異。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】14、問題：學(xué)習(xí)主定理和遞歸樹等求解遞歸方程方法，主要目的是解決求遞歸算法的時(shí)間復(fù)雜性問題選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】15、問題：自然語言、偽代碼都可以描述算法，而流程圖不能描述算法選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】第二章單元測試1、問題：分治法解決問題分為三步走，即分、治、合。下面列出了幾種操作，請按分、治、合順序選擇正確的表述。（1）將各個(gè)子問題的解合并為原問題的解，（2）將問題分解為各自獨(dú)立的多個(gè)子問題，（3）將多個(gè)子問題合并為原問題。（4）求各個(gè)子問題的解，（5）將問題分解為可重復(fù)的多個(gè)子問題。選項(xiàng)：A、(5)(4)(1)B、(2)(4)(1)C、(2)(1)(3)D、(5)(1)(3)正確答案:【(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)確的是選項(xiàng)：A、k是常系數(shù)；n/m是規(guī)模為n的問題分為m個(gè)子問題；f(n)是分解為子問題的時(shí)間復(fù)雜性與合并子問題的解的時(shí)間復(fù)雜性之和。B、k是子問題個(gè)數(shù)，n/m是子問題的規(guī)模，f(n)是分解為子問題的時(shí)間復(fù)雜性與合并子問題的解的時(shí)間復(fù)雜性之和C、k是子問題個(gè)數(shù)，n/m是子問題的規(guī)模，f(n)是規(guī)模為n的問題分解為子問題的時(shí)間復(fù)雜性D、k是常系數(shù)，n/m是規(guī)模為n的問題分為m個(gè)子問題，f(n)是將子問題的解合并為問題的解的時(shí)間復(fù)雜性。正確答案:【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)中選取答案。選項(xiàng)：A、能，因?yàn)樗鼭M足分治法的四個(gè)適應(yīng)條件B、能，因?yàn)樗梢杂梅?、治、合三個(gè)步驟完成計(jì)算C、不能，因?yàn)樗粷M足分治法的第四個(gè)適應(yīng)條件（子問題是相互獨(dú)立的，也就是沒有重復(fù)子問題）D、不能，因?yàn)樗豢梢杂梅?、治、合三個(gè)步驟完成計(jì)算正確答案:【不能，因?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);}}對該同學(xué)的算法評價(jià)正確的是？選項(xiàng)：A、運(yùn)行結(jié)果正確，時(shí)間復(fù)雜性為O(logn)B、運(yùn)行結(jié)果錯(cuò)誤，時(shí)間復(fù)雜性為O(n)C、運(yùn)行結(jié)果正確，時(shí)間復(fù)雜性為O(n)D、運(yùn)行結(jié)果錯(cuò)誤，時(shí)間復(fù)雜性為O(logn)正確答案:【運(yùn)行結(jié)果正確，時(shí)間復(fù)雜性為O(n)】5、問題：快速排序和歸并排序是常用的排序算法，也都是采用分治法解決的問題?？焖倥判虻臅r(shí)間復(fù)雜性為O(),而歸并排序的時(shí)間復(fù)雜性為O(nlogn),究其原因，下面的解釋你認(rèn)為哪個(gè)正確？選項(xiàng)：A、這是因?yàn)闅w并排序把問題劃分為子問題時(shí)的時(shí)間復(fù)雜性是O(1)，而快速排序劃分為子問題是使用partition()函數(shù)，其時(shí)間復(fù)雜性是O（n）。B、因?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)C、歸并排序的分和合的時(shí)間復(fù)雜性之和低于快速排序的分和合的時(shí)間復(fù)雜性之和D、因?yàn)榭焖倥判驅(qū)栴}劃分為子問題的個(gè)數(shù)比歸并排序要多正確答案:【因?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ù)，讓你猜。猜對了，你贏了，游戲結(jié)束。如果沒有猜對，會告訴你猜大了，還是猜小了。當(dāng)然，越早猜對越好。問最少需要猜多少次，就能保證一定能猜對？選項(xiàng)：A、6B、7C、51D、101正確答案:【7】7、問題：對于一個(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）】);}算法中【】處缺少語句，請分析算法，從如下選項(xiàng)中選擇語句補(bǔ)齊算法。選項(xiàng)：A、(1)n==1(2)str[n](3)str+1(4)n-1B、(1)n==1(2)str[n-1](3)str+1(4)n-2C、(1)str[0]==str[n-1](2)str[n-1](3)str(4)n-1D、(1)str[0]==str[n-1](2)str[n](3)str(4)n-2正確答案:【(1)n==1(2)str[n-1](3)str+1(4)n-2】8、問題：對于一個(gè)采用字符數(shù)組存放的長度為n的字符串str，下面是判斷是否回文的不完整算法。比如：“abcba”、“abba”是回文，“abc”則不是回文boolisPal(char*str,intn){if(n==0||【（1）】)returntrue;if(str[0]!=【（2）】)returnfalse;returnisPal(【（3）】,【（4）】);}請補(bǔ)齊代碼后分析算法的時(shí)間復(fù)雜性，回答如下問題選項(xiàng)：A、該算法時(shí)間復(fù)雜性的遞歸定義為：T(n)=T(n-1)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(1)B、該算法時(shí)間復(fù)雜性的遞歸定義為：T(n)=T(n-1)+1,ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(n)C、該算法時(shí)間復(fù)雜性的遞歸定義為：T(n)=T(n-2)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(1)D、該算法時(shí)間復(fù)雜性的遞歸定義為：T(n)=T(n-2)+1，ifn1;T(n)=O(1),ifn≤1。T(n)=O(n),T(n)=Ω(n)正確答案:【該算法時(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ù)雜性描述不正確的是選項(xiàng)：A、T(n)=4T(n/2)+O(1),ifn1;T(n)=O(1),ifn==1。B、T(k)=4T(k-1)+O(1),ifk0;T(k)=O(1),ifk==0。這里n=2^kC、T(n)=O(n^4)D、T(k)=O(4^k)正確答案:【T(n)=O(n^4)】10、問題：棋盤8X8的覆蓋問題，其中一個(gè)點(diǎn)已經(jīng)被覆蓋，用L型模塊將其余完全覆蓋的分治策略。約定解決四個(gè)子問題的順序?yàn)橛蚁?，左?左上，右上。用數(shù)字標(biāo)識法填寫覆蓋方案（如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)的覆蓋方案？選項(xiàng)：A、棧算法，隊(duì)列算法，遞歸算法B、隊(duì)列算法，棧算法，遞歸算法C、遞歸算法，隊(duì)列算法，棧算法D、遞歸算法，棧算法，隊(duì)列算法正確答案:【遞歸算法，隊(duì)列算法，棧算法】11、問題：下面哪些不是遞歸算法的特點(diǎn)選項(xiàng)：A、結(jié)構(gòu)清晰B、可讀性強(qiáng)C、容易用數(shù)學(xué)歸納法證明算法的正確性D、遞歸算法耗費(fèi)的時(shí)間和占用的內(nèi)存空間要比解決同一問題的非遞歸算法要少正確答案:【遞歸算法耗費(fèi)的時(shí)間和占用的內(nèi)存空間要比解決同一問題的非遞歸算法要少】12、問題：給定n個(gè)正整數(shù)組成的無序序列，要找到該序列的中位數(shù)，解決該問題的最優(yōu)算法的時(shí)間復(fù)雜性是？選項(xiàng)：A、O（logn）B、O（n）C、O（nlogn）D、正確答案:【O（n）】13、問題：將一個(gè)遞歸算法改造為非遞歸算法，常用的數(shù)據(jù)結(jié)構(gòu)是？選項(xiàng)：A、順序表B、鏈表C、棧D、隊(duì)列正確答案:【?！?4、問題：分治法解決問題時(shí)，平衡子問題思想是指：當(dāng)問題劃分出的子問題規(guī)?；疽恢聲r(shí)，算法計(jì)算效率高選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】15、問題：遞歸程序代碼簡短，結(jié)構(gòu)清晰，易讀性強(qiáng)，相比解決同一問題的非遞歸程序，遞歸程序運(yùn)行時(shí)間短。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】第三單元測試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)（也就是，對于一個(gè)問題，首先判斷是否該問題已被解決過，如果解決，不再重復(fù)。另外，解決過的問題，答案要記?。﹊ntf[N]={0,1,1};intfib(intn){if(【1】)returnf[n];elsereturn【2】;}代碼中【1】和【2】位置代碼缺失，請從下列選項(xiàng)中選出合適的語句補(bǔ)齊算法。選項(xiàng)：A、【1】n3【2】fib(n-1)+fib(n-2)B、【1】f[n]0【2】fib(n-1)+fib(n-2)C、【1】f[n]0【2】f[n]=fib(n-1)+fib(n-2)D、【1】n3【2】f[n]=fib(n-1)+fib(n-2)正確答案:【【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è)？選項(xiàng)：A、分析最優(yōu)解的結(jié)構(gòu)：一個(gè)一般化問題可以分解為幾個(gè)性質(zhì)相同的子問題，并且問題的最優(yōu)解可以通過子問題的最優(yōu)解合并得到，也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)B、建立遞歸關(guān)系：建立關(guān)于問題最優(yōu)值的遞歸定義，即問題的最優(yōu)值通過子問題的最優(yōu)值合并得到。C、計(jì)算最優(yōu)值：以自頂往下的方法計(jì)算問題的最優(yōu)值，也就是先求解規(guī)模較大的問題的最優(yōu)值。D、構(gòu)造最優(yōu)解：根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造正確答案:【計(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ù)，并用加括號的方法表示出其乘法順序。從如下選項(xiàng)中選擇。選項(xiàng)：A、15125,(A2(A3A4))(A5A6)B、10500,(A2(A3A4))(A5A6)C、15125,(A2A3)((A4A5)A6)D、10500,(A2A3)((A4A5)A6)正確答案:【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)的二種不同劃分為子問題的方法，哪種是正確的將問題劃分為子問題的方案？正確的劃分方案共有幾種不同方式？選項(xiàng)：A、右圖正確，9種B、左圖正確，9種C、左圖正確，4種D、右圖正確，4種正確答案:【左圖正確，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è)？選項(xiàng)：A、圖2方案的算法設(shè)計(jì)思路：設(shè)定二重循環(huán)：循環(huán)變量i（問題的終點(diǎn)站編號），循環(huán)變量k（斷點(diǎn)位置控制），去計(jì)算問題的最優(yōu)值.時(shí)間復(fù)雜性為O(）B、圖1是將從i站到j(luò)站最小費(fèi)用問題劃分為2個(gè)子問題i到k和k到j(luò)的最小費(fèi)用和，且ikj，這些不同方式中的最小值還要同r(i,j)比較，最小者即為cost(i,j)C、圖2是將從1站到i站的最小費(fèi)用問題劃分為2個(gè)子問題即從第1站到第k站的最小費(fèi)用問題和從k站到i站的最小費(fèi)用問題。D、圖1方案的算法設(shè)計(jì)思路：設(shè)定三重循環(huán)：循環(huán)變量r（規(guī)?？刂疲h(huán)遍歷i（規(guī)模為r的問題個(gè)數(shù)控制，同時(shí)也是問題的首編號），循環(huán)變量k（斷點(diǎn)位置控制），去計(jì)算問題的最優(yōu)值,時(shí)間復(fù)雜性為O（）正確答案:【圖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)中找出。選項(xiàng)：A、03771013B、0336815C、037101315D、037101013正確答案:【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的最長公共子序列長度及最長公共子序列包含的符號選項(xiàng)：A、長度2“AB”B、長度1“C”C、長度2“AC”D、長度1“A”正確答案:【長度2“AC”】8、問題：下面是求最長公共子序列長度和構(gòu)造最優(yōu)解的算法?！尽恐械恼Z句缺失，請從如下選項(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】;}選項(xiàng)：A、(1)c[i][j]=c[i][j-1](2)c[i][j]=c[i-1][j](3)LCS(i-1,j,x,b)(4)LCS(i,j-1,x,b)B、(1)c[i][j]=c[i-1][j](2)c[i][j]=c[i][j-1](3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)C、(1)c[i][j]=c[i][j-1](2)c[i][j]=c[i-1][j](3)LCS(i,j-1,x,b)(4)LCS(i-1,j,x,b)D、(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)正確答案:【(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、問題：操場上擺放一行共n堆石頭，從左到右方向編號為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ù)雜性選項(xiàng)：A、T（n）=O（）S(n)=O(B、T（n）=O（）S(n)=O(C、T（n）=O（）S(n)=O(D、T（n）=O（）S(n)=O())))正確答案:【T（n）=O（）S(n)=O()】10、問題：可用動(dòng)態(tài)規(guī)劃算法解決的問題需要滿足幾個(gè)基本要素，從下面選項(xiàng)中找出這些基本要素選項(xiàng)：A、階段性B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、無后向性D、重復(fù)子問題正確答案:【最優(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]的遞歸定義。選項(xiàng)：A、B、C、D、正確答案:【#】12、問題：操場上擺放一行共n堆石頭，從左到右方向編號為1~n，石子的數(shù)目分別為p[1],……,p[n]，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過n-1次合并，最終合并為一堆。計(jì)算這n堆石子合并為一堆的最小得分。請根據(jù)題目要求，從如下選項(xiàng)中找出關(guān)于從第i堆到第j堆合并為一堆的最小得分m[i][j]的遞歸定義.選項(xiàng)：A、m[i][j]=0,if(i==j)B、m[i][j]=p[i],if(i==j)C、if（ij）m[i][j]=min(m[i][k]+m[k+1][j])+sum(i,j)這里i=kj，sum（i，j）是i堆到j(luò)堆石子的累加和。D、if（ij）m[i][j]=min(m[i][k]+m[k][j])+sum(i,j)這里i=kj，sum（i，j）是i堆到j(luò)堆石子的累加和。正確答案:【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ò)堆石子的累加和。】13、填空題：操場上擺放一行共4堆石頭，從左到右方向編號為1~4，各堆石子的數(shù)目分別為7,10,3,5，現(xiàn)要將石子有次序的合并為一堆，規(guī)定每次只能選相鄰的2堆合并為新的一堆，將新的一堆石子數(shù)記為該次合并的得分，經(jīng)過5次合并，最終合并為一堆。計(jì)算這6堆石子合并為一堆的最小得分正確答案:【50】14、填空題：現(xiàn)有一樓梯共8級臺階，有一小朋友一步可以邁出1、2或3級臺階，問小朋友有多少種不同的爬樓梯的方法正確答案:【81】第四單元測試1、問題：一個(gè)問題，針對某個(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è)反例是對的，哪個(gè)反例是錯(cuò)的，從如下選項(xiàng)中找到你的答案。選項(xiàng)：A、（1）對（2）錯(cuò)B、（1）對（2）對C、（1）錯(cuò)（2）錯(cuò)D、（1）錯(cuò)（2）對正確答案:【（1）錯(cuò)（2）對】2、問題：一個(gè)n位的10進(jìn)制正整數(shù)，使得刪除k位（kn）后剩余數(shù)字組成的正整數(shù)最小，用貪心算法實(shí)現(xiàn)該算法，問該問題的貪心策略是什么？也就是每次要?jiǎng)h除哪個(gè)數(shù)字？選項(xiàng)：A、每次從整數(shù)中刪去數(shù)字最大者B、每次從整數(shù)中找包含最高位的從左至右的一個(gè)最長的非遞減序列，將該序列的最后一位刪除C、每次刪除該整數(shù)的最高位數(shù)字D、貪心算法不能有效解決該問題正確答案:【每次從整數(shù)中找包含最高位的從左至右的一個(gè)最長的非遞減序列，將該序列的最后一位刪除】3、問題：某中學(xué)有一個(gè)開水房，只有一個(gè)供熱水龍頭，課間時(shí)，會有很多同學(xué)去排隊(duì)打開水，同學(xué)們的水瓶大小不一，每個(gè)同學(xué)打水時(shí)都會將自己的水瓶裝滿。管理開水房的師傅是個(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）選項(xiàng)：A、按照打水時(shí)間從大到小排隊(duì)，平均等待時(shí)間T=∑ti/n1=i=nB、按照打水時(shí)間從小到大排隊(duì)，平均等待時(shí)間T=∑ti/n1=i=nC、按照打水時(shí)間從大到小排隊(duì)，假定排隊(duì)后第i個(gè)人的打水時(shí)間是ti,平均等待時(shí)間T=∑(n-i+1)ti/n1=i=nD、按照打水時(shí)間從小到大排隊(duì)，假定排隊(duì)后第i個(gè)人的打水時(shí)間是ti,平均等待時(shí)間T=∑(n-i+1)ti/n1=i=n正確答案:【按照打水時(shí)間從小到大排隊(duì)，假定排隊(duì)后第i個(gè)人的打水時(shí)間是ti,平均等待時(shí)間T=∑(n-i+1)ti/n1=i=n】4、問題：哈夫曼編碼樹是用貪心算法解決的典型問題，分析該算法，回答如下問題，假定有n個(gè)字符生成的編碼樹，問編碼樹中的結(jié)點(diǎn)總數(shù)是多少？可能的最長的字符編碼是多少位？選項(xiàng)：A、2n個(gè)結(jié)點(diǎn)，n位編碼B、2n-1個(gè)結(jié)點(diǎn)n-1位編碼C、2n-1個(gè)結(jié)點(diǎn)n位編碼D、2n個(gè)結(jié)點(diǎn)n-1編碼正確答案:【2n-1個(gè)結(jié)點(diǎn)n-1位編碼】5、問題：下圖中A~F頂點(diǎn)分別代表6個(gè)村莊，圖中的邊代表村莊之間的距離，為了滿足這六個(gè)村莊相互通信的需要（任意兩個(gè)村莊有線路可達(dá)），需要架設(shè)通信線路，這里要求代價(jià)最小化（即線路總長度最?。?，請你分析問題找到代價(jià)最小的方案，并計(jì)算出線路總長度，從如下選項(xiàng)中找出答案。選項(xiàng)：A、線路總長度20B、線路總長度21C、線路總長度22D、線路總長度23正確答案:【線路總長度21】6、問題：一個(gè)問題，確定了某個(gè)貪心策略，如果用貪心算法能夠構(gòu)造出問題的最優(yōu)解，需要該問題具備哪兩個(gè)條件？選項(xiàng)：A、沒有重復(fù)子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、無后向性D、貪心選擇性質(zhì)正確答案:【最優(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算法，下面哪些描述是正確的？選項(xiàng)：A、設(shè)定一個(gè)頂點(diǎn)集合S，初始時(shí)，S={A}，每次從V-S中選擇頂點(diǎn)加入S，直到全部加入，算法結(jié)束。B、每次選擇加入S集合的頂點(diǎn)是從A頂點(diǎn)出發(fā)的最短路徑長度已知的頂點(diǎn)，也就是V-S集合中最短特殊路徑長度最小的頂點(diǎn)，通常算法中用dist[]數(shù)組記錄各頂點(diǎn)的最短特殊路徑長度。C、每次從V-S集合選擇加入S集合的頂點(diǎn)是V-S集合中的頂點(diǎn)同S集合的頂點(diǎn)連接邊最短的，通常算法中用dist[]數(shù)組記錄S集合中各頂點(diǎn)與V-S集合中各頂點(diǎn)的最短連接邊。D、每次選擇一個(gè)頂點(diǎn)加入S集合后，都要檢查是否需要更新dist[]數(shù)組元素的值正確答案:【設(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)解。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】9、問題：教材例題：多機(jī)調(diào)度問題，是用貪心算法求最優(yōu)解的一個(gè)例子，貪心策略是每次從剩余任務(wù)中選擇一個(gè)花費(fèi)時(shí)間最長的任務(wù)，安排在占用時(shí)間最少的機(jī)器上。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】10、問題：貪心算法中常包含排序算法，也就是排序是貪心算法的伴隨算法，有人這樣解釋其原因：貪心算法是根據(jù)貪心策略一步一步地選擇去構(gòu)造問題的解，排序就是按照要選擇的順序排列好，選擇時(shí)只需按照排好的順序選擇就可以了。主要目的就是方便選擇。該說法是否正確？選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】11、問題：貪心算法是以自底向上的方式構(gòu)造問題的最優(yōu)解選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】12、填空題：我國的貨幣單位是100元，50元，20元、10元、5元、2元、1元。有人到超市買了32元的商品，交給收銀員100元，問收銀員最少需要幾張貨幣就能完成找零錢？正確答案:【5】13、填空題：最優(yōu)分解問題：一個(gè)正整數(shù)分解為若干互不相同的自然數(shù)的和，使其乘積最大。使用貪心算法求將22這個(gè)數(shù)最優(yōu)分解后，取得的最大乘積是多少？正確答案:【1008】第五章單元測試1、問題：下面關(guān)于回溯法的描述中，不正確的是哪個(gè)?選項(xiàng)：A、回溯法可使用遞歸算法實(shí)現(xiàn)B、回溯法是以深度優(yōu)先的狀態(tài)生成樹法去搜索問題的解，并且能夠避免不必要搜索。C、回溯法解決的問題，其解通?？梢员磉_(dá)為n元組的形式D、回溯法，從解空間樹的根結(jié)點(diǎn)開始，當(dāng)搜索至葉子結(jié)點(diǎn)時(shí)，就找到了問題的解，算法結(jié)束。正確答案:【回溯法，從解空間樹的根結(jié)點(diǎn)開始，當(dāng)搜索至葉子結(jié)點(diǎn)時(shí)，就找到了問題的解，算法結(jié)束?！?、問題：下面描述不正確的是？選項(xiàng)：A、解空間樹的分類中，盡管子集樹的每個(gè)非葉子結(jié)點(diǎn)都有二個(gè)分支，但是不能把它稱為n叉樹。B、剪枝函數(shù)有二種，分別是約束函數(shù)和限界函數(shù)C、當(dāng)解空間樹是子集樹時(shí)，約束函數(shù)對0分支剪枝，限界函數(shù)對1分支剪枝。D、對解空間樹是n叉樹（或排列樹）來說，回溯法搜索時(shí)對每個(gè)分支使用的的剪枝條件（函數(shù)）是完全相同的。正確答案:【當(dāng)解空間樹是子集樹時(shí)，約束函數(shù)對0分支剪枝，限界函數(shù)對1分支剪枝?！?、問題：n皇后問題是可用回溯法解決的問題。下面描述不正確的是？選項(xiàng)：A、當(dāng)其解空間樹是n叉樹時(shí)，剪枝函數(shù)是任一列或任一（正反）對角線只能安排一個(gè)皇后。B、當(dāng)其解空間樹是排列樹時(shí)，剪枝函數(shù)是任一（正反）對角線只能安排一個(gè)皇后。C、算法搜索至葉子結(jié)點(diǎn)時(shí)，就找到了一種新的皇后安排方案，算法可找到所有可行的方案。D、兩種不同解空間樹的算法效率比較，排列樹的時(shí)間耗費(fèi)高于n叉樹正確答案:【兩種不同解空間樹的算法效率比較，排列樹的時(shí)間耗費(fèi)高于n叉樹】4、問題：0-1背包問題的回溯算法，下面的解釋不正確的是選項(xiàng)：A、解空間樹是子集樹B、左(1)分支的剪枝：當(dāng)選擇裝入背包的物品重量之和超過背包容量時(shí)就剪枝。C、右（0）分支的剪枝：已裝入背包內(nèi)的物品價(jià)值和+剩余物品裝剩余背包容量所能獲得的最大價(jià)值（物品可分割，即用背包問題的貪心算法求得的最大價(jià)值）當(dāng)前最優(yōu)值bestp,就剪枝.D、當(dāng)搜索至葉子結(jié)點(diǎn)時(shí)，一定是發(fā)現(xiàn)了到目前為止最好的解正確答案:【右（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)中找到正確答案選項(xiàng)：A、A對，B對B、A對，B錯(cuò)C、A錯(cuò)，B對D、A錯(cuò)、B錯(cuò)正確答案:【A對，B錯(cuò)】6、問題：符號三角形問題的回溯算法如下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)要求將紅色代碼去掉，保持算法功能不改變，需在【】添加下面哪段代碼？選項(xiàng)：A、if((counthalf)||(t*(t-1)/2-counthalf))B、if((count=half)(t*(t-1)/2-count=half))C、if((count=half)(t*(t+1)/2-count=half))D、if((counthalf)||(t*(t+1)/2-counthalf))正確答案:【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);【】}}}請將【】位置缺失的代碼補(bǔ)齊，從下面選項(xiàng)中找到答案。選項(xiàng)：A、sum-=a[i];B、sum-=a[i];backtrack(i+1);C、backtrack(i+1);D、backtrack(i+1);sum-=a[i];正確答案:【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】位置代碼缺失，請從如下選項(xiàng)中找到合適的代碼。選項(xiàng)：A、【1】i，【2】t，【3】ok=1B、【1】i，【2】t，【3】ok=0C、【1】t，【2】i，【3】ok=1D、【1】t，【2】i，【3】ok=0正確答案:【【1】t，【2】i，【3】ok=0】9、問題：符號三角形問題，其解空間樹是哪種？選項(xiàng)：A、排列樹B、子集樹C、n叉樹（這里n=2）D、不規(guī)則樹正確答案:【n叉樹（這里n=2）】10、問題：子集和問題：給定n個(gè)不同的正整數(shù)，已知其和大于c，要求找出一個(gè)子集使其和等于c。該問題除解空間樹是子集樹的回溯法外，還有解空間樹是排列樹的回溯算法，思考該問題，從如下選項(xiàng)中找到關(guān)于該算法設(shè)計(jì)的正確的描述。選項(xiàng)：A、當(dāng)解空間樹是排列樹時(shí)，搜索時(shí)，可以將從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑上的數(shù)看成是一個(gè)子集。B、剪枝條件:當(dāng)路徑上的數(shù)之和c時(shí)剪枝C、該算法搜索至排列樹的葉子結(jié)點(diǎn)（即第n層結(jié)點(diǎn)）時(shí)，就找到了一個(gè)解。D、數(shù)據(jù)預(yù)處理，首先必須將n個(gè)數(shù)按從小到大排序存放于x[1:n]，這樣可以提高該算法的搜索效率。正確答案:【當(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】是分支上的取值。選項(xiàng)：A、滿足隱約束函數(shù)和限界函數(shù)約束的所有x【k】的個(gè)數(shù)B、計(jì)算隱約束函數(shù)值的時(shí)間C、計(jì)算限界函數(shù)值的時(shí)間D、滿足顯約束的x【k】的個(gè)數(shù)。正確答案:【滿足隱約束函數(shù)和限界函數(shù)約束的所有x【k】的個(gè)數(shù)#計(jì)算隱約束函數(shù)值的時(shí)間#計(jì)算限界函數(shù)值的時(shí)間#滿足顯約束的x【k】的個(gè)數(shù)?！?2、問題：回溯法是在一顆已經(jīng)建立起來的解空間樹中實(shí)現(xiàn)深度優(yōu)先搜索的算法。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】13、問題：回溯法中，剪枝函數(shù)能夠剪掉的分支越多，算法效率就越高。因此，我們在設(shè)計(jì)回溯法時(shí)，就要設(shè)計(jì)剪枝函數(shù)能夠剪掉盡量多的分支。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】第六單元測試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)中找出答案。選項(xiàng)：A、（1）（3）（4）B、（1）（2）（3）C、（1）（2）（4）D、（2）（3）（4）正確答案:【（1）（2）（4）】2、問題：分支限界法中，擴(kuò)展出的孩子結(jié)點(diǎn)在入隊(duì)時(shí)，存儲該孩子結(jié)點(diǎn)的父結(jié)點(diǎn)的地址和左孩子標(biāo)志。其目的是什么？選項(xiàng)：A、為了計(jì)算最優(yōu)值B、為了確定其孩子結(jié)點(diǎn)在隊(duì)列中的位置C、為了構(gòu)造最優(yōu)解D、為了方便判定是否已搜索到達(dá)葉子層正確答案:【為了構(gòu)造最優(yōu)解】3、問題：在隊(duì)列式分支限界法解決裝載問題時(shí)，為什么在其改進(jìn)算法中，每次進(jìn)入左分支都要檢查更新bestw，而不是等搜索到達(dá)葉子結(jié)點(diǎn)時(shí)才去更新bestw，其目的是什么？選項(xiàng)：A、為了及早使右（0）分支剪枝函數(shù)生效。B、為了及早使左（1）分支剪枝函數(shù)生效C、為了計(jì)算最優(yōu)值D、為了方便構(gòu)造最優(yōu)解正確答案:【為了及早使右（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í)，會將該葉子結(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)先級的定義是限界函數(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)先級都不大于該葉子結(jié)點(diǎn)的優(yōu)先級，葉子結(jié)點(diǎn)的優(yōu)先級等于最優(yōu)值，算法結(jié)束，無論優(yōu)先隊(duì)列是否為空。根據(jù)其正確與否，給出答案選項(xiàng)：A、（1）正確，（2）錯(cuò)誤B、（1）正確，（2）正確C、（1）錯(cuò)誤，（2）錯(cuò)誤D、（1）錯(cuò)誤，（2）正確正確答案:【（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;}選項(xiàng)：A、【1】in+1,【2】besp=cp+p[i]B、【1】i!=n+1,【2】cw=cw+w[i]C、【1】i!=n,【2】cw=cw+w[i]D、【1】in,【2】besp=cp+p[i]正確答案:【【1】in+1,【2】besp=cp+p[i]】6、問題：閱讀該單元測試中關(guān)于0-1背包問題的優(yōu)先隊(duì)列分支限界算法代碼，問左分支的剪枝條件是什么？右分支的剪枝條件是什么？從代碼中找到命令行，使用原代碼回答問題。選項(xiàng)：A、左分支：wt=c,右分支：upbestpB、左分支：cp+p[i]bestp,右分支：upbestpC、左分支：cp+p[i]bestp,右分支：wt=cD、左分支：wt=c,右分支：cp+p[i]bestp正確答案:【左分支：wt=c,右分支：upbestp】7、問題：優(yōu)先隊(duì)列式分支限界法解決0-1背包問題時(shí)，下面描述正確的是選項(xiàng)：A、左孩子結(jié)點(diǎn)的優(yōu)先級等于父結(jié)點(diǎn)的優(yōu)先級B、左孩子結(jié)點(diǎn)相應(yīng)的背包內(nèi)物品的價(jià)值等于父結(jié)點(diǎn)相應(yīng)的背包內(nèi)的物品價(jià)值C、右孩子結(jié)點(diǎn)的優(yōu)先級等于父結(jié)點(diǎn)的優(yōu)先級D、右孩子結(jié)點(diǎn)相應(yīng)的背包內(nèi)物品的價(jià)值等于父結(jié)點(diǎn)相應(yīng)的背包內(nèi)的物品價(jià)值正確答案:【左孩子結(jié)點(diǎn)的優(yōu)先級等于父結(jié)點(diǎn)的優(yōu)先級#右孩子結(jié)點(diǎn)相應(yīng)的背包內(nèi)物品的價(jià)值等于父結(jié)點(diǎn)相應(yīng)的背包內(nèi)的物品價(jià)值】8、問題：回溯法與分支限界法的空間復(fù)雜度是相同的，都是O(h(n)),h(n)是解空間樹的深度。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(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)志。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】10、填空題：下面是一個(gè)布線問題,S表示布線的起點(diǎn)，O表示布線的終點(diǎn)，假定布線只能垂直、或水平布線，從一個(gè)點(diǎn)按照上、下、左、右的優(yōu)先順序可往四個(gè)方向布線，“#是障礙不能通過。已知從一個(gè)位置向其上、下、左、右四個(gè)相鄰位置布線的線路長度為1。使用隊(duì)列式分支限界法解決該問題，問從S到O的最短布線長度？###S##o#######正確答案:【8】第七單元測試1、問題：有這樣一種算法，運(yùn)行一次可能找不到問題的解，運(yùn)行多次就一定能找到問題的解，且運(yùn)行次數(shù)有界，這種算法是？選項(xiàng)：A、拉斯維加斯算法B、蒙特卡洛算法C、舍伍德算法D、數(shù)值概率算法正確答案:【拉斯維加斯算法】2、問題：有這樣一種算法，運(yùn)行一次一定能找到問題的解，有時(shí)不知其是否正確，可以確定的是該解高概率（大于50%）是正確的。這種算法是？選項(xiàng)：A、拉斯維加斯算法B、蒙特卡洛算法C、舍伍德算法D、數(shù)值概率算法正確答案:【蒙特卡洛算法】3、問題：有一個(gè)問題的蒙特卡洛算法，給定一個(gè)實(shí)例，已知運(yùn)行一次其答案是錯(cuò)誤的概率是1/8,現(xiàn)運(yùn)行k次該算法，其答案一直不變，問該答案的正確率是？選項(xiàng)：A、(1/8)^kB、7/8C、1-(7/8)^kD、1-(1/8)^k正確答案:【1-(1/8)^k】4、問題：一致的p正確的偏y0的蒙特卡洛算法，下面解釋不正確的是?選項(xiàng)：A、運(yùn)行蒙特卡洛算法p次，至少有一次是正確的。B、一致是指蒙特卡洛算法對于一個(gè)實(shí)例，其正確解是唯一的。C、當(dāng)正確解是y0,而蒙特卡洛算法得到的解不是y0D、猜硬幣的正反面問題，因?yàn)椴乱淮握_的概率是50%，所以不能使用蒙特卡洛算法解決。正確答案:【運(yùn)行蒙特卡洛算法p次，至少有一次是正確的?！?、問題：pollard算法找到一個(gè)整數(shù)因子的時(shí)間復(fù)雜性是？選項(xiàng)：A、O(n)B、O(logn)C、O(D、O())正確答案:【O()】6、問題：n=12皇后問題的三種不同的解決方案：回溯法、拉斯維加斯算法、拉斯維加斯算法+回溯法。對于給定的一個(gè)實(shí)例，(1)平均耗費(fèi)時(shí)間最少的是那種方案？，(2)平均耗費(fèi)時(shí)間最多的是那種方案？選項(xiàng)：A、(1)回溯法(2)拉斯維加斯+回溯法B、(1)回溯法(2)拉斯維加斯C、(1)拉斯維加斯(2)回溯法D、(1)拉斯維加斯+回溯(2)回溯法正確答案:【(1)拉斯維加斯+回溯(2)回溯法】7、問題：在分治法中講到快速排序，如果每次使用partion函數(shù)導(dǎo)致分組出現(xiàn)嚴(yán)重不平衡情況下，算法效率不高，最壞情況下的時(shí)間復(fù)雜度為O（n^2）,通過改造partition函數(shù)，也就是每次隨機(jī)選擇一個(gè)元素作為劃分基準(zhǔn)，這樣會很好地改善算法的性能，這種算法思想是？選項(xiàng)：A、拉斯維加斯算法B、蒙特卡洛算法C、舍伍德算法D、數(shù)值概率算法正確答案:【舍伍德算法】8、問題：舍伍德算法思想是通過引入隨機(jī)化策略將確定性算法改造為隨機(jī)算法，打破原來確定性算法在某些實(shí)例情況下，其時(shí)間復(fù)雜性必然遠(yuǎn)高于平均時(shí)間復(fù)雜性的規(guī)律。下面哪些算法可以應(yīng)用舍伍德算法思想？選項(xiàng)：A、快速排序算法B、線性時(shí)間選擇算法C、歸并排序D、跳躍表正確答案:【快速排序算法#線性時(shí)間選擇算法#跳躍表】9、問題：計(jì)算機(jī)中的隨機(jī)數(shù)是偽隨機(jī)的，因?yàn)樗蔷哂幸欢ㄒ?guī)律的，是按公式計(jì)算出來的。該說法正確嗎？選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】10、問題：素?cái)?shù)測試問題的蒙特卡洛算法，n是一個(gè)待判定正整數(shù)。當(dāng)n是素?cái)?shù)時(shí)，有時(shí)會被判定為非素?cái)?shù)。該說法正確嗎?選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】11、問題：有人說可以設(shè)計(jì)蒙特卡洛算法去猜硬幣的反正面問題，該說法是否正確？選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(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】第八單元測試1、問題：下面哪個(gè)問題不是NPC問題選項(xiàng)：A、最大團(tuán)問題B、子集和問題C、旅行售貨員問題D、最小生成樹問題正確答案:【最小生成樹問題】2、問題：請從下列選項(xiàng)中找出正確的P問題與NP問題的關(guān)系選項(xiàng)：A、B、C、D、正確答案:【】3、問題：NP問題是確定性算法不能在多項(xiàng)式時(shí)間復(fù)雜性解決的可判定問題選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【錯(cuò)誤】4、問題：一個(gè)NPC問題，首先是NP問題，另外所有的其他NP問題都能在多項(xiàng)式時(shí)間復(fù)雜性規(guī)約為該問題選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】5、問題：研究NPC問題的意義，一旦一個(gè)NPC問題找到了多項(xiàng)式時(shí)間復(fù)雜性的確定性算法，那么所有的NPC問題都找到了多項(xiàng)式時(shí)間復(fù)雜性的確定性算法。選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】6、問題：NP難問題未必是NP問題選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】7、問題：一個(gè)人正站在門口，讓你猜他（她）是否要出門？，該問題是不可判定問題，該觀點(diǎn)是否正確？選項(xiàng)：A、正確B、錯(cuò)誤正確答案:【正確】客觀題試卷1、問題：如下哪種表示不是歸并排序算法時(shí)間復(fù)雜性選項(xiàng)：A、Ω（nlogn）B、O（nlogn）C、o(nlogn)D、θ（nlogn）正確答案:【o(nlogn)】2、問題：最優(yōu)子結(jié)構(gòu)性質(zhì)是選項(xiàng)：A、問題可以分解為性質(zhì)相同的子問題B、問題的最優(yōu)解可通過性質(zhì)相同的子問題的最優(yōu)解合并而成C、問題的最優(yōu)解可通過一步步局部最優(yōu)的選擇來獲得。D、子問題可同原問題性質(zhì)不同，但是原問題的最優(yōu)解可通過子問題的最優(yōu)解合并而成正確答案:【問題的最優(yōu)解可通過性質(zhì)相同的子問題的最優(yōu)解合并而成】3、問題：有一算法的時(shí)間復(fù)雜性遞歸定義:T(n)=8T(n/2)+nlognifn1,T(1)=1;問T(n)=？選項(xiàng)：A、O（nlogn)B、C、D、正確答案:【】4、問題：哈夫曼編碼樹算法中用優(yōu)先隊(duì)列（堆）存儲生成的結(jié)點(diǎn)，n個(gè)字符的哈夫曼編碼樹算法時(shí)間復(fù)雜性為選項(xiàng)：A、B、C、D、正確答案:【】5、問題：下列哪些問題不能用貪心算法求最優(yōu)解選項(xiàng)：A、最小生成樹B、單源最短路徑C、最優(yōu)二叉搜素樹D、哈夫曼編碼樹正確答案:【最優(yōu)二叉搜素樹】6、問題：在下列算法中，可求解n皇后問題的算法是選項(xiàng)：A、數(shù)值概率算法B、舍伍德算法C、拉斯維加斯算法D、蒙特卡羅算法正確答案:【拉斯維加斯算法】7、問題：爬樓梯問題：有一樓梯共n級臺階，有一小朋友一次可以邁1，2或3級臺階，求共有多少不同的走法走完這n級臺階。回答該問題最適合使用哪種算法？選項(xiàng)：A、分治法B、回溯法C、貪心算法D、動(dòng)態(tài)規(guī)劃正確答案:【動(dòng)態(tài)規(guī)劃】8、問題：給定n個(gè)任務(wù)接受同一臺機(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)解？選項(xiàng)：A、以服務(wù)時(shí)間ti從小到大安排B、以di-ti從小到大安排C、以截止時(shí)間di從小到大安排D、以上都不可能正確答案:【以截止時(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]的遞歸定義選項(xiàng)：A、m[i][j]=max(m[i][k]+m[k+1][j]+a[i]*a[k]*a[j]),ikj,if(j-i1).m[i][j]=0;if(j-i==1).B、m[i][j]=max(m[i][k]+m[k+1][j]+a[k-1]*a[k]*a[k+1]),ikj,if(j-i1).m[i][j]=0;if(j-i==1)C、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)D、m[i][j]=max(m[i][k]+m[k][j]+a[k-1]*a[k]*a[k+1]),ikj,if(j-i1).m[i][j]=0;if(j-i==1)正確答案:【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)選項(xiàng)：A、葉子結(jié)點(diǎn)要加入隊(duì)列B、如果需要，隊(duì)列中同層結(jié)點(diǎn)后可加入特殊標(biāo)志與下層結(jié)點(diǎn)區(qū)分開C、結(jié)點(diǎn)沒有優(yōu)先級定義D、算法中循環(huán)的結(jié)束條件是當(dāng)隊(duì)列為空時(shí)。正確答案:【葉子結(jié)點(diǎn)要加入隊(duì)列】11、問題：回溯法和分支限界法的主要區(qū)別是選項(xiàng)：A、解空間樹不同B、約束條件不同C、搜素方式不同D、求解目標(biāo)不同正確答案:【搜素方式不同#求解目標(biāo)不同】12、問題：P問題、NP問題、NPC問題，下列哪些解釋是正確的？選項(xiàng)：A、P問題是確定性算法多項(xiàng)式時(shí)間復(fù)雜性解決的可判定問題B、NP問題是確定性算法不能在多項(xiàng)式時(shí)間復(fù)雜性解決的可判定問題C、PíNPD、NPCìNP正確答案:【P問題是確定性算法多項(xiàng)式時(shí)間復(fù)雜性解決的可判定問題#PíNP】13、問題：快速排序算法，其時(shí)間復(fù)雜性是，而其平均時(shí)間復(fù)雜性是，下面哪些方法可以改善快速排序算法的性能？選項(xiàng)：A、拉斯維加斯算法B、蒙特卡洛算法C、洗牌算法D、舍伍德算法正確答案:【洗牌算法#舍伍德算法】14、問題：下面哪些算法是解決單源最短路徑問題的有效算法？選項(xiàng)：A、貪心算法B、分治法C、優(yōu)先隊(duì)列分支限界法D、隊(duì)列式分支限界法正確答案:【貪心算法#優(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)中找到正確的描述選項(xiàng)：A、將一個(gè)規(guī)模為n的問題分解為兩個(gè)子問題B、將一個(gè)規(guī)模為n的問題分解為一個(gè)子問題C、該算法的時(shí)間復(fù)雜度是O（log（n）)D、該算法的時(shí)間復(fù)雜度是O（n）正確答案:【將一個(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)？選項(xiàng)：A、編碼長度為n-1位的有二個(gè)字符B、編碼長度為1到n-2的字符都只有一個(gè)C、編碼長度為n-1的有一個(gè)字符D、編碼長度為1到n-2的字符可能超過1個(gè)。正確答案:【編碼長度為n-1位的有二個(gè)字符#編碼長度為1到n-2的字符都只有一個(gè)】17、問題：1、最大團(tuán)問題是指求無向圖中任意兩個(gè)頂點(diǎn)都有連接邊的子圖，且頂點(diǎn)個(gè)數(shù)最多。現(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;b