第一章單元測試1.【多選題】正確答案：ABC下列關于效率的說法正確的是（）。A.提高程序效率的根本途徑在于選擇良好的設計方法，數據結構與算法B.效率是一個性能要求，其目標應該在需求分析時給出C.效率主要指處理機時間和存儲器容量兩個方面D.程序的效率與程序的長度強相關2.【多選題】正確答案：BC算法的時間復雜度取決于（）。A.硬盤容量B.待處理數據的初態C.問題的規模D.計算機性能3【單選題】(2分)計算機算法指的是（）。A.排序方法B.調度方法C.解決問題的有限運算序列D.計算方法4.【多選題】正確答案：BD歸并排序法的時間復雜度和空間復雜度分別是（）。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)5【判斷題】將長度分別為m,n的兩個單鏈表合并為一個單鏈表的時間復雜度為O(m+n)。（）A.對B.錯6【判斷題】用漸進表示法分析算法復雜度的增長趨勢。（）A.錯B.對7【判斷題】算法分析的兩個主要方面是時間復雜度和空間復雜度的分析。（）A.錯B.對8【單選題】(2分)某算法所需時間由以下方程表示，求出該算法時間復雜度（）。A.O(n2)B.O(n)C.O(nlog2n)D.O(log2n)9【單選題】(2分)下列代碼的時間復雜度是（）。A.O(1)B.O(log2N)C.O(log3N)D.O(N)10【單選題】(2分)下列算法為在數組A[0,...,n-1]中找出最大值和最小值的元素，其平均比較次數為（）。A.3n/2-3/2B.n-3/2C.3n/2D.2n-1第二章單元測試1【單選題】(2分)可用Master方法求解的遞歸方程的形式為（）。A.T(n)=T(n-a)+T(a)+f(n)，a≥1B.T(n)=T(n/a)+T(n/b)+f(n)，a≥1,b1C.T(n)=aT(n/b)+f(n),a≥1,b1,為整數,f(n)0.D.T(n)=T(n-a)+T(n-b)+f(n)，a≥1,b12【判斷題】A.錯B.對3【判斷題】……遞歸方程9的解是.()A.對B.錯4【判斷題】假設數組A包含n個不同的元素，需要從數組A中找出n/2個元素，要求所找的n/2個元素的中點元素也是數組A的中點元素。針對該問題的任何算法需要的時間復雜度的下限必為。()A.錯B.對5【單選題】(2分)使用Master方法求解遞歸方程的解為（）.C.6【判斷題】考慮包含n個二維坐標點的集合S，其中n為偶數，且所有坐標點中的均不相同。一條豎直的直線若能把S集合分成左右兩部分坐標點個數相同的子集合，則稱直線L為集合S的一條分界線。若給定集合S，則可在時間內找到這條分界線L。()A.對B.錯7【單選題】(2分)C.8【判斷題】從n個數中找出前k個最小的元素并對所選擇的前k個最小的元素進行排序。使用歸并排序算法將這n個數進行排序的時間復雜度，從排好序的數組中提取有序的k個最小數的時間復雜度為，因此總的運行時間復雜度為.()A.錯B.對9【判斷題】假定問題對于規模為n的所有不同輸入，存在一個分治算法其平均時間復雜度為，則算法在最壞情形下的時間復雜度可能為（）A.錯B.對10【單選題】(2分)使用分治算法求解最大最小問題。假定問題的規模,每次將問題分成規模接近的兩個子問題，遞歸地對子問題求解并將子問題的解合并得到大問題的解，該分治算法的復雜度函數可寫為()A.第三章單元測試1【判斷題】在一個至少包含三個頂點的加權連通單向圖中，假定邊的權重互不相同，則權重最大的邊不可能被包含在任何最小生成樹中。()A.對B.錯2【判斷題】令是一個加權圖，令T是G的最小生成樹，則T中任意兩個頂和之間的路徑必定是圖G中該兩點之間的最短路徑。()A.對B.錯3【判斷題】對于一個加權連通無向圖，在Kruskal’sMST(KrusKal’s最小生成樹)算法中,若使用最大隊列代替最小隊列，則可生成一個最大成本樹(而不是最小成本樹).()A.錯B.對4.【多選題】正確答案：CD貪心算法適用于求解的問題一般具備以下幾個特征().A.子問題的解相互獨立B.問題可分為相互獨立的子問題C.滿足貪心選擇性質D.滿足最優子結構性質5【判斷題】0/1背包問題是NP-hard問題，任何求解0/1背包問題的貪心算法都不能保證得到該問題的最優解。（）A.對B.錯6【判斷題】一個連通圖中具有最小權重的邊，必定被包含在圖的最小生成樹中。()A.錯B.對7【判斷題】一個問題的貪心選擇性質是指問題的最優解可通過一系列具備最優(貪心)選擇得到。（）A.錯B.對8【判斷題】貪心算法所做出的選擇可能依賴于到目前為止已經做出的選擇，但是不依賴于將來的選擇或子問題的解。（）A.錯B.對9【判斷題】貪心算法是一種自頂向下的求解方法，分步做出貪心選擇，逐步將問題變成規模較小的問題求解。（）A.對B.錯10【單選題】(2分)下列問題可使用貪心算法求得最優解的是（）.A.偶圖覆蓋問題B.集合覆蓋問題C.貨箱裝載問題D.0/1背包問題第四章單元測試1.【多選題】正確答案：BCD動態規劃的適用條件為（）。A.子問題相互獨立B.最優子結構性質C.子問題的重疊性D.無后效性2【單選題】(2分)（1）計算動態規劃數組；（2）確定動態規劃函數；（3）構造最優解；（4）定義子問題。動態規劃一般可以將步驟依次劃分為：（）。A.（4）（1）（2）（3）B.（4）（3）（1）（2）C.（4）（2）（1）（3）D.（3）（4）（2）（1）3【判斷題】使用動態規劃方法解決0/1背包問題，設V(i,j)表示將前i(1≤i≤n)個物品裝入容量為j(1≤j≤C)的背包獲得的最大價值，在決策其動態規劃函數為：。（）A.錯B.對4【單選題】(2分)設有5個物品，背包承重為10，5個物品價值p=[6,3,5,4,6]，質量w=[2,2,6,5,4]，則該0/1背包問題的解向量為（）。A.[1,1,0,0,1]B.[1,0,0,1,1]C.[1,0,0,0,1]D.[0,0,1,1,0]5【單選題】(2分)設M1,4=M1M2M3M4表示4個矩陣相乘，矩陣維度r1=2,r2=10,r3=2,r4=10,r5=2，則鏈乘的最少次數是（）。A.44B.40C.80D.886【單選題】(2分)使用動態規劃方法解決矩陣乘法鏈問題的時間復雜度和空間復雜度分別為（）。A.7【單選題】(2分)設有有向加權圖如下圖所示，每兩對點之間的最短路徑長度（）。D.8【單選題】(2分)設有有向加權圖如下圖所示，起點0點與其他點之間的最短路徑長度（）。A.9【單選題】(2分)設有一個網(i,Ci)如下圖所示，則滿足i≤5且Ci≤7的最大不交叉網子集有（）個。A.4B.3C.1D.210【單選題】(2分)有字符串a=ABCB,b=BDCA，則使用動態規劃方法求解a與b的最長公共子序列時，下表X處的值為()。A.0B.-1C.1D.2第五章單元測試1【判斷題】回溯法是指具有限界函數的深度優先生成法。（）A.對B.錯2【判斷題】用回溯法解題的一個顯著特征是在搜索過程中動態產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。（）A.對B.錯3【判斷題】用回溯法解批處理作業調度問題時，該問題的解空間結構為子集樹結構。（）A.對B.錯4【單選題】(2分)在對問題的解空間樹進行搜索的方法中，一個結點有多次機會成為活結點的是（）。A.分支限界法B.回溯法和分支限界法C.動態規劃D.回溯法5【單選題】(2分)回溯法在解空間樹T上的搜索方式是（）。A.深度優先B.最小耗費優先C.廣度優先D.活結點優先6【單選題】(2分)回溯算法和分支限界法的問題的解空間樹不會是（）。A.排列樹B.無序樹C.有序樹D.子集樹7【判斷題】回溯法求問題的所有解時，要回溯到根，且根結點的子樹都要已被搜索遍才結束。（）A.對B.錯8.【多選題】正確答案：ABCD下列問題中可以用回溯算法解決的是？（）A.0/1背包問題B.旅行商問題C.N皇后問題D.貨箱裝船問題9【單選題】(2分)回溯法的效率不依賴于以下哪一個因素？（）A.問題的解空間的形式B.滿足顯約束的x[k]值的個數C.產生x[k]的時間D.計算上界函數bound的時間10【單選題】(2分)用回溯法解圖的m著色問題時，使用下面的函數OK檢查當前擴展結點的每一個兒子所相應的顏色的可用性，則需耗時（漸進時間上限）（）。A.O(m2)B.O(n)C.O(mn)D.O(m)第六章單元測試1【單選題】(2分)分支限界法中，解空間組織成()結構然后進行搜索。A.樹B.鏈表C.堆棧D.數組2【單選題】(2分)分支限界法在問題的解空間樹中，按()策略，從根節點出發搜索解空間樹。A.擴展節點優先B.活動節點優先C.深度優先D.廣度優先3【單選題】(2分)優先隊列式分支限界法選取擴展節點的原則是()A.先進先出B.節點的優先級C.后進后出D.隨機4.【多選題】(3分)正確答案：BD分支限界法主要有哪幾種方式實現？（）A.堆棧式分支限界法B.FIFO隊列式C.廣度優先分支限界法D.優先隊列式分支限界法5.【多選題】(3分)正確答案：ABCD比較分支限界法和回溯法，兩者的不同是()A.分支限界法需要借助活動節點表數據結構，而回溯法則不需要B.分支限界法與回溯法的搜索方式不同C.在一般情況下，分支限界法與回溯法的求解目標不同D.擴展節點的擴展方式不同6.【多選題】(3分)正確答案：BCD下述有關分支限界法搜索過程描述正確的是()A.必須當活動節點表為空時，算法才算結束B.搜索過程中，擴展節點一次性生成所有的孩子節點C.搜索過程中，保留下來的孩子節點是可能導致可行解或最優解的節點D.搜索過程中，保留下來的孩子節點是活動節點，被插入活動節點表中7【判斷題】(1分分支限界法保留下來的活動節點是有可能導致可行解或最優解的節點，回溯法則不是。（）A.對B.錯8【判斷題】(1分分支限界法中活動節點可以多次擴展。（）A.錯B.對9【判斷題】(1分分支限界法一般比回溯法使用更多內存空間。（）A.錯B.對10【判斷題】(1分分支限界法一般更適合求解最優化問題。（）A.對B.錯第七章單元測試1【單選題】(2分)快速排序問題屬于()A.難解問題B.易解問題C.不可解問題D.NP難問題2【單選題】(2分)能夠用動態規劃算法求解的問題一定屬于()A.易解問題B.難解問題C.NP問題D.NP難問題3【單選題】(2分)停機問題不屬于()A.NP難問題B.難解問題C.決策問題D.不可計算問題4.【多選題】(4分)正確答案：BCD下面的問題屬于NP問題的有（）A.定理識別問題B.找出圖中所有點對的最短路徑問題C.計算兩個正整數的最大公約數D.矩陣乘法鏈問題5.【多選題】(4分)正確答案：ACDNP完全題可能屬于()A.NP類問題B.難解問題C.NP難問題D.P類問題6.【多選題】(4分)正確答案：AC關于多項式規約，下面敘述正確的是()