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

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

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

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

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

5、定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運輸費用與新的一堆中集裝箱數(shù)成正比。 給定各堆的集裝箱數(shù)，試制定一個運輸方案，使總運輸費用最少。設(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個人，每個人都可以完成n種不同的任務(wù)，但所需時間不同。如果只需一人去完成每一項工作，則應(yīng)如何分配n個人并使完成所有n項工作的總時間為最小。考慮n=4的情況人 工作

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