算法分析與設(shè)計(jì)考試

1、算法設(shè)計(jì)與分析年級(jí)測(cè)試（90分鐘）學(xué)號(hào)112012_ 班級(jí)_ 成績(jī)_（40分）填空題（請(qǐng)作答到答題紙上）：（3分）標(biāo)準(zhǔn)復(fù)雜性函數(shù)的漸近時(shí)間復(fù)雜度之間的關(guān)系（排序）O(n)、O(logn) 、O(n!) 、O(nn)、O(nlogn)、O(n2) 、O(2n)、O(1)、O(n3)_（3分）有效算法的定義：_（3分）分治法的求解步驟：分治法在每一層遞歸上有三個(gè)步驟：（ ）、（ ）和（ ）（1分）二分搜索方法利用分治策略，可在最壞情況下用_時(shí)間完成搜索任務(wù)。（6分）快速排序：取序列的一個(gè)元素作為（ ） ，利用這個(gè)軸把序列分成（ ）、（ ）和（ ）, 使（ ）中的元素都（ ）軸（本空填大小關(guān)系），（

2、 ）中的元素都（ ）軸（本空填大小關(guān)系）。（這個(gè)過程稱做對(duì)序列的（ ）（ ）可以獨(dú)立排序,最后將（ ）即可。上面的過程可以遞歸地執(zhí)行，直到（ ），最壞時(shí)間復(fù)雜度：（ ），平均時(shí)間復(fù)雜度/最好時(shí)間復(fù)雜度：（ ），輔助空間大?。?）。（2分）貪心算法求解的問題一般具有2個(gè)重要的性質(zhì)：（ ）和（ ）（8分）子集樹與排列樹遍歷子集樹時(shí)間復(fù)雜度（ ），有（ ）個(gè)葉節(jié)點(diǎn)。遍歷排列樹時(shí)間復(fù)雜度（ ），有（ ）葉節(jié)點(diǎn)。搜索從（ ）出發(fā)，以DFS搜索整個(gè)解空間。開始結(jié)點(diǎn)成為一個(gè)（ ），同時(shí)也成為當(dāng)前的（ ）。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處向縱深方向移至一個(gè)新結(jié)點(diǎn)，并成為一個(gè)（ ），也成為當(dāng)前（ ）。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不

3、能再向縱深方向擴(kuò)展，則（ ）。此時(shí)，應(yīng)（ ）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的（ ） ；直至（ ）。（2分）動(dòng)態(tài)規(guī)劃的思想實(shí)質(zhì)是（ ）和（ ）。（4分）動(dòng)態(tài)規(guī)劃的求解步驟（四步）：（ ）（ ）（ ）和（ ）。（4分）分支限界法與回溯法的區(qū)別（四條）：（ ）（ ）（ ）和（ ）。（4分）假設(shè)某算法在輸入規(guī)模為n的時(shí)間復(fù)雜性為T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒。現(xiàn)在另一計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為_。（20分）簡(jiǎn)答題（請(qǐng)作答到答題紙上）：（4分）問請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算

4、（主要是對(duì)于給出的算法推導(dǎo)T(n)）X = X = Y = X = 11111 11100 01100 00110 01010Y = 10101 01011 10000 11100 01110T(n)=（3分）用歐幾里德(Euclid)算法寫出計(jì)算下面輸入輸出要求的過程輸入 正整數(shù)24,18輸出 24和18的最大公因子（3分）遞歸算法的定義（5分）算法的特征及評(píng)價(jià)算法的標(biāo)準(zhǔn)。（5分）動(dòng)態(tài)規(guī)劃與分治法類似的是什么以及與分治法不同的是什么？（40分）算法題（請(qǐng)作答到答題紙上）：（10分）動(dòng)態(tài)規(guī)劃貨物儲(chǔ)運(yùn)問題：在一個(gè)鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲(chǔ)運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)

5、定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費(fèi)用與新的一堆中集裝箱數(shù)成正比。 給定各堆的集裝箱數(shù)，試制定一個(gè)運(yùn)輸方案，使總運(yùn)輸費(fèi)用最少。設(shè)每堆重量為：4,2,3,4（10分）貪心最優(yōu)裝載：輪船載重為c，集裝箱重量為wi，在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船：假設(shè)n =8, w1, . ,w8=100,200,50,90,150,50,20,80, c=400。（10分）分支限界（不要用dp）分配問題：設(shè)有n個(gè)人，每個(gè)人都可以完成n種不同的任務(wù)，但所需時(shí)間不同。如果只需一人去完成每一項(xiàng)工作，則應(yīng)如何分配n個(gè)人并使完成所有n項(xiàng)工作的總時(shí)間為最小?？紤]n=4的情況人 工作

6、1234A21097B154148C13141611D415139（10分）回溯法解4后問題：設(shè)有一4*4的棋盤，把4個(gè)皇后放在棋盤上，要求滿足下列兩個(gè)條件：1）任意兩個(gè)皇后不在同一行上和同一列上；2）任意兩個(gè)皇后不在同一條對(duì)角線上；問有多少種放法？Learn young, learn fair.There is no such thing as genius; it is nothing but labour and diligence.To be continued答題紙學(xué)號(hào)112012_ 班級(jí)_ 成績(jī)_填空題（40分）：（3分）答：_（3分）答：_（3分）答：_、_、_（1分）答：_（6分）答：_、_、_、_、_、_、_、_、_、_、_、_、_、_、_。(備用，若填寫不下寫在下面)（2分）答：_、_ （8分）答：_、_、_、_、_、_、_、_、_、_、_、_、_。(備用，若填寫不下寫在下面)（2分）答：_、_（4分）答：_、_、_、_（4分）答：_、_、_、