算法分析與設計學習通超星期末考試答案章節(jié)答案2024年

算法分析與設計學習通超星期末考試章節(jié)答案2024年/star3/origin/e76a7f9b8f7ae1543445394686a02f3b.png

答案:錯問題的計算時間下界為Ω(f(n))，則計算時間復雜性為O(f(n))的算法是最優(yōu)算法。

答案:對/ananas/latex/p/3202708

答案:對Θ符號比O符號和Ω符號都精確，f(n)=Θ(g(n)），只要g(n)既是f(n)的上界又是f(n)的下界。

答案:錯一個算法的時間用Ω符號表示時，總是采用最有價值的g(n)表示，稱之為“緊湊下界”或“緊確下界”。

答案:對一個算法的時間用O符號表示時，總是采用最有價值的g(n)表示，稱之為“緊湊下界”或“緊確下界”。

答案:錯算法分析是分析算法占用計算機資源的情況，即分析算法的時間復雜度。

答案:錯算法是把人類找到的求解問題的方法，用算法要素過程化、形式化、機械化地表示出來。

答案:對如果一個算法對其每一個輸入實例，都能輸出正確的結果并停止，則稱它是可靠的。

答案:錯算法操作的對象是數(shù)據(jù)，數(shù)據(jù)間的（）就是數(shù)據(jù)的數(shù)據(jù)結構。

答案:邏輯關系;存儲方式;處理方式描述算法的形式包括（）。

答案:自然語言;程序設計語言;偽代碼;流程圖算法中的控制結構指的是各操作之間的執(zhí)行次序?；究刂平Y構包括（）。

答案:順序結構;選擇結構;循環(huán)結構算法由（）要素組成。

答案:操作;控制結構;數(shù)據(jù)結構算法設計應滿足以的目標包括（）。

答案:正確性;可使用性;健壯性算法的主要特征包括（）。

答案:有限性;確定性;可行性T(n)=T(n/3)+T(2n/3)+n

答案:O(log3/2n)/ananas/latex/p/576

答案:O()/ananas/latex/p/576

答案:O()給出算法的時間復雜性Loop(n):

p←0

fori←0to2ndo

p←p*i

答案:O(n)設S是一組n條直線，其中沒有兩條是平行的，也沒有三條在同一點相交?？梢杂脭?shù)學歸納法證明S中的直線確定了（）個交點。

答案:Θ()/ananas/latex/p/1542

答案:-1計算T(n)T(n)=1,

n=1T(n)=T(n-1)+n,

其它

答案:n(n+1)/2計算T(n)T(n)=4,當n=1T(n)=T(n-1)+4,其它

答案:4n算法分析包括最好情況下的時間復雜度(時間復雜度下界)、最壞情況下的時間復雜度(時間復雜度上界)和平均情況下的時間復雜度（時間復雜度均值）。實踐表明可操作性最好的，且最有實際價值的，是（）。

答案:時間復雜度上界算法要對異常情況進行適當?shù)奶幚?，就是算法的（）?/p>

答案:健壯性一切合法的輸入數(shù)據(jù)都能得出滿足要求的結果，包括典型的、苛刻的輸入數(shù)據(jù)也能夠得出滿足要求的結果。這個含義對應算法的（）。

答案:正確性從klnk=Θ(n)能得出k=Θ(n/ln)嗎？

答案:對O(1)=O(8)，O(1)和O(8)表示同一個函數(shù)時，差別僅在于其中的常數(shù)因子。

答案:對/ananas/latex/p/3207191

答案:對/ananas/latex/p/1086418

答案:對算法執(zhí)行時間相關的因素包括（）。

答案:問題中數(shù)據(jù)存儲的數(shù)據(jù)結構;算法設計的策略;問題的規(guī)模;實現(xiàn)算法的程序設計語言;算法采用的數(shù)學模型設n為算法中的問題規(guī)模，通常用（）漸進符號表示算法的執(zhí)行時間與n之間的一種增長關系。

答案:Ο;Θ;Ω對算法與數(shù)據(jù)結構關系的描述，正確包括（）。

