算法設計與分析（安徽理工大學）知到智慧樹章節(jié)測試課后答案2024年秋安徽理工大學

算法設計與分析（安徽理工大學）知到智慧樹章節(jié)測試課后答案2024年秋安徽理工大學第一章單元測試

算法的重要特性()。

A:有窮性

B:能行性

C:確定性

D:輸出

E:輸入

答案:有窮性

；能行性

；確定性

；輸出

；輸入

語句returnsum(x,y);執(zhí)行頻度為1()

A:對B:錯

答案:錯的上界函數(shù)是()

A:錯B:對

答案:對算法時間復雜度為O(1)說明算法執(zhí)行時間是單位時間()

A:對B:錯

答案:錯集合的位向量表示法，合并集合操作的時間復雜度為()

A:

B:

C:

D:

答案:

帶加權規(guī)則的Union算法中，Parent(1)=-8,Parent(2)=-4，1、2代表的集合合并后,集合的根是1,Parent(1)=-12,Parent(2)=1()

A:錯B:對

答案:對寫一個算法交換兩個變量x、y的值不使用第三個變量。

答案:0求下列函數(shù)的漸進表達式：;;;

答案:無的漸進表達式=____

答案:無按照漸進階從低到高的順序排列以下表達式：,,,,,,。

答案:無

第二章單元測試

遞歸程序每一次遞歸執(zhí)行的語句都完全相同()

A:錯B:對

答案:錯對數(shù)組ary[0:n-1]求和,采用如下遞歸方式：arysum(n)=ary[n-1]+arysum(n-1),遞歸方式是()

A:線性遞歸B:非線性遞歸

答案:線性遞歸問題規(guī)模為的全排列問題，可以看作個規(guī)模為的全排列問題，因此時間復雜度為：()

A:對B:錯

答案:對遞歸程序簡潔明了，因此比非遞歸程序執(zhí)行效率高()

A:錯B:對

答案:錯MasterMethod適應于求解形式如T(n)=aT(n/b)+f(n)的遞歸關系式。其中，a表示子問題個數(shù)，n/b子問題規(guī)模，f(n)表示劃分子問題或整合子問題解的時間。()

A:對B:錯

答案:對遞歸關系式：F(n)=F(n-1)+F(n-2)+1是二階齊次常系數(shù)線性遞歸式。()

A:對B:錯

答案:錯解形式為()(p均為待定系數(shù)):

A:

B:

C:

D:

答案:

求解非線性變系數(shù)遞歸關系式一個原則是“變換”，經(jīng)過變換將其轉(zhuǎn)換為線性常系數(shù)等常規(guī)可求的遞歸式。()

A:錯B:對

答案:對用MasterMethod求解遞歸關系式：，上界是____

答案:無分析算法的時間復雜度，

寫出T(n)的表達式____

答案:無

第三章單元測試

在求解矩陣乘法問題中使用分治策略改善了問題的時間復雜度。()

A:對B:錯

答案:錯問題規(guī)模為n的二分檢索，不成功檢索的情況有無數(shù)種()

A:錯B:對

答案:錯二分檢索平均時間復雜度是()

A:

B:

C:

D:

答案:

；

分治策略在求最大最小元素問題中的應用有助于改善時間復雜度()

A:對B:錯

答案:錯插入排序算法的最好情況是初始序列從小到大排列(目標是從小到大)時間復雜度是()

A:對B:錯

答案:錯歸并排序MergeSort算法存在的問題是()

A:元素在數(shù)組間頻繁復制

B:遞歸層次多

C:子問題規(guī)模太小

答案:元素在數(shù)組間頻繁復制

；遞歸層次多

；子問題規(guī)模太小

數(shù)組link表示數(shù)組A(1:n)中元素的大小關系的鏈接信息表內(nèi)容如下

link下標：12345678

值：64713080

表頭指針p=5，則以p開頭的數(shù)據(jù)順序是()

