計算機系2005下半年算法考題b卷

1、計算機系2005下半年算法考題B卷1.畫出RAM機的結(jié)構(gòu)示意圖，并簡述其工作方式。2.設(shè)某一算法的時間復(fù)雜性為，請給出它的表示。log!n?3.列出常用指數(shù)時間的算法復(fù)雜性之間的關(guān)系，說明不等式成立的條件并解釋有效算法的含義。4.設(shè)有處理同一個問題的兩個不同算法和，其時間復(fù)雜性分別為和，請討1A2A2n28n論這兩個算法的優(yōu)劣。5.用貪心法求解矩陣乘積問題時，一定能夠等到最優(yōu)解嗎為什么6.用貪心法求解以下最優(yōu)裝載問題：輪船的裝載量為，個

2、集裝箱的重量分別為4008，在裝載體積不受限12345678()(1002005090150502080)wwwwwwww?制的情況下，將盡可能多的集裝箱裝上輪船。7.(1).用分治法求n個元素的集合S中最大元素和最小元素。這里假設(shè)n=2^m要求每次平分成兩個子集寫出算法并分析其時間復(fù)雜性(按照比較次數(shù))。(2).寫出每次平分成三個子集的時間復(fù)雜性，并分析得到的結(jié)果。并分析得到的結(jié)果。8.寫出使用分治法所得到的最常見的時間復(fù)雜性函數(shù)，并

3、解釋式中各項的含義。給出求解給出求解的一般形式。的一般形式。9.證明動態(tài)規(guī)劃求解貨郎擔(dān)問題的空間復(fù)雜性是。(2)nOnA10.用動態(tài)規(guī)劃的后向處理法后向處理法，求解下圖中從s到t的最小成本路徑。123456789104231096710384896548411.用分支限界法求解背包問題。給定一個裝載量為的背包及重量分別為0115的個物體。1234()(2469)wwww?412.利用余數(shù)以及倒推法求解水罐問題：兩個沒有刻度的水罐，分別能