本文格式為Word版，下載可任意編輯——中南大學(xué)算法設(shè)計與分析試卷及答案（補(bǔ)考）中南大學(xué)考試試卷（補(bǔ)考）

2023--2023學(xué)年2學(xué)期時間110分鐘

算法分析與設(shè)計課程48學(xué)時3學(xué)分考試形式：閉卷

專業(yè)年級：信安0601-0602總分100分，占總評成績70%

注：此頁不作答題紙，請將答案寫在答題紙上

一、基本概念題（本大題40分）

1、一般狀況下，如何計算執(zhí)行順序、選擇、循環(huán)、子過程調(diào)用結(jié)構(gòu)的運(yùn)算時間？

（6分）

2、設(shè)T(n)=n，根據(jù)T(n)=O(f（n）)的定義，以下等式是否成立？（4分）

1）T(n)=O(n2)

2

2）O(n)=T(n)

3）T(n)=O(logn)+O(n)4）T(n)=O(n)*O(logn)

3、與順序查找算法相比，折半查找算法的時間繁雜性有多大程度的降低？

它是如何提高算法的效率的？（6分）4、簡述歸并排序算法和快速排序算法的分治方法。（6分）5、一般背包問題的貪心算法可以獲得最優(yōu)解嗎？物品的選擇策略是什么？（6分）6、Prim算法和Dijkstra算法選擇下一個節(jié)點(diǎn)的標(biāo)準(zhǔn)分別是什么？對于有負(fù)邊的無

向圖，Prim算法和Dijkstra算法還能保證獲得最優(yōu)解嗎？（6分）7、比較回溯法和分支限界法的探尋方式，哪種方法更適合找最優(yōu)解問題？（6分）

二、分析算法的時間繁雜性，需要寫出分析過程（本大題20分）

1、用分割元素v將有n個元素的數(shù)組分割成元素大于v和小于v的兩部分，需要

花多少時間（要講出道理）。（5分）2、假使修改歸并排序算法，將數(shù)組分成1/3和2/3大小不等的兩部分，分別排序

后再歸并，算法的最壞時間繁雜度有什么變化？（5分）3、設(shè)函數(shù)f1、f2和f3的處理時間分別為O(n)、O(n2)和O(1)，分析以下流程的時間繁雜性：1)基本結(jié)構(gòu)

procedureA1(intn，b)（4分）

ifb3(2分)O(1)n≤3考慮n=3k

T(n)=T(3k-1)+T(2*3k-1)+n-1

=T(3k-2)+2T(2*3k-2)+T(22*3k-2)+（n-1）+(n-2)

=T(3k-3)+3T(22*3k-3)+3T(223k-3)+T(233k-3)+（n-1）+(n-2)+(n-3)最終T(2i3k-i)=O(1)時，2i3k-i≤3

T(n)≤（n-1）+(n-2)+(n-3)++(n-(k-1))=nk-（1+2++(k-1)）

≤nlog3/2n（3分）

3、設(shè)函數(shù)f1、f2和f3的處理時間分別為O(n)、O(n2)和O(1)，分析以下流程

的時間繁雜性：1)基本結(jié)構(gòu)

procedureA1(intn，b)（4分）

T(n)=max{O(n),O(n)}+n*O(1)=O(n2)

2

2)遞歸結(jié)構(gòu)

設(shè)A2的時間為T（n）T(n)=T(n-1)+O(1)n>1

=O(1)n≤3（3分）T(n)=T(n-2)+2O(n)==T(1)+nO(n)

=O(n2)（3分）

三、算法理解（本大題24分）

1、在一個空間安排n=5個活動，開始時間和終止時間分別為。寫出活動安排貪

心算法的運(yùn)行結(jié)果。

1）依照終止時間排序（3分）

[8,10)1,[9,11:30)3,[11:40,13)4，[12,14)2,[13:30,15)52）可行解1，4，5（3分）

2、寫出0/1背包問題的動態(tài)規(guī)劃方程，并簡要說明。fi（X）＝max{fi-1(X)，{fi-l(X—wi)+pi當(dāng)X≥wi}（3分）

fi（X）是前i個物品，背寬容積X子問題的最優(yōu)值，

當(dāng)?shù)趇個物品不選入，fi（X）等于fi-1(X)前i-1個物品，背寬容積X子問題的最優(yōu)值，

當(dāng)?shù)趇個物品不選入，得利潤pi,但前i-1個物品能使用背包為X—wi。（3分）

3、修改圖的m-著色的回溯算法，找到一個解，算法就終止。（6分）

Mcolor(n)

{k←1;x[k]←0;

Whilek>0do（2分）{x[k]←x[k]+1;

whileplace(k)=falseandx[k]≤mdo

x[k]←x[k]+1

ifx[k]≤mthen