A:A(5)＜A(3)＜A(7)＜A(8)

B:A(5)＜A(3)＜A(7)＜A(8)＜A(0)

C:A(5)＜A(6)＜A(7)＜A(8)＜A(0)

答案:A(5)＜A(3)＜A(7)＜A(8)

歸并排序子問題是通過位置劃分得到的，而快速排序的子問題是通過元素劃分得到的()

A:錯B:對

答案:對規(guī)模為n的快速排序，第一次劃分比較次數(shù)是n+1次。()

A:錯B:對

答案:對大堆排序求解選擇問題，首先確定出最大元素()

A:對B:錯

答案:對造成選擇問題最壞情況的原因是，劃分元素選擇使得兩個子問題規(guī)模懸殊()

A:對B:錯

答案:對二次取中間值方法得到的劃分元素可以劃分成兩個規(guī)模為n/2的子問題()

A:對B:錯

答案:錯

第四章單元測試

貪心法的關鍵是首先選擇一種度量標準，按照這個標準依次處理n個輸入()

A:錯B:對

答案:對貪心法求解背包問題的最優(yōu)度量標準是()

A:單位效益值pi/wi的非增次序

B:物品重量wi從小到大

C:目標函數(shù)效益值Pi從大到小

答案:單位效益值pi/wi的非增次序

證明貪心解就是最優(yōu)解的思路是在不減少總效益值的情況下，替換解向量中不同元素，直到把最優(yōu)解轉(zhuǎn)化為貪心解。()

A:錯B:對

答案:對貪心法求解帶有限期的作業(yè)調(diào)度問題，度量標準是總效益值，即按照效益值的從大到小的順序處理作業(yè)。()

A:錯B:對

答案:對一個作業(yè)i是否可以插入到可行調(diào)度序列，要看能否找到一個可行的位置q，滿足以下要求()

A:位置q之后的作業(yè)的期限值都大于作業(yè)i的期限值.

B:位置q之前的作業(yè)的期限值都小于等于當前作業(yè)i的期限值

C:作業(yè)i的期限值大于等于q+1

D:位置q之后的作業(yè)的期限值都大于它們當前的位置

答案:位置q之后的作業(yè)的期限值都大于作業(yè)i的期限值.

；位置q之前的作業(yè)的期限值都小于等于當前作業(yè)i的期限值

；作業(yè)i的期限值大于等于q+1

；位置q之后的作業(yè)的期限值都大于它們當前的位置

插入算法求帶期限的作業(yè)調(diào)度問題最大的問題是作業(yè)的調(diào)度順序不固定，需要不斷移動作業(yè)的調(diào)動位置，用并查集求解該問題的思路是開始就確定作業(yè)的調(diào)度位置。()

A:對B:錯

答案:對已知F(0)=0,F(1)=0,F(2)=1,F(3)=3,F(4)=4,P(0)=1,P(1)=-3,P(2)=1,P(3)=-1,P(4)=-1正處理作業(yè),2，它的期限值為3，以下判斷正確的是()

A:P(3)=1,P(1)=-4,其他P值不變

B:由于F(3)=3＞0，所以作業(yè)3可以調(diào)度，調(diào)度位置是時間片3[2,3]

C:P(3)=1,其他P值不變

D:處理完作業(yè)2，F(xiàn)(3)-1=2,2所在集合的根是1，所以F(1)=F(3)=0

答案:P(3)=1,P(1)=-4,其他P值不變

；由于F(3)=3＞0，所以作業(yè)3可以調(diào)度，調(diào)度位置是時間片3[2,3]

；處理完作業(yè)2，F(xiàn)(3)-1=2,2所在集合的根是1，所以F(1)=F(3)=0

n個結點的無向圖連通圖的生成樹的性質(zhì)有()

A:無環(huán)

B:有n-1條邊

C:連通

D:包含n個結點

答案:無環(huán)

；有n-1條邊

；連通

；包含n個結點