答案:數(shù)據(jù)結構是算法設計的基礎。;算法是編程思想，數(shù)據(jù)結構則是這些思想的邏輯基礎;算法設計就是在選定的存儲結構上設計一個滿足要求的好算法。半數(shù)集問題：給定一個自然數(shù)n，右n開始可以依次產(chǎn)生半數(shù)集set(n)中的數(shù)如下：1）n加入set(n)；2）在n的左邊加一個自然數(shù)，但該自然數(shù)不能超過最近添加的數(shù)的一半；3）按此規(guī)則處理，直到不能添加自然數(shù)為止。元素允許重復。計算半數(shù)集set(n)中元素個數(shù)。設f(n)是半數(shù)集set(n)中元素個數(shù)，它的遞推公式是（）。

答案:f(n)=f(n/2)+...+f(1)+1計算T(n)T(n)=4,當n=1T(n)=T(n-1)+4,其它

答案:4n假設有一臺高性能計算機，其中CPU包含專用k>2個優(yōu)化寄存器。假設已經(jīng)存儲在寄存器中的數(shù)不超過k個，那么這些寄存器支持在O(1)時間插入鍵值對（x,y）的操作。此外，這些寄存器支持在O(1)時間刪除和返回具有最小關鍵字x的鍵值對（x,y）。證明：可使用這臺高性能計算機用（）時間對n個數(shù)排序。

答案:O(nlogn/logk)/ananas/latex/p/550836

答案:Θ(㏒n)給定A,B,C,D,E五個字符，出現(xiàn)的頻率（即權值）分別為5,4,3,2,1，霍夫曼編碼是什么？

答案:A->11,B->10,C->00,D->011,E->010計算T(n)T(n)=1,

n=1T(n)=T(n-1)+n,

其它

答案:n(n+1)/2給出算法的時間復雜性Loop(n):

p←0

fori←0to2ndo

p←p*i

答案:O(n)貪心算法則通常以（）的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。

答案:自頂向下函數(shù)MinMax用來查找數(shù)組a[0:n-1]中的最大元素和最小元素，問：在各個程序中，a中元素之間的比較次數(shù)在最好、最壞和平均情況下各

1

,

2

,

3

。templateboolMinMax(Ta[],intn,int&Min,int&Max){//尋找a[0:n-1]中的最小元素與最大元素

//如果數(shù)組中的元素數(shù)目小于1，則還回false

if(n<1)returnfalse;

Min=Max=0;//初始化

for(inti=1;ia[i])Min=i;

elseif(a[Max]答案:A.n-1;C.2(n-1);D.(n-1)/ananas/latex/p/31709

答案:B.2n;A.n/ananas/latex/p/507324

答案:C.Q;A.O;B.W;B.W;C.Q;B.W;B.W;A.O下面算法的時間復雜度T（n）為O（）。輸入：n=2k

,k為正整數(shù)輸出：kk

←0Whilen

≥1do

forj

←1tondo

k

←k+1

n

←n/2returnk

答案:n假設某算法在輸入規(guī)模為n時的計算時間為T(n)=

n2。在某臺計算機上實現(xiàn)并完成該算法的時間為t秒?，F(xiàn)有另一臺計算機，其運行速度為第一臺的64倍，那么在這臺新計算機上用同一算法在t秒內(nèi)能解輸入規(guī)模為

的問題。

答案:8n/ananas/latex/p/4320178

答案:A.n;C.

Θ;B.2;C.nlogn/star3/origin/a04005488eb2979f4558fbb68f823d77.png

答案:C.;A.θ()流水線作業(yè)問題。有8個作業(yè){1，2，…，8}要在由2臺機器M1和M2組成的流水線上完成加工。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時間分別為ai和bi。M110281269414M2571151631113作業(yè)12345678（1）給出一個最優(yōu)調(diào)度方案

1

，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成所需的時間最少；（2）計算所需的最少時間為

2

。

答案:A.{2，7，5，4，8，1，6，3};B.73/star3/origin/1f064ac14632579f99e5671f39f912d6.png

答案:C.112344;C.AADB/star3/origin/dca1b6dcaedaf4f73371de71a2f1e3c4.png

答案:B.35;C.27;B.45;B.37;C.1，2，4，3，5當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應的解空間樹為

1

，遍歷時間為O（

2

）的計算時間。

答案:B.子集樹;A.回溯法中遍歷排列樹的時間復雜度為O（

）。

答案:n!常用剪枝函數(shù)中，用