算法分析與設(shè)計(jì)習(xí)題集

1、算法分析與設(shè)計(jì)習(xí)題集算法分析與設(shè)計(jì)習(xí)題集算法分析與設(shè)計(jì)習(xí)題集算法分析與設(shè)計(jì)習(xí)題集整理第一章算法引論一、填空題：1、算法運(yùn)轉(zhuǎn)所需要的計(jì)算機(jī)資源的量，稱為算法復(fù)雜性，主要包含時(shí)間復(fù)雜度和空間復(fù)雜度。2、多項(xiàng)式A(n)amnmLa1na0的上界為O(nm)。3、算法的基本特色：輸入、輸出、確立性、有限性、可行性。4、怎樣從兩個(gè)方面談?wù)撘粋€(gè)算法的利害：時(shí)間復(fù)雜度、空間復(fù)雜度。5、計(jì)算下邊算法的時(shí)間復(fù)雜度記為：O(n3)。for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj;6、描繪算法常用的方法：自然語言、偽代碼、程序設(shè)計(jì)

2、語言、流程圖、盒圖、PAD圖。7、算法設(shè)計(jì)的基本要求：正確性和可讀性。8、計(jì)算下邊算法的時(shí)間復(fù)雜度記為：O(n2)。for（i1；in;i+）y=y+1;for（j0；j=2nx；j+）9、計(jì)算機(jī)求解問題的步驟：問題分析、數(shù)學(xué)模型成立、算法設(shè)計(jì)與選擇、算法表示、算法分析、算法實(shí)現(xiàn)、程序調(diào)試、結(jié)果整理文檔編制。10、算法是指解決問題的方法或過程。11、算法由操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)三因素構(gòu)成。二、簡答題：1、依據(jù)時(shí)間復(fù)雜度從低到高擺列：O(4n2)、O(logn)、O(3n)、O(20n)、O(2)、O(n2/3),O(n!)應(yīng)當(dāng)排在哪一位2/32n答：O(2)，O(logn)，O(n)，O(2

3、0n)，O(4n)，O(3)，O(n!)2、什么是算法算法的特色有哪些答：1）算法：指在解決問題時(shí)，依據(jù)某種機(jī)械步驟必然能夠獲得問題結(jié)果的辦理過程。2）特色：1)算法有零個(gè)或多個(gè)輸入；)算法有一個(gè)或多個(gè)輸出；3)確立性；)有窮性3、給出算法的定義何謂算法的復(fù)雜性計(jì)算下例在最壞狀況下的時(shí)間復(fù)雜性for(j=1;j=n;j+)(1)for(i=1;i=n;i+)(2)cij=0;(3)for(k=1;k=n;k+)(4)cij=cij+aik*bkj;(5)答：1）定義：指在解決問題時(shí)，依據(jù)某種機(jī)械步驟必然能夠獲得問題結(jié)果的辦理過程。）算法的復(fù)雜性：指的是算法在運(yùn)轉(zhuǎn)過程中所需要的資源（時(shí)間、空間）

4、多少。所需資源越多，表示算法的復(fù)雜性越高3）該算法的主要元操作是語句5，其履行次數(shù)是n3次。故該算法的時(shí)間復(fù)雜度記O(n3).4、算法A和算法B解同一問題，設(shè)算法A的時(shí)間復(fù)雜性知足遞歸方程T(n)1,n1T(n)，4T(n/2)n,n1算法B的時(shí)間復(fù)雜性知足遞歸方程T(n)1,n1A時(shí)間復(fù)雜T(n)，若要使得算法aT(n/4)n,n1性的階高于算法B時(shí)間復(fù)雜性的階，a的最大整數(shù)值可取多少答：分別記算法A和算法B的時(shí)間復(fù)雜性為TA(n)和TB(n)，解相應(yīng)的遞歸方程得：TTAB(n)O(n2)O(n),a4(n)O(nlogn),a4O(nlog4a),a4依題意，要求最大的整數(shù)a使得TB(n)

5、TA(n)。明顯，當(dāng)a4時(shí)，TB(n)TA(n)log4a2a2n=2寫出其相的算法IntF(intn)if(n=1)return1;elseif(n=2)return2;elsereturnF(n-1)+F(n-2);2、a,b,c是3個(gè)塔座。開始，在塔座a上有一疊共n個(gè)，些自下而上，由大到小地疊在一同。各從小到大號(hào)1,2,n,要求將塔座a上的一疊移到塔座b上，并仍按同序疊置。在移恪守以下移：1：每次只好移1個(gè)；2：任何刻都不允將大的在小的之上；3：在足移1和2的前提下，可將移至a,b,c中任一塔座上。寫出的解步并寫出其相的算法解：第一步：將n1個(gè)子看作一個(gè)整體，從A移到C；第二步：將第n個(gè)