Prim算法處理邊的順序是構成樹的邊中最小的邊，剩余的邊中權值最小的邊不一定最先被選入生成樹中。()

A:對B:錯

答案:對Kruscal算法處理邊的順序是全部邊中權值從小到大的順序，選擇n-1條邊，這個過程中要保證不形成環(huán)。()

A:錯B:對

答案:對給定無向連通圖的最小生成樹是唯一的()

A:錯B:對

答案:錯單源點最短路問題要求有向圖中邊的權值不能為負數(shù)。()

A:錯B:對

答案:對

第五章單元測試

動態(tài)規(guī)劃求解問題的前提是最優(yōu)化原理成立，求解問題的關鍵是找到遞推關系式。()

A:對B:錯

答案:對

()

A:錯B:對

答案:對K段圖匯點t，cost(k-1,j)表示k-1階段的結點j到t的權值，cost(i,j)表示i階段的結點j到匯點t的最小成本。()

A:對B:錯

答案:對每對節(jié)點間最短路徑問題，遞推關系式從到的路徑上最大編號的結點時。()

A:錯B:對

答案:對二分檢索樹的左子樹中的元素都小于根，右子樹中的元素都大于根()

A:對B:錯

答案:對最優(yōu)二分檢索樹就是求解一個預期成本最小的二分檢索樹，決策過程主要是確定子樹的根。()

A:錯B:對

答案:對i曲線的構造是將的曲線在X軸上右移i單位，然后上移個單位而得到。()

A:錯B:對

答案:對組成的序偶：(5,4)(3,6),由于占的背包容量:6>4,產(chǎn)生的效益值3<5,因此序偶(3,6)被支配，刪除掉()

A:對B:錯

答案:對函數(shù)g(i,s)表示由結點i開始，通過S中的所有結點，在結點1終止的一條最短路徑長度()

A:錯B:對

答案:對已知序列X=＜A,B,C,B,D,A,B＞,Y=＜B,D,C,A,B,A＞，則序列X和Y的最長公共子序列是（）

A:＜B,C,A＞

B:＜B,D,B,A＞

C:＜B,D,A,B＞

D:＜B,C,B,A＞

答案:＜B,C,B,A＞

n個人拎著水桶在一個水龍頭前面排隊打水，水桶有大有小，水桶必須打滿水，水流恒定。如下()說法不正確？

A:讓水桶小的人先打水，在某個確定的時間t內(nèi)，可以讓盡可能多的人打上水

B:若要在盡可能短的時間內(nèi)，n個人都打完水，按照什么順序其實都一樣

C:讓水桶大的人先打水，可以使得每個人排隊時間之和最小

D:讓水桶小的人先打水，可以使得每個人排隊時間之和最小

答案:讓水桶大的人先打水，可以使得每個人排隊時間之和最小

動態(tài)規(guī)劃方法求解每對結點間的最短路問題要求圖中不含有負環(huán)()

A:錯B:對

答案:對

第六章單元測試

已知一棵二元樹的中序遍歷序列：FDHGIBEAC，先序遍歷序列為：ABDFGHIEC。其后序遍歷序列為（）

A:FHIGEDBCA

B:FHIGDEABC

C:FHIGDEBCA

D:HIGFDEBCA

答案:FHIGDEBCA

算術表達式的后綴形式是()

A:

B:

C:

答案:

將寄存器的值存入存儲單元的語句是()

A:

B:

C:

D:

答案:

機器模型A下生成最優(yōu)代碼規(guī)則，當右子樹不是葉子的時候，要先對右子樹進行遞歸處理，結果存入存儲單元，再處理左子樹，最后是根。（）

A:錯B:對

答案:對MR(T)的意思是表達式不使用store指令需要的最少的寄存器數(shù)量。()

A:對B:錯

答案:對當n＜MR(L)＜MR(R),其中n是機器的寄存器數(shù)量，應該先處理（）

A:先左子樹，再右子樹

