算法設(shè)計與分析試卷及答案

1、算法設(shè)計與分析算法設(shè)計與分析1、(1)證明：證明：O(f)O(g)=O(fg)（7分）分）(2)求下列函數(shù)的漸近表達式：（求下列函數(shù)的漸近表達式：（6分）分）①3n210n②211n2、對于下列各組函數(shù)、對于下列各組函數(shù)f(n)和g(n)，確定，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并簡述理由。，并簡述理由。（15分）分）(1)5log)(log)(2???nngnnf(2))(log)(2n

2、ngnnf??(3)log)()(2nngnnf??3、試用分治法對數(shù)組、試用分治法對數(shù)組A[n]實現(xiàn)快速排序。實現(xiàn)快速排序。（13分）分）4、試用動態(tài)規(guī)劃算法實現(xiàn)最長公共子序列問題。、試用動態(tài)規(guī)劃算法實現(xiàn)最長公共子序列問題。（15分）分）5、試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛、試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個加油站。試設(shè)計一個有效算法，指出應(yīng)公里，而旅途中有若干個加

3、油站。試設(shè)計一個有效算法，指出應(yīng)在哪些加油站停靠加油，使加油次數(shù)最少。在哪些加油站停靠加油，使加油次數(shù)最少。（12分）分）6、試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設(shè)、試用動態(tài)規(guī)劃算法實現(xiàn)下列問題：設(shè)A和B是兩個字符串。我是兩個字符串。我們要用最少的字符操作，將字符串們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串轉(zhuǎn)換為字符串B，這里所說的，這里所說的字符操作包括：字符操作包括：(1)刪除一個字符。刪除一個字符。(2)插入一個字符。插入一個字符。(

4、3)將一個字符改為另一個字符。將一個字符改為另一個字符。將字符串將字符串A變換為字符串變換為字符串B所用的最少字符操作數(shù)稱為字符串所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為的編輯距離，記為d(AB)。試設(shè)計一個有效算法，對任給的兩。試設(shè)計一個有效算法，對任給的兩個字符串個字符串A和B，計算出它們的編輯距離，計算出它們的編輯距離d(AB)。1、⑴證明：令證明：令F(n)=O(f)則存在自然數(shù)則存在自然數(shù)n1、c1，使得對任意的自

5、然，使得對任意的自然數(shù)n≥n1，有：，有：F(n)≤c1f(n)……………………………..（2分）分）同理可令同理可令G(n)=O(g)則存在自然數(shù)則存在自然數(shù)n2、c2，使得對任意的自然數(shù)，使得對任意的自然數(shù)n≥n2，有：，有：G(n)≤c2g(n)……………………………..（3分）分）令c3=maxc1c2n3=maxn1n2則對所有的則對所有的n≥n3，有：，有：F(n)≤c1f(n)≤c3f(n)G(n)≤c2g(n)≤c3g(

6、n)……………………………..（5分）分）故有：故有：O(f)O(g)=F(n)G(n)≤c3f(n)c3g(n)=c3(f(n)g(n))因此有：因此有：O(f)O(g)=O(fg)……………………………..（7分）分）⑵解：解：①因為因為01033)103(lim222??????nnnnnn由漸近表達式的定義易知：由漸近表達式的定義易知：3n2是3n210n的漸近表達式。的漸近表達式。……………………………..（3分）分）②因為因