6、子移到B;第三步：將n1個(gè)子看作一個(gè)整體，從C移到B；寫出其相的算法：voidhanoi(intn,inta,intb,intc)if(n0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);第二章分治算法（2）分治算法一、填空：1、在迅速排序、插入排序和合并排序算法中，2、合并排序算法使用的是分治3、二分找尋算法是利用分治插入排序算法的思想。算法思想的。算法不是分治算法。二、答：1、適適用分治算法求解的擁有的基本特色答：1)的模小到必然的程度就能夠簡單解決;能夠分解若干個(gè)模小的同樣，即擁有最子構(gòu)性；）所分解出的各個(gè)子是相互獨(dú)立的，即子之不包含公共的子。4

7、）利用分解出子解能夠合并解;2、分治算法基本思想，解步三、算法：1、改寫二分找算法：a1n是一個(gè)已排好序的數(shù)，改寫二分找算法，使合適找尋元素中，返回小于x的最大元素地點(diǎn)i，和大于x的最小元素地點(diǎn)j；當(dāng)找尋元素，i和j同樣，均x在數(shù)中的地點(diǎn)。x不在數(shù)x在數(shù)中并分析其復(fù)度解：intbinsearch(intan,intx,)3）回溯將分解的兩解大者取大，小者取小，合并目前的解。、第三章動(dòng)向規(guī)劃算法一、填空題：1、動(dòng)向規(guī)劃算法中儲(chǔ)蓄子問題的解是為了防范重復(fù)求解子問題2、（最優(yōu)子結(jié)構(gòu)）是問題能用動(dòng)向規(guī)劃算法求解的前提。3、矩陣連乘問題的算法可由（動(dòng)向規(guī)劃。）算法設(shè)計(jì)實(shí)現(xiàn)。二、判斷題：1、動(dòng)向規(guī)劃算法基

8、本因素的是最優(yōu)子結(jié)構(gòu)。2、最優(yōu)子結(jié)構(gòu)性質(zhì)是指原問題的最優(yōu)解包含其子問題的最優(yōu)解。3、動(dòng)向規(guī)劃算法求解問題時(shí)，分解出來的子問題相互獨(dú)立。（）（）（X）三、簡答題：1、動(dòng)向規(guī)劃算法解題步驟答：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特色;（即原問題的最優(yōu)解，包含了子問題的最優(yōu)解）遞歸地定義最優(yōu)值;（即子問題擁有重疊性，由子問題定義原問題）以自底向上的方式計(jì)算出最優(yōu)值;依據(jù)計(jì)算最優(yōu)值時(shí)獲得的信息，結(jié)構(gòu)最優(yōu)解;2、動(dòng)向規(guī)劃算法基本思想答：動(dòng)向規(guī)劃算法與分治法近似，其基本思想也是將待求解問題分解成若干個(gè)子問題；可是經(jīng)分解獲得的子問題經(jīng)常不是相互獨(dú)立的。不同樣子問題的數(shù)量經(jīng)常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子

9、問題被重復(fù)計(jì)算了很多次；假如能夠保留已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就能夠防范大批重復(fù)計(jì)算，進(jìn)而獲得多項(xiàng)式時(shí)間算法。3、動(dòng)向規(guī)劃與分治算法異同點(diǎn)4、動(dòng)向規(guī)劃算法的基本因素四、算法與算：1、Xx1,x2,L,xm和Yy1,y2,L,yn的最公共子序列Zz1,z2,L,zk。：若用cij序列Xix1,x2,L,xi和Yjy1,y2,L,yj公共子序列度。求：用劃法求解,算最的公式算最的算法以及結(jié)構(gòu)最解的算法2、江游艇俱部在江上置了n個(gè)游艇出租站1,2n.旅客可在些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站游艇。游艇出租站i到游艇出租站j之的租金r(i，j)，此中1=ij=

