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

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

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

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

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

5、然，使得對(duì)任意的自然數(shù)n≥n1，有：，有：F(n)≤c1f(n)……………………………..（2分）分）同理可令同理可令G(n)=O(g)則存在自然數(shù)則存在自然數(shù)n2、c2，使得對(duì)任意的自然數(shù)，使得對(duì)任意的自然數(shù)n≥n2，有：，有：G(n)≤c2g(n)……………………………..（3分）分）令c3=maxc1c2n3=maxn1n2則對(duì)所有的則對(duì)所有的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分）分）⑵解：解：①因?yàn)橐驗(yàn)?1033)103(lim222??????nnnnnn由漸近表達(dá)式的定義易知：由漸近表達(dá)式的定義易知：3n2是3n210n的漸近表達(dá)式。的漸近表達(dá)式?！?.（3分）分）②因?yàn)橐?/p>