算法理論知識考核試題一、選擇題1.2n=O(100n2)[單選題]*A.正確B.錯誤√2.10=θ(log10)[單選題]*A.正確√B.錯誤3.2n=O(3n)_____。（）[單選題]*A.正確√B.錯誤4.logn2=θ(logn+5)[單選題]*A.正確√B.錯誤5.針對順序查找算法，影響它時間復雜度的因素只有算法的輸入序列()[單選題]*A.正確B.錯誤√6.n!的時間復雜度為O(n)[單選題]*A.正確√B.錯誤7.遞歸是指自己間接或直接調用自身[單選題]*A.正確√B.錯誤8.算法的基本特征有（）[多選題]*A.輸入√B.輸出√C.有限性√D.確定性√E.可行性√9.漸進復雜性的含義是（）情況下的復雜性。[單選題]*A.在最佳輸入情況下B.問題規模趨向于無窮√C.在最壞輸入情況下D.平均各種輸入之后10.n個連續自然數a1...an連加和問題算法（利用等差數列求和公式）的輸入可以是什么（）。[多選題]*A.a1，n√B.an,n√C.a1,an√D.a1,an,n√11.平均時間復雜度是指（）[單選題]*A.各種情況時間復雜度按概率的加權平均√B.最好情況和最壞情況的時間復雜度的算術平均C.各種情況時間復雜度按概率的算術平均D.出現可能性最高的情況下的時間復雜度12.算法的常見描述方式不包括（）[單選題]*A.代碼B.甘特圖√C.偽代碼D.流程圖13.算法的基本特性不包括（）[單選題]*A.先進性√B.有窮性C.有輸入輸出D.無二義性14.階乘問題求n!算法的時間復雜度為（）。[單選題]*A.n√B.n!C.2nD.n^215.二分搜索（二分查找）算法的時間復雜度是（）。[單選題]*A.nB.logn√C.n^2D.2n16.漢諾塔問題的時間復雜度是（）。___。（）[單選題]*A.n!B.2^n√C.2nD.logn17.下述描述算法的方式采用的是算法的哪種描述方式（）？算法：gcd(m,n)輸入：非負整數m,n，其中m,n不全為0輸出：m與n的最大公約數1.whilem>0do2.r←nmodm3.n←m4.m←r5.returnn[單選題]*A.自然語言B.程序流程圖C.偽碼√D.程序設計語言18.背包問題的算法設計策略是（）[單選題]*A.重量小的優先裝B.價值大的優先裝C.單位重量價值大的優先裝√D.以上都不對19.調度問題的算法設計策略是（）[單選題]*A.加工時間短的優先安排√B.加工時間長的優先安排C.等待時間短的優先安排D.以上都不對20.n個元素的冒泡排序代碼如下：defbubble_sort(arr):foriinrange(len(arr)-1):forjinrange(len(arr)-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr請分析算法的時間復雜度，用O表示（）[單選題]*A.O(1)B.O(n)C.O(n的平方)√D.O(nlogn)21.百元買白雞問題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，則翁、母、雛各幾何？設計一算法，則該算法的輸入是（）[單選題]*A.100元B.100只雞C.各種雞的單價D.無需任何輸入√22.下面算法最好情況下的時間復雜度___，最壞情況下的時間復雜度為___defbubble_sort(nums):foriinrange(len(nums)-1):swap_flag=False#改進后的冒泡，設置一個交換標志位forjinrange(len(nums)-i-1):ifnums[j]>nums[j+1]:nums[j],nums[j+1]=nums[j+1],nums[j]swap_flag=Trueifnotswap_flag:returnnums#若沒有元素交換，則表示已經有序returnnums[單選題]*A.O(n)、O(n2)√23.以下遞歸程序fun(5,0)輸出的第一個元素是___，求解過程中最大層次為___deffun(i,d):if(i>1andi%2!=0):fun(i-i//2,d+1)if(i>1):fun(i//2,d+1)（）[單選題]*A.1、4√24.斐波那契數列的第1項為1，第2項為2，以后每一項等于前面兩項之和，則第6項為___[單選題]*A.13√25.冒泡排序時間復雜度是___，堆排序時間復雜度是___。[單選題]*A.n2、nlogn√26.遞歸算法必須具備的兩個條件是___和_____。（）[單選題]*A.邊界條件或停止條件、遞推方程或遞歸方程√27.求遞推方程得到的解是___。（）[單選題]*A.O(nlogn)√28.求遞推方程得到的解是___。[單選題]*A.O(logn)√29.求遞推方程的解是___。（）[單選題]*A.O(n的平方)√30.求遞推方程得到的解是（）[單選題]*A.O(logn)√31.求遞推方程的解是（）[單選題]*A.O(n^2)√32.物品可以切割的背包問題的最佳貪心策略不一定能保證裝入背包的物品總價值最大。（）[單選題]*正確錯誤√33.設字符m1，m2，…m10的查閱頻率依次為：0.05，0.01，0.01，0.10，0.03，0.17，0.02，0.24，0.31，0.06。試構造對應的哈夫曼(Haffman)編碼，并畫出相應的編碼樹，同時寫出ml,m2,…m10的編碼。（）[單選題]*A.每個字符的編碼為從根節點到該字符所在葉子結點的路徑上的0,1組成的串?！?4.在10000個元素中找到前100個最大的元素，如果使用以下某個數據結構作為輔助，比較合適的是。（）[單選題]*A.堆√B.并查集C.循環鏈表D.哈希表35.給定下面的有向、連通帶權圖用dijkstra算法，找從源點1到其他各個頂點的最短路徑。算法運行若干步以后，得到各數據結構的數據如下（數組下標從1開始，表示頂點編號）：下標11223456788S11010110dist028163311pre01217147根據當前狀態，可判斷從初始狀態到當前狀態已經做了（）次貪心選擇。（）[單選題]*A.1B.2C.3D.4√36.用Prim算法求解上圖的最小生成樹，初始時，集合S={a}，集合V-S={b,c,d,e,f,g}，第六步貪心選擇的邊是（）。（）[單選題]*A.（a,b）B.（c,d）√C.（b,c）D.（c,f）37.用Prim算法求解上圖的最小生成樹，初始時，集合S={a}，集合V-S={b,c,d,e,f,g}，第三步貪心選擇的邊是（）。（）[單選題]*A.（a,b）B.（b,c）C.（c,d）D.（c,f）√38.用Prim算法求解上圖的最小生成樹，初始時，集合S={a}，集合V-S={b,c,d,e,f,g}，第一步貪心選擇的邊是（）。（）[單選題]*A.（a,b）√B.（b,c）C.（c,d）D.（c,f）39.用Kurskal算法求解上圖的最小生成樹，第一步貪心選擇的邊是（）。（）[單選題]*A.（a,b）B.（b,c）C.（c,g）D.（c,f）√40.給定一個有向連通帶權圖G=(V,E),n個頂點,e條邊,Dijsktra算法的時間復雜度為()。（）[單選題]*A.O(n2)√B.O(n3)C.O(eloge)D.O(nlogn)41.背包問題:n個物品和1個背包。對物品i,其價值為vi,重量為wi,背包的容量為W。如何選取物品裝入背包,使背包中所裝入的物品的總價值最大?物品可以分割。該問題的貪心策略是()。（）[單選題]*A.重量小的優先裝入背包B.體積小的優先裝入背包C.價值大的優先裝入背包D.單位重量的價值大的優先裝入背包√42.調度問題:有n個客戶帶來n項任務,每項加工時間已知,設為ti,i=1,2,…,n。從0時刻開始,陸續安排到一臺機器上加工。每個任務的完成時間是從0時刻到該任務加工完成的時間。為了使盡可能多的客戶滿意,我們希望找到是的總等待時間最少的調度方案。該問題的貪心策略是()。（）[單選題]*A.加工時間長的優先安排B.加工時間短的優先安排√C.完成時間早的優先安排D.等待時間長的優先安排43.找零錢問題的貪心策略是()。（）[單選題]*A.面值大的錢幣優先找出B.面值小的錢幣優先找出C.面值小于待找錢數且面值最大的優先找出√D.以上都不對44.物品不可拆開的最優裝載問題的貪心策略是()。（）[單選題]*A.體積大的集裝箱優先裝B.體積小的集裝箱優先裝C.重量大的集裝箱優先裝D.重量小的集裝箱優先裝√45.會場安排問題的最好的貪心策略是()。（）[單選題]*A.在不沖突的情況下，開始時間早的優先安排B.在不沖突的情況下，使用時間短的優先安排C.在不沖突的情況下，使用時間長的優先安排D.在不沖突的情況下，結束時間早的優先安排√46.調度問題的算法設計策略是（）。（）[單選題]*A.加工時間短的優先安排√B.加工時間長的優先安排C.等待時間短的優先安排D.以上都不對47.以下問題中，哪些問題的分治算法消耗的時間與輸入序列無關。（）[單選題]*A.二分查找B.合并排序√C.快速排序D.最小值問題48.有關2個n位大整數乘法問題說法正確的是（）。（）[多選題]*A.將兩個n位大整數分解為4個規模大致相等的n/2位整數的整數乘法問題√B.遞歸解決4個子問題√C.子問題的解需要歸并成原問題的解√D.子問題的解本身就是原問題的解49.分治算法的步驟有（）。（）[多選題]*A.分解√B.治理√C.遞歸D.合并50.分治算法的思想是（）。（）[多選題]*A.將規模較大的問題劃分為規模較小的相同子問題√B.子問題之間相互獨立√C.子問題之間不相互獨立D.遞歸解決劃分得到的子問題√E.將子問題的解歸并得到原問題的解√51.大整數A和B的乘法,將A分成位數大致相等的兩部分A1和A2，將B分成位數大致相等的兩部分B1和B2,以下描述正確的是()。（）[多選題]*A.子問題的解歸并為原問題解的方法為:A×B=10nA1B1+10n/2(A1B2+A2B1)+A2B2√B.子問題的解歸并為原問題解的方法為:A×B=10nA1B1+10n/2((A1-A2)(B2-B1)+A1B1+A2B2)+A2B2√C.子問題的解歸并為原問題解的方法為:A×B=10nA1B1+10n/2((A1+A2)(B1+B2)-A1B1-A2B2)+A2B2√D.以上方法都不對。52.關于快速排序分治算法時間復雜度描述正確的是()。（）[多選題]*A.快速排序分治算法最好情況下的時間復雜度為O(nlogn).√B.快速排序分治算法最壞情況下的時間復雜度為O(n2).√C.快速排序分治算法平均情況下的時間復雜度為O(n2).D.二快速排序分治算法平均情況下的時間復雜度為O(nlogn).√53.有關快速排序的分治算法描述正確的是()。（）[多選題]*A.快速排序A[left,right],選取基準元素的方法,將待排序元素分解為兩個子問題。√B.快速排序基準元素的選取可以是待排序元素中的任何一個元素。√C.快速排序劃分的兩個子問題規模大致相等。D.快速排序A[left,right],遞歸算法的邊界條件是left≥right√54.關于二分查找時間復雜度描述正確的是()。（）[多選題]*A.二分查找算法最好情況下的時間復雜度為O(1).√B.二分查找算法最壞情況下的時間復雜度為O(n).C.二分查找算法最壞情況下的時間復雜度為O(logn).√D.二分查找算法平均情況下的時間復雜度為O(logn).√55.有關合并排序的分治算法描述正確的是()。（）[多選題]*A.合并排序A[left,right]的元素,采用的分解方法是(left+right)/2。√B.合并排序A[left,right]的元素,采用的分解方法是(right-left)/2。C.合并排序A[left,right]的元素,需要治理規模大致等于(right-left+1)/2的兩個子問題?！藾.合并排序需要將兩個有序的子序列歸并成一個有序的子序列?！?6.有關循環賽日程表分治算法描述正確的是()。（）[多選題]*A.循環賽日程表給定2k個運動員,采用2k/2的方法將運動員分成兩組?！藼.循環賽日程表算法先安排組內的賽程,再安排兩組對打?！藽.循環賽日程表算法的邊界條件是兩個運動員,一天的比賽?！藾.循環賽日程表算法為2k個運動員安排了2k-1天的比賽。57.下述關于二分查找(折半查找)算法描述正確的是()。（）[多選題]*A.二分查找是在任意給定的n個元素序列中查找指定元素。B.二分查找的序列為A[left,right],分解操作為:(right-left)/2C.二分查找根據比較的結果,好的情況是相等,算法結束。壞的情況是進入其中一個子問題繼續查找?！藾.若二分查找的序列為A[left,right],用遞歸來解決子問題,則邊界條件是left>right?！?8.分治算法核心就是分而治之,其中的“治”描述正確的是()。（）[多選題]*A.分治法通過治理小問題來治理大問題。√B.分治法遞歸治理小問題?！藽.分治法需要將子問題的解歸并成大問題的解。√D.治理子問題時,會有重復性治理子問題的現象。59.分治算法的基本思想描述正確的是()。（）[多選題]*A.分治法將規模大的問題分解成規模較小的問題解決。√B.分治法劃分的小問題相互重疊。C.分治法一般采用遞歸的方法解決子問題?！藾.分治法劃分的小問題規模小到一定程度時容易解決?！?0.根據下面斐波那契數列的遞歸算法，可知斐波那契數列的第n項的遞歸式為（）。defFibonacci(intnum):if(num==0||num==1):returnnumreturnFibonacci(num-1)+Fibonacci(num-2)。（）[單選題]*A.Fibonacci(n)=0當n=0時B.Fibonacci(n)=1當n=1時C.Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)當n〉1時√D.Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3)當n〉1時61.下面代碼為求n！的遞歸算法，該代碼反應的n!問題遞歸實現的停止條件（邊界條件）為（）。（）deffun(n):if(n==1):return1else:returnfun(n-1)*n[單選題]*A.n!=1當n=0時B.n!=1當n=1時√C.n!=1當n〈1時D.n!=1當n〈=1時62.以下哪個問題的時間復雜度與輸入序列有關（）。（）[單選題]*A.二分查找√B.最小值問題C.合并排序D.以上都不對63.以下函數的功能是（）defQ(R,low，high):if(low<high):#僅當區間長度大于1時才須排序pivotpos=Partition(R,low,high)#劃分后的基準元素所對應的位置Q(R,low,pivotpos-1)#對左區間遞歸排序Q(R,pivotpos+1,high)#對右區間遞歸排序[單選題]*A.二分查找B.二分求最值C.合并排序D.快速排序√64.以下代碼功能為合并排序，請根據注釋按照數順序選擇合適的語句填入對應的括號。defMergeSort(A，low，high):if(low<high):（）#分解（）#遞歸序列左半部分（）#遞歸序列右半部分Merge(A,low,middle,high)#子問題的解合并成原問題的解[單選題]*A.middle=(high-low)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);B.middle=(low+high)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);√C.middle=(low+high)/2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);D.middle=(high-low)/2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);65.棋盤覆蓋問題的分解方法為（）。（）[單選題]*A.B.C.√D.以上分解的方法都不對66.合并排序的分治算法時間復雜度的是()。（）[單選題]*A.O(logn)B.O(nlogn)√C.D.67.解決給定的5個矩陣連乘問題：矩陣A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3），設m[i][j]表示Ai...Aj的最優計算次序對應的乘法計算次數（最優值），P為存儲矩陣行列的數組，其中P[i]是第i個矩陣的列、第i-1個矩陣的行。求解最優值遞歸關系是為：，根據該遞歸關系式，求解過程中得到下面最優決策的二維表：由此，可得上述5個矩陣連乘的最優計算次序為（）。（）[單選題]*A.（A1（A2（A3（A4A5））））B.（（A1A2）（A3（A4A5）））C.（（A1A2）（（A3A4）A5））D.（A1（（A2（A3A4））A5））√68.關于動態規劃和回溯法的區別，以下表述不正確的是。（）[單選題]*A.動態規劃和回溯法都可以用來求解最優化問題，但回溯法是基于枚舉解的思想，動態規劃則是基于構造子問題最優值關系的方式B.在遇到重疊子問題的時候，動態規劃思想會使用存儲最優值的方式直接排除，而回溯法一般做法是設法避環和剪枝，降低其影響C.在求解相同問題時，動態規劃必然比回溯法浪費空間，但是更節約時間√69.關于動態規劃與分治法的區別，表述不正確的是。（）[單選題]*A.動態規劃劃分的子問題一般具有重疊子問題，分治法則通?；ゲ幌嘟籅.動態規劃建立在描述子問題最優值關系的狀態轉移方程基礎上，分治法一般不需要建立類似的最優值之間的數量關系C.分治法能寫成遞歸形式，動態規劃不能寫成遞歸形式√D.動態規劃一般用來求解最優化問題，分治法多不用于求解最優化問題，70.矩陣連乘問題中，A1矩陣大小是100*5,A2矩陣大小為5*30，A3矩陣大小為30*10，則乘法次序(A1*A2)*A3需要的乘法次數是。（）[單選題]*A.15000B.30000C.45000√D.45000000071.規模為5矩陣連乘問題,計算次序有()種。（）[單選題]*A.10B.12C.14√D.1672.根據下面斐波那契數列的遞歸算法，可知斐波那契數列的第n項的遞歸式為（）。defFibonacci(intnum):if(num==0||num==1):returnnumreturnFibonacci(num-1)+Fibonacci(num-2)。（）[單選題]*A.Fibonacci(n)=0當n=0時B.Fibonacci(n)=1當n=1時C.Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)當n〉1時√D.Fibonacci(n)=Fibonacci(n-2)+Fibonacci(n-3)當n〉1時73.下面代碼為求n！的遞歸算法，該代碼反應的n!問題遞歸實現的停止條件（邊界條件）為（）。（）deffun(n):if(n==1):return1else:returnfun(n-1)*n[單選題]*A.n!=1當n=0時B.n!=1當n=1時√C.n!=1當n〈1時D.n!=1當n〈=1時74.合并排序的空間復雜度為()。（）[單選題]*A.θ(logn)B.θ(n)√C.θ(nlogn)D.θ(n*n)75.以下哪個問題的時間復雜度與輸入序列有關（）。（）[單選題]*A.二分查找√B.最小值問題C.合并排序D.以上都不對76.以下函數的功能是（）defQ(R,low，high):if(low<high):#僅當區間長度大于1時才須排序pivotpos=Partition(R,low,high)#劃分后的基準元素所對應的位置Q(R,low,pivotpos-1)#對左區間遞歸排序Q(R,pivotpos+1,high)#對右區間遞歸排序[單選題]*A.二分查找B.二分求最值C.合并排序D.快速排序√77.以下代碼功能為合并排序，請根據注釋按照數順序選擇合適的語句填入對應的括號。defMergeSort(A，low，high):if(low<high):（）#分解（）#遞歸序列左半部分（）#遞歸序列右半部分Merge(A,low,middle,high)#子問題的解合并成原問題的解。（）[單選題]*A.middle=(high-low)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);B.middle=(low+high)/2;MergeSort(A,low,middle);MergeSort(A,middle+1,high);√C.middle=(low+high)/2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);D.middle=(high-low)/2;MergeSort(A,middle+1,high);MergeSort(A,low,middle);78.矩陣連乘問題中有多個矩陣相乘，問題是安排矩陣相乘的先后順序，使總乘法次數最少，例如有[A][B]C三個矩陣，則可行的順序有ABC\ACB\CAB\CBA\BAC\BCA六個。（）[單選題]*正確錯誤√79.以動態規劃求解0-1背包問題，背包容量可以是任意實數。（）[單選題]*正確錯誤√80.有關矩陣連乘問題說法正確的是()。（）[多選題]*A.矩陣Ai...Aj連乘,其中Ak的行列為(pk×qk),k=i,i+1,...,j,其結果矩陣的行列為(pi×qj)?！藼.n個矩陣連乘A1...An,其子問題為Ai...Aj連乘,1≤i≤j≤n,其中i=j表示規模為1的子問題,其需要的乘法次數為0?！藽.設矩陣Ai...Aj連乘最少的乘法次數為c[i][j],矩陣Ai...Aj連乘的子問題為矩陣Ai...Ak連乘和矩陣Ak+1...Aj連乘,則最優值的遞歸關系式表示為c[i][j]=c[i][k]+c[k+1][j]+piqjqkD.矩陣連乘問題的時間復雜度為O(n2)81.動態規劃的基本要素是()。（）[多選題]*A.重疊子問題√B.最優子結構性質√C.自底向上的求解方式√D.自頂向下的遞歸求解方式82.有關動態規劃描述正確的是()。（）[多選題]*A.動態規劃將多階段決策問題轉化為單階段決策問題?！藼.動態規劃往往用于求解某種最優性質的問題?！藽.適用動態規劃求解的問題經分解得到的各個子問題往往不是相互獨立的?！藾.動態規劃求解時往往采用填表的方法記錄問題最優值?！蘀.動態規劃劃分的各子問題與原問題相同,一般遞歸求解子問題?！蘁.動態規劃求解某種最優性質的問題時,整體的最優值和子問題的最優值之間存在遞歸關系?！?3.設c[i][j]表示序列Xi和Yj的最長公共子序列的長度。則它的遞推關系式為：則，根據給定的X=={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}從上到下填寫缺失值。（）[單選題]*A.233B.222C.344√D.33384.給定序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}，它們的最長公共子序列是（）。（）[單選題]*A.BCBA√B.BCDAC.BDABD.BCAA85.按照順序排列動態規劃的求解步驟,正確的是()（1)遞歸定義最優值。（2)以自底向上的方式計算出最優值,并記錄相關信息。（3）分析最優解子結構性質。（4)構造出最優解。（）[單選題]*A.(1),(2),(3),(4)B.(1),(3),(2),(4)C.(3),(1),(2),(4)√D.(1),(2),(4),(3)86.以下算法框架中，哪個是排列樹模型的算法設計模式（）。（）[單選題]*A.defBacktrack(t):if(t>n):output(x)else:foriinrange(1,m+1):if(constraint(t)andbound(t)):x[t]=i做其他相關標識Backtrack(t+1)做其他相關標識的反操作B.defBacktrack(t):if(t>n):output(x)else:foriinrange(t,n+1):x[t],x[i]←x[i],x[t]if(constraint(t)andbound(t)):Backtrack(t+1)x[t],x[i]←x[i],x[t]√C.defBacktrack(intt):if(t>=n):output(x)else:foriinrange(s(n,t),e(n,t)):x[t]=d(i)if(constraint(t)andbound(t)):Backtrack(t+1)D.defBacktrack(intt):if(t>n):output(x)if(constraint(t)):做相關標識Backtrack(t+1)做相關標識的反操作if(bound(t)):做相關標識Backtrack(t+1)做相關標識的反操作87.最優化問題優化目標是使求目標函數最大化，基于回溯法求解該問題。如果對于解空間的任何分支X，均可求出目標函數值的兩個上界lb1(X)和lb2(X)，且總有lb1（X）>=lb2(X),則如果想用于剪枝，從減少搜索節點的角度，哪個界限更優？（）[單選題]*A.lb1B.lb2√C.二者等價D.依賴于具體輸入88.0-1背包問題的解空間結構屬于（）。（）[單選題]*A.排列樹B.子集樹√C.滿n叉樹D.隱式圖89.以下關于回溯法的說法，錯誤的是（）[單選題]*A.回溯法一般會將解空間組織成樹形結構并按照深度優先的順序遍歷B.回溯法可以適用于求所有解、某個解、最優解等各種問題C.回溯法能夠保證生成時間復雜度較低的算法√D.回溯法的編程中，有“當前搜索路徑”的概念，需要保存當前路徑上節點的狀態90.現有一個用于求解最優化問題的回溯算法，在搜索過程中涉及的函數的描述，錯誤的是（）[單選題]*A.違反約束函數的分支不屬于問題的定義域B.違反限界函數的分支不需要訪問，不能夠得到更優解C.目標函數是衡量解的優劣程度的函數D.在目標函數最小化問題中，限界函數應當使用上界√91.關于旅行商問題的說法，錯誤的是（）[單選題]*A.旅行商問題的解空間與最短路徑問題相同√B.旅行商問題的優化目標是回路長度最短C.有4個點的旅行商問題的兩個回路，ABCDA和BCDAB，實際上是兩個相同的回路D.旅行商問題無法用窮舉求解，因為回路數目太多92.以下有關旅行商問題的遞歸代碼，根據注釋判斷空缺部分填寫正確的是（）。defTraveling(t):()#到達葉子結點#g存儲圖的鄰接矩陣，x是存儲解向量，初始化為x[1:n]={1,2,...,n},cl是當前已走的路經長度，bestl是當前已找到的最短路徑長度。if(g[x[n]][1]!=∞and(cl+g[x[n]][1]<bestl)):forjinrange(1,n+1):bestx[j]=x[j]bestl=cl+g[x[n]][1]else:#沒有到達葉子結點()#控制當前節點的分支數目，即對xt的所有可能的取值。if(g[x[t-1]][x[j]]!=∞and(cl+g[x[t-1]][x[j]]<bestl)):#保存第t個要去的城市編號到x[t]中，進入到第t+1層x[t],x[j]=x[j],x[t]#交換兩個元素的值cl+=g[x[t-1]][x[j]]Traveling(t+1)#從第t+1層的擴展結點繼續搜索#第t+1層搜索完畢，回溯到第t層cl-=g[x[t-1]][x[j]]x[t],x[j]=x[j],x[t]。（C）[單選題]*A.空1：if(t==n)空2：for(j=t;j<=n;j++)B.空1：if(t>n-1)空2：for(j=1;j<=n;j++)C.空1：if(t>n)空2：for(j=t;j<=n;j++)√D.空1：if(t>=n-1)空2：for(j=1;j<=n;j++)93.有關回溯法說法正確的是（）。（）[多選題]*A.回溯法是一種深度優先搜索的搜索算法√B.回溯法是一種“能進則進、進不了則換、換不了則退（回溯）”的搜索方法√C.回溯法是一種寬（廣）度優先搜索的搜索算法D.回溯法是一種最大效益或最小費用優先搜索的方法94.有關n皇后問題說法正確的是（）。（）[多選題]*A.該問題的解的形式為(x1,x2,…,xn)，xi表示第i個皇后位于第i行、第xi列(i=1,2,3,...n)√B.該問題的初始狀態為：(0,0,...,0)√C.該問題的解空間的組織結構可以是排列樹，也可以是滿n叉樹?！藾.該問題只需要設置約束條件，不需要限界條件。√E、該問題解向量中的任意兩個分量xi,xj滿足：xi≠xj且|i-j|≠|xi-xj|√95.兩個分量xi,xj滿足：xi≠xj且|i-j|≠|xi-xj|下述有關搜索過程描述錯誤的是（）。（）[多選題]*A.當解空間結構是一棵樹時，搜索從根開始B.搜索過程中，正在生成孩子的節點稱為擴展節點C.搜索過程中，所有孩子節點均已生成的節點稱為擴展節點√D.搜索過程中，所有孩子節點均已生成的節點稱為活結點節點√E.搜索過程中所有孩子節點均已生成的節點稱為死節點√F.搜索過程動態生成的樹稱為搜索樹√96.以下描述中，影響回溯法的搜索效率的是（）。（）[多選題]*A.問題的解空間，即搜索范圍√B.設定的約束函數和限界函數√C.搜索方法D.滿足約束條件和限界條件的節點數目√97.以下有關子集樹的描述中說法正確的是（）。（）[多選題]*A.當所給的問題是從n個元素組成的集合S中找出滿足某種性質的一個子集時，相應的解空間樹稱為子集樹。√B.子集樹模型解的形式為n元組（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i個元素是否在子集中。√C.子集樹模型的解向量中，分量xi的取值為0或1，xi=0表示第i個元素不在子集中；xi=1表示第i個元素在子集中?！藾.旅行售貨員問題可以開用子集樹模型求解E.最優裝載問題可以采用子集樹模型求解F.0-1背包問題可以采用子集樹模型求解98.有關子集樹描述中，說法錯誤的是（）。（）[多選題]*A.子集樹的根結點為問題的初始狀態√B.子集樹的中間結點為搜索過程中形成的某中間狀態√C.子集樹的葉子結點為問題結束狀態√D.子集樹的分支表示從一個狀態過渡到另一個狀態的行為√E.子集樹中從根結點到葉子結點的路徑是一個可行解（一個子集）√F.子集樹的深度等于問題的規模加1√99.有關0-1背包問題說法正確的是（）。（）[多選題]*A.該問題的解的形式為(x1,x2,…,xn)，xi(i=1,2,3,...n)的取值為0或1√B.該問題的解空間的組織結構可以是排列樹。C.該問題需要設置約束條件，也可以設置限界條件?！藾.該問題只需要設置約束條件，不需要限界條件。100.有關下圖說法正確的是（）。（）[多選題]*A.該樹表示的問題的規模為3√B.該樹為一棵排列樹√C.該樹表示的問題規模為4。D.該樹為一棵子集樹101.有關批處理作業調度問題說法正確的是（）。（）[多選題]*A.該問題的解形式為(x1,x2,…,xn)，xi取值范圍為：令S={1,2,…,n}，則xi∈S-{x1,x2,…,xi-1}，i=1,2,...,n√B.該問題的解空間的組織結構是排列樹。√C.該問題需要設置約束條件，不需要限界條件。D.該問題不需要設置約束條件，只需要限界條件?！蘀.該問題既需要設置約束條件，也需要限界條件?！?02.有關旅行售貨員問題說法正確的是（）。（）[單選題]*A.該問題的解形式為(x1,x2,…,xn)，xi取值范圍為：令S={1,2,…,n}，則xi∈S-{x1,x2,…,xi-1}B.該問題的解空間的組織結構是排列樹?！藽.該問題需要設置約束條件，不需要限界條件。D.該問題不需要設置約束條件，只需要限界條件。E.該問題既需要設置約束條件，也可以設置限界條件。103.有關回溯法說法正確的是（）。（）[多選題]*A.回溯法是一種深度優先搜索的搜索算法√B.回溯法是一種“能進則進、進不了則換、換不了則退（回溯）”的搜索方法√C.回溯法是一種寬（廣）度優先搜索的搜索算法D.回溯法是一種最大效益或最小費用優先搜索的方法104.有關n皇后問題說法正確的是（）。（）[多選題]*A.該問題的解的形式為(x1,x2,…,xn)，xi表示第i個皇后位于第i行、第xi列(i=1,2,3,...n)√B.該問題的初始狀態為：(0,0,...,0)√C.該問題的解空間的組織結構可以是排列樹，也可以是滿n叉樹?！藾.該問題只需要設置約束條件，不需要限界條件?！蘀.該問題解向量中的任意兩個分量xi,xj滿足：xi≠xj且|i-j|≠|xi-xj|√105.以下描述中，影響回溯法的搜索效率的是（）。（）[多選題]*A.問題的解空間，即搜索范圍√B.設定的約束函數和限界函數√C.搜索方法D.滿足約束條件和限界條件的節點數目√106.有關隨機化算法錯誤的是（）。（）[單選題]*A.隨機化算法的特征是對所求解問題的同一實例用同一隨機化算法求解兩次可能得到完全不同的效果，這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。B.數值隨機化算法常用于數值問題的求解，所得到的解都是精確解?！藽.蒙特卡羅算法用于求問題的準確解，但解不一定正確。D.舍伍德算法引入隨機性來降低最壞情況出現的概率，從而消除或減少問題好壞實例之間的時間消耗的差異。107.有關估算π值的隨機化算法說法錯誤的是（）。（）[單選題]*A.估算π值的隨機化算法估算的近似值的精度隨算法消耗的時間的增加而提高B.估算π值的隨機化算法隨機實驗次數越多，估算的π值精度越高C.估算π值的隨機化算法是數值隨機化算法。D.估算π值的隨機化算法估算的近似值的精度與算法消耗的時間無關√108.有關主元素問題的蒙特卡羅算法說法錯誤的是。（）[單選題]*A.主元素問題的蒙特卡羅算法每次執行都返回True或False，True表示有主元素，False表示沒有主元素。B.主元素問題的蒙特卡羅算法返回True的解是正確解，False的解不一定是正確解。C.主元素問題的蒙特卡羅算法得到正確解的概率隨算法消耗的時間的增加而降低?！藾.主元素問題的蒙特卡羅算法得到的解為正確解的概率大于0.5。109.有關素數測試問題算法說法正確的是。（）[單選題]*A.根據Wilson定理，可以設計素數測試的隨機化算法。B.可以采用試除法，設計素數測試的隨機化算法。C.根據二次探測定理設計的素數測試蒙特卡羅算法得到的解為正確解的概率大于0.5√D.根據二次探測定理，可以設計素數測試的蒙特卡羅算法，當算法返回True時，解一定正確；當返回False時，解不一定正確。110.有關n皇后問題的拉斯維加斯算法說法正確的是。（）[單選題]*A.n皇后問題的拉斯維加斯算法可以采用對不沖突的多個列位置進行隨機。√B.n皇后問題的拉斯維加斯算法得到接的概率小于0。C.n皇后問題的拉斯維加斯算法每次運行都能得到一種n個皇后的放置方案。D.多次運行n皇后問題的拉斯維加斯算法并不能提高算法得到解的概率。111.有關隨機快速排序算法說法錯誤的是。（）[單選題]*A.隨機快速排序與快速排序的區別是隨機快速排序隨機選擇基準元素，而快速排序的確定性算法選擇固定位置的元素作為基準元素。B.隨機快速排序通過對快速排序引入隨機性，降低了快速排序最好和最壞情況出現的概率。C.隨機快速排序的時間復雜度趨于O(nlogn)。D.隨機快速排序每次運行都能夠得到解，但是得到的解不一定正確?！?12.有關整數n的因子分解問題說法正確的是。（）[單選題]*A.整數的因子分解就是將整數n分解多個因子的乘積，并不要求因子的素數性。B.整數的因子分解問題不可以轉化為因子分割問題。C.因子分割不可以采用試除法找出整數n的因子。D.Pollard算法，只要給足夠的時間，肯定能找到整數n的因子?！?13.以下有關隨機數產生的線性同余法說法正確的是。（）[單選題]*A.線性同余法產生的隨機數是偽隨機數。√B.線性同余法的系數是模數的倍數時，隨機數的隨機性能好。C.線性同余法的系數、增量、模數越大，隨機數的隨機性能越差。D.線性同余法的系數與模數互質，隨機數的隨機性能差。114.以下有關隨機選擇第k小算法正確的是。（）[單選題]*A.隨機選擇第k小算法中的隨機性和隨機快速排序的隨機性一樣，都是隨機選擇基準元素?！藼.隨機選擇第k小算法是對線性時間選擇算法中劃分過程進行了隨機，其他和線性時間選擇算法一樣。C.隨機選擇第k小算法劃分過程結束后，要在比基準元素小