10、n；求：用劃法求解,算最（最少租金）的公式算最（最少租金）的算法并分析其復(fù)度解：ri,j0ijminri,krk1,jijikj算最算法publicstaticvoidmatrixChain(intp,intm,ints)intn=;for(inti=1;i=n;i+)mii=0;要求：出Dijkstra算法的迭代程，算源到個(gè)點(diǎn)的最短路徑（用表表示）解：本123表4-2解：迭代過程：第章回溯算法一、填空題1、回溯法與分支限界法找尋方式不同樣，回溯法按深度優(yōu)先找尋解空間，分支限界法按廣度優(yōu)先或最小耗資優(yōu)先找尋解空間。二、判斷題1、回溯法中限界函數(shù)的目的是剪去得不到最優(yōu)解的子樹。2、分支限界法近似

11、于回溯法，也是一種在問題的解空間樹找尋方式是同樣的。（）T上找尋問題解的算法，二者的X）三、簡答題1、簡述回溯法和分支限界法的同樣點(diǎn)和不同樣點(diǎn)2、什么是子集樹什么是擺列樹什么叫滿m叉樹3、回溯算法的基本思想回溯算法的解題步驟四、算法設(shè)計(jì)題1、n皇后問題44格的棋盤上擱置相互不受攻擊的4個(gè)皇后。依據(jù)國際象棋的規(guī)則，皇后能夠攻擊與之處在同一行或同一列或同一斜線上的棋子。用回溯算法解決4皇后問題：結(jié)構(gòu)求解該問題的解空間樹設(shè)計(jì)該4皇后問題的回溯算法解：解空間樹回溯算法2、01背包問題：假定有3個(gè)物件，它們的重量和價(jià)值以下表所示。若這些物件均不可以夠夠被切割，且背包容量M10，問應(yīng)當(dāng)怎樣裝入使背包中物件

12、的總價(jià)值最大用回溯算法求解該01背包問題：ABC結(jié)構(gòu)求解該問題的解空間樹物件設(shè)計(jì)該01背包問題的回溯算法重量655解：1）解空間樹;價(jià)值4225302)3、圖的著色問題：以以以下圖給定無向連通圖G和m種不同樣的顏色；用這m種顏色為圖G的各個(gè)極點(diǎn)著色，能否有一種方法使得圖G中每一條邊的兩個(gè)極點(diǎn)著不同樣顏色；求：結(jié)構(gòu)求解該問題的解空間樹設(shè)計(jì)該圖的著色問題回溯算法12354解：1）解空間樹：）算法:doublemcoloring(intmm)intm=mm;法1：行列式（FIFO先進(jìn)先出）分支限界法?從根結(jié)點(diǎn)1開始；將活結(jié)點(diǎn)組織成一個(gè)行列；?初始時(shí)活結(jié)點(diǎn)行列為空，結(jié)點(diǎn)加入行列，結(jié)點(diǎn)1為目前擴(kuò)展結(jié)點(diǎn)；

13、1?結(jié)點(diǎn)1的孩子結(jié)點(diǎn)2、9為可行結(jié)點(diǎn)，故舍棄目前結(jié)點(diǎn)1，將2、9加入活結(jié)點(diǎn)行列；29?先進(jìn)先出原則，2作為目前擴(kuò)展結(jié)點(diǎn)，其孩子結(jié)點(diǎn)3、6；因?yàn)榻Y(jié)點(diǎn)3是不可以行結(jié)點(diǎn)舍棄；將結(jié)點(diǎn)6加入活結(jié)點(diǎn)行列；96?先進(jìn)先出原則，9作為目前擴(kuò)展結(jié)點(diǎn)，其孩子結(jié)點(diǎn)10、13;結(jié)點(diǎn)10、13是可行結(jié)點(diǎn)加入活結(jié)點(diǎn)行列；61013ntValue();ntValue();回溯法解TSP問題時(shí)的解空間樹是（A）。A、子集樹B、擺列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹6以下算法中平常以自底向上的方式求解最優(yōu)解的是（B）。、備忘錄法B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法7、權(quán)衡一個(gè)算法利害的標(biāo)準(zhǔn)是（C）。A運(yùn)轉(zhuǎn)速度快B占用空間少C

14、時(shí)間復(fù)雜度低D代碼短8、以下不可以夠夠使用分治法求解的是（D）。A棋盤覆蓋問題B選擇問題C合并排序D0/1背包問題實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（A）。、分治策略B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法10、實(shí)現(xiàn)最長公共子序列利用的算法是（B）。A、分治策略B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法11下邊不是分支界限法找尋方式的是（D）。、廣度優(yōu)先B、最小耗資優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先12以下算法中平常以深度優(yōu)先方式系統(tǒng)找尋問題解的是（D）。A、備忘錄法B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法13.一個(gè)問題可用動(dòng)向規(guī)劃算法或貪婪算法求解的重點(diǎn)特色是問題的（B）。A、重疊子問題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪婪選擇性

