![算法分析設(shè)計(jì)歷年題目_第1頁](http://file4.renrendoc.com/view/9123184501838876d106a6689e11f096/9123184501838876d106a6689e11f0961.gif)
![算法分析設(shè)計(jì)歷年題目_第2頁](http://file4.renrendoc.com/view/9123184501838876d106a6689e11f096/9123184501838876d106a6689e11f0962.gif)
![算法分析設(shè)計(jì)歷年題目_第3頁](http://file4.renrendoc.com/view/9123184501838876d106a6689e11f096/9123184501838876d106a6689e11f0963.gif)
下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
算法分析設(shè)計(jì)歷年題目1.判斷題.一個正確的算法,對于每個合法輸入,都會在有限的時間內(nèi)輸出一個滿足要求的結(jié)果。.NP完全問題比其他所有NP問題都要難。.回溯法用深度優(yōu)先法或廣度優(yōu)先法搜索狀態(tài)空間樹。.在動態(tài)規(guī)劃中,各個階段所確定的策略就構(gòu)成一個策略序列,通常稱為一個決策。.P類和NP類問題的關(guān)系用PuNP來表示是錯誤的。.若近似算法A求解某極小化問題一實(shí)例的解為%,且已知該問題的最優(yōu)解為%/3,則該近似算法的性能比為3。.通常來說,算法的最壞情況的時間復(fù)雜行比平均情況的時間復(fù)雜性容易計(jì)算。.若P2多項(xiàng)式時間轉(zhuǎn)化為(polynomialtransformsto)Pl,則P2至少與Pl一樣難。.快速排序算法的平均時間復(fù)雜度是0(nlogn),使用隨機(jī)化快速排序算法可以將平均時間復(fù)雜度降得更低。.基于比較的尋找數(shù)組A[1,…,可中最大元素的問題下屆是。(幾/3)。.0(/(^))+。(。(幾))=0(min{f(n),g(7i)}).若/(幾)=C(g(n)),g(n)=。(八(九)),則/(九)=(1(八(九)).若f(n)=0(^(n)),則g(n)=0(/(n)).貪婪技術(shù)所做的每一步選擇所產(chǎn)生的部分解,不一定是可行性的。.LasVegas算法只要給出解就是正確的。.一個完全多項(xiàng)式近似方案是一個近似方案{A其中每一個算法人在輸入實(shí)例/的規(guī)模的多項(xiàng)式時間內(nèi)運(yùn)行。2.問答題.二叉查找樹屬于減治策略的三個變種中的哪一個的應(yīng)用?什么情況下二叉查找樹表現(xiàn)出最差的效率?此時的查找和插入算法的復(fù)雜性如何?.何謂為多項(xiàng)式算法?如何將一MonteCarlo算法轉(zhuǎn)化為LasVegas算法?.構(gòu)造AVL樹和2-3數(shù)的主要目的是什么?它們各自有什么樣的查找和插入的效率?.寫出0/1背包問題的一個多項(xiàng)式等價(jià)(PolynomialEquivalent)的判定問題,并說明為什么它們是多項(xiàng)式等價(jià)的。.下面問題是否屬于NP問題?為什么?問題表述:給定圖G=(N,4)中的兩個點(diǎn)p、q,整數(shù)c和3圖G中每條邊的長度電?及便利這條邊的時間小?,問圖G中是否存在一條由p到q的路徑,使得其長度大于c,且遍歷時間小3.分治題.寫出一個求解下列問題的分治算法,推導(dǎo)其時間復(fù)雜性并與蠻力法相比較。給定互不相等的n個數(shù)的一個序列???1。九,若其中某兩個數(shù)四和由?的關(guān)系為:>%且iV/,則稱七和內(nèi)?是逆序的。要求計(jì)算該序列中的逆序個數(shù),即具有逆序關(guān)系的元素對的總數(shù)目。.A[l,…,可為一個整數(shù)序列,A中的整數(shù)a如果在A中出現(xiàn)次數(shù)多余[n/2j,那么。稱為多數(shù)元素。例如,在序列1,3,2,334,3中3是多數(shù)元素,因?yàn)槌霈F(xiàn)了4次,大于[7/2]。求A的多數(shù)元素問題的蠻力算法復(fù)雜性如何?設(shè)計(jì)一個具有變治思想的算法,提高蠻力算法的效率,寫出偽代碼并分析其事件復(fù)雜性。4.動態(tài)規(guī)劃題.某工廠調(diào)查了解市場情況,估計(jì)在今后四個月內(nèi),市場對其產(chǎn)品的需求量如下表所示。時期(月)需要量(產(chǎn)品單位)12342324已知:對每個月來講,生產(chǎn)一批產(chǎn)品的固定成本費(fèi)為3(千元),若不生成,則為零。每生產(chǎn)單位產(chǎn)品的成本費(fèi)為1(千元)。同時、在任何一個月內(nèi),生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個單位。又知:每單位產(chǎn)品的庫存費(fèi)用為每月0?5(千元),同時要求在第一個月開始之初,及在第四個月末,均無產(chǎn)品庫存。問:在滿足上述條件下,該廠應(yīng)如何安排各個時期的生產(chǎn)與庫存,使所花的總成本費(fèi)用最低?寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式,和手工求解的詳細(xì)步驟及結(jié)果。.用動態(tài)規(guī)劃方法手工求解以下問題有8萬元的投資可以投給3個過目,每個項(xiàng)目在不同筒子數(shù)額下(以萬元為單位)的利潤如下表投資額盈利項(xiàng)目012345678項(xiàng)目105154080909598100項(xiàng)目20515406070737475項(xiàng)目30426404550515253請安排投資計(jì)劃,使總的利潤最大。寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式和手工求解的詳細(xì)步驟及結(jié)構(gòu)。5.分支定界題i.用分支定界法求解以下問題:某部門欲建立聯(lián)通分布于五個區(qū)的共50個站點(diǎn)的有線通訊網(wǎng)絡(luò),每兩個站點(diǎn)之間的線路敷設(shè)費(fèi)用由對成矩陣C給出,任意兩站點(diǎn)之間敷設(shè)線路需建設(shè)的地井?dāng)?shù)目由對稱矩陣U給出。設(shè)計(jì)一線路敷設(shè)總費(fèi)用為最小的無環(huán)網(wǎng)絡(luò),使得徐建設(shè)的總地井?dāng)?shù)目不超過UMAX,且需跨區(qū)敷設(shè)的線路總數(shù)目不超過DMAX(個站點(diǎn)所屬的區(qū)由向量D給出)。1)說明你是如何構(gòu)造搜索樹的。(要求是二叉搜索樹)2)說明算法遍歷搜索樹的原則。(何時以及如何前進(jìn)、分支、回溯、剪枝等等)3)你設(shè)計(jì)的分支定界算法的“界”是什么,他為什么是正確的和有效的?4)寫出偽代碼。2.用分支定界法求解以下問題:A國與B國之間尚未直接通商。與A國直接通商的有20個國家(Cl,C2, C20);與B國直接通商的為另外30個國家(C21,C22C50)o上述50個國家之間并不是每兩個國家都直接通商,任意兩國之間的貿(mào)易稅率由對稱矩陣R給出,其中8代表兩國不能直接通商。A國某公司與B國一公司欲通過某幾個中間國家的公司完成一筆貿(mào)易,各個國家的進(jìn)出口貿(mào)易通關(guān)等手續(xù)所需辦理時間由向量T給出。請安排一中轉(zhuǎn)貿(mào)易計(jì)劃,使得該交易所產(chǎn)生的向各中轉(zhuǎn)國繳納的稅費(fèi)最低,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 涂裝后處理工初級模擬試題
- 生物質(zhì)能源利用的全球視野與本土實(shí)踐
- 數(shù)字貨幣支付解決方案考核試卷
- 現(xiàn)代職場中的著裝搭配與形象設(shè)計(jì)
- 2025-2030年戶外野營教育體驗(yàn)行業(yè)跨境出海戰(zhàn)略研究報(bào)告
- 2025-2030年護(hù)眼臺燈行業(yè)跨境出海戰(zhàn)略研究報(bào)告
- 2025-2030年口腔正畸力學(xué)模擬軟件行業(yè)跨境出海戰(zhàn)略研究報(bào)告
- 2025-2030年口腔護(hù)理片行業(yè)跨境出海戰(zhàn)略研究報(bào)告
- 2025-2030年增強(qiáng)現(xiàn)實(shí)服裝定制企業(yè)制定與實(shí)施新質(zhì)生產(chǎn)力戰(zhàn)略研究報(bào)告
- 2025-2030年插畫藝術(shù)工作坊連鎖行業(yè)跨境出海戰(zhàn)略研究報(bào)告
- 膿包瘡護(hù)理查房
- 《信號工程施工》課件 項(xiàng)目一 信號圖紙識讀
- 設(shè)備日常維護(hù)及保養(yǎng)培訓(xùn)
- 設(shè)計(jì)院個人年終總結(jié)
- 中石油高空作業(yè)施工方案
- 避孕藥具知識培訓(xùn)
- 醫(yī)保違規(guī)檢討書
- 鋼結(jié)構(gòu)實(shí)習(xí)報(bào)告
- 2024年建房四鄰協(xié)議范本
- FTTR-H 全光組網(wǎng)解決方案裝維理論考試復(fù)習(xí)試題
- 2024年廣東佛山市中醫(yī)院三水醫(yī)院招聘61人歷年高頻考題難、易錯點(diǎn)模擬試題(共500題)附帶答案詳解
評論
0/150
提交評論