B:先右子樹，再左子樹

答案:先右子樹，再左子樹

深度優(yōu)先檢索DFS需要使用（）存儲被訪問但尚未被檢測的結點

A:隊列

B:堆棧

答案:堆棧

圖采用鄰接表或鄰接矩陣存儲方式，深度優(yōu)先檢索的時間復雜度不同（）

A:對B:錯

答案:對刪除無向連通圖的一個結點及其相關聯(lián)的邊，形成了兩個及以上的非空分圖，這個結點稱為關節(jié)點（）

A:對B:錯

答案:對深度優(yōu)先數(shù)DFN，表示深度優(yōu)先訪問的順序。DFN(1)=5表示結點1第5個被訪問。（）

A:錯B:對

答案:對結點u及其兒子x、y、z的信息如下：DFN(u)=5，L(x)=1,L(y)=2,L(z)=5,可以判斷：結點u不是關節(jié)點。（）

A:對B:錯

答案:錯算法ART(u,v)中，當對u(不是根結點)的鄰接節(jié)點w遞歸訪問結束后，就得到了L(w)的值。（）

A:對B:錯

答案:對

第七章單元測試

背包問題中,約束條件是顯式約束條件。（）

A:對B:錯

答案:錯0/1背包問題的顯示約束條件是____

答案:0是回溯法搜索方式的是（）。

A:最大效益優(yōu)先

B:廣度優(yōu)先

C:深度優(yōu)先

D:最小耗費優(yōu)先

答案:深度優(yōu)先

皇后k可行的放置X(k)，已決策的前i個皇后的位置x(i),必須滿足以下條件（）

A:x(i)均不等于x(k)

B:x(i)-x(k)的絕對值不等于i-k的絕對值

C:x(i)＜x(k)

答案:x(i)均不等于x(k)

；x(i)-x(k)的絕對值不等于i-k的絕對值

子集和數(shù)問題中，限界函數(shù)Bk(x(1)...x(k))取真的條件是（）

A:已決策的前k個數(shù)據(jù)之和，加上剩余所有數(shù)據(jù)之和大于等于M

B:已決策的前k個數(shù)據(jù)之和加上第k+1個數(shù)小于等于M

C:已決策的前k個數(shù)據(jù)之和加上第k+1個數(shù)大于M

答案:已決策的前k個數(shù)據(jù)之和，加上剩余所有數(shù)據(jù)之和大于等于M

；已決策的前k個數(shù)據(jù)之和加上第k+1個數(shù)小于等于M

應用著色問題求解排考問題時，n門課程作為圖的n個結點，有公共學生的課程，其對應結點用邊連接，形成一個無向連通圖。對該圖求解著色問題，不同顏色數(shù)量即為需要排考的時間段數(shù)（）

A:錯B:對

答案:對背包問題的回溯算法所需的計算時間為（）

A:

B:C:D:

答案:對于給定問題的解空間樹是唯一的()

A:對B:錯

答案:錯以深度優(yōu)先方式搜索問題的解的方法稱為回溯法()

A:錯B:對

答案:對樹結構與所求問題的實例無關，結構不變的解空間樹稱為靜態(tài)樹()

A:對B:錯

答案:對

第八章單元測試

分支限界法搜索結點的順序是廣度優(yōu)先。（）

A:對B:錯

答案:對下面不是分支界限法搜索方式的是（）。

A:深度優(yōu)先

B:LC檢索C:LIFOD:FIFO

答案:深度優(yōu)先

15謎問題中，Less(12)=5說明比牌12小并且位置在牌12之后的牌有5個。（）

A:錯B:對

答案:對下列算法中不能解決0/1背包問題的是（）

A:分支限界法

B:回溯法C:貪心法D:動態(tài)規(guī)劃

答案:貪心法如果x是答案結點，且效益值P是當前的最優(yōu)解，則問題的界U更新為P，如果x不是答案結點則界等于P+ε，ε是個極小的正數(shù)