15、質(zhì)D、定義最優(yōu)解14廣度優(yōu)先是（A）的一找尋方式。A、分支界限法B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法15背包問題的貪婪算法所需的計(jì)算時(shí)間為（B）。A、O（n2）nB、O（nlogn）C、O（2）nD、O（n）16實(shí)現(xiàn)最大子段和利用的算法是（B）。、分治策略B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法17實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（A）。、分治法B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法下邊是貪婪算法的基本因素的是（C）。、重疊子問題B、結(jié)構(gòu)最優(yōu)解C、貪婪選擇性質(zhì)D、定義最優(yōu)解回溯法的效率不依靠于以下哪些因素（D）A.知足顯拘束的值的個(gè)數(shù)C.計(jì)算限界函數(shù)的時(shí)間B.計(jì)算拘束函數(shù)的時(shí)間D.確立解空間的時(shí)間下邊哪一種函

16、數(shù)是回溯法中為防范無效找尋采納的策略（B）A遞歸函數(shù)剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.找尋函數(shù)21、以深度優(yōu)先方式系統(tǒng)找尋問題解的算法稱為(D)。A、分支界限算法B、概率算法C、貪婪算法D、回溯算法22、貪婪算法與動(dòng)向規(guī)劃算法的主要差別是（B）。、最優(yōu)子結(jié)構(gòu)B、貪婪選擇性質(zhì)C、結(jié)構(gòu)最優(yōu)解D、定義最優(yōu)解采納最大效益優(yōu)先找尋方式的算法是（A）。、分支界限法B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法（D）是貪婪算法與動(dòng)向規(guī)劃算法的共同點(diǎn)。A、重疊子問題B、結(jié)構(gòu)最優(yōu)解C、貪婪選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)25.矩陣連乘問題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)向規(guī)劃算法C、貪婪算法D、回溯算法26.0-1背包問

17、題的回溯算法所需的計(jì)算時(shí)間為（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）27、背包問題的貪婪算法所需的計(jì)算時(shí)間為（B）A、O（n2）B、O（nlogn）C、O（2）D、O（n）29、使用分治法求解不需要知足的條件是（A）。A子問題必然是同樣的B子問題不可以夠夠重復(fù)C子問題的解能夠合并D原問題和子問題使用同樣的方法解30、下邊問題（B）不可以夠使用貪婪法解決。nnA單源最短路徑問題BN皇后問題C最小開支生成樹問題D背包問題31、以下算法中不可以夠解決0/1背包問題的是（A）A貪婪法B動(dòng)向規(guī)劃C回溯法D分支限界法32、回溯法找尋狀態(tài)空間樹是依據(jù)（C）的次序。A中序遍歷B廣度

18、優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷33、采納廣度優(yōu)先策略找尋的算法是（A）。、分支界限法B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法34實(shí)現(xiàn)合并排序利用的算法是（A）。A、分治策略B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法35以下是動(dòng)向規(guī)劃算法基本因素的是（D）。A、定義最優(yōu)解B、結(jié)構(gòu)最優(yōu)解C、算出最優(yōu)解D、子問題重疊性質(zhì)36以下算法中平常以自底向下的方式求解最優(yōu)解的是（B）。A、分治B、動(dòng)向規(guī)劃法C、貪婪法D、回溯法二、填空題算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。2、程序是算法用某種程序設(shè)計(jì)語言的詳細(xì)實(shí)現(xiàn)。3、算法的“確立性”指的是構(gòu)成算法的每條指令是清楚的，無歧義的。矩陣連乘問題的算法可由動(dòng)向規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。5、算法是指解決問題的一種方法或一個(gè)過程。6、迅速排序算法的性能取決于區(qū)分的對(duì)稱性。7、從分治法的一般設(shè)計(jì)模式能夠看出，用它設(shè)計(jì)出的程序一般是遞歸算法8、問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)向規(guī)劃算法或貪婪算法求解的重點(diǎn)特色。9、以深度優(yōu)先方式系統(tǒng)找尋問題解的算法稱為回溯法。10、任何可用計(jì)算機(jī)求解的問題所需的時(shí)間都與其規(guī)模有關(guān)。11、計(jì)算一個(gè)算法時(shí)間復(fù)雜度平常能夠計(jì)算或計(jì)算步。循環(huán)次數(shù)、基本操作的頻次12、回溯法找尋解空間樹時(shí)，常用的兩種剪枝函數(shù)為拘束函數(shù)和限界函數(shù)14、解決0/1背