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

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

第一章測試

算法的重要特性()。

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:錯

答案:對

第二章測試

遞歸程序每一次遞歸執(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ù)遞歸關系式一個原則是“變換”，經過變換將其轉換為線性常系數(shù)等常規(guī)可求的遞歸式。()

A:錯B:對

答案:對

第三章測試

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

A:對B:錯

答案:錯

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

A:錯B:對

答案:錯

二分檢索平均時間復雜度是()

A:

B:

C:

D:

答案:

;

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

A:對B:錯

答案:錯

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

A:對B:錯

答案:錯

歸并排序MergeSort算法存在的問題是()

A:遞歸層次多

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

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

答案:遞歸層次多

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

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

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

link下標：12345678

值：64713080

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

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

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

C:A(5)＜A(3)＜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:目標函數(shù)效益值Pi從大到小

C:物品重量wi從小到大

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

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

A:對B:錯

答案:對

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

A:對B:錯

答案:對

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

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

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

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

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

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

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

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

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

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

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:由于F(3)=3＞0，所以作業(yè)3可以調度，調度位置是時間片3[2,3]

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

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

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

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

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

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

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

A:無環(huán)

B:連通

C:有n-1條邊

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,產生的效益值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,C,B,A＞

C:＜B,D,A,B＞

D:＜B,D,B,A＞

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

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

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

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

C:讓水桶小的人先打水，在某個確定的時間t內，可以讓盡可能多的人打上水

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

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

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

A:錯B:對

答案:對

第六章測試

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

A:FHIGDEABC

B:HIGFDEBCA

C:FHIGDEBCA

D:FHIGEDBCA

答案: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:對

答案:錯

是回溯法搜索方式的是（）。

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)的絕對值不等于i-k的絕對值

;x(i)均不等于x(k)

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

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

B:已決策的前k個數(shù)據(jù)之和，加上剩余所有數(shù)據(jù)之和大于等于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:LIFOB:深度優(yōu)先

C:LC檢索D:FIFO

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

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

A:對B:錯

答案:對

下列算法中不能解決0