計(jì)算機(jī)系2005下半年算法考題b卷

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

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

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