算法分析設(shè)計歷年題目

算法分析設(shè)計歷年題目1.判斷題.一個正確的算法，對于每個合法輸入，都會在有限的時間內(nèi)輸出一個滿足要求的結(jié)果。.NP完全問題比其他所有NP問題都要難。.回溯法用深度優(yōu)先法或廣度優(yōu)先法搜索狀態(tài)空間樹。.在動態(tài)規(guī)劃中，各個階段所確定的策略就構(gòu)成一個策略序列，通常稱為一個決策。.P類和NP類問題的關(guān)系用PuNP來表示是錯誤的。.若近似算法A求解某極小化問題一實例的解為%,且已知該問題的最優(yōu)解為%/3,則該近似算法的性能比為3。.通常來說，算法的最壞情況的時間復(fù)雜行比平均情況的時間復(fù)雜性容易計算。.若P2多項式時間轉(zhuǎn)化為(polynomialtransformsto)Pl,則P2至少與Pl一樣難。.快速排序算法的平均時間復(fù)雜度是0(nlogn)，使用隨機化快速排序算法可以將平均時間復(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算法只要給出解就是正確的。.一個完全多項式近似方案是一個近似方案{A其中每一個算法人在輸入實例/的規(guī)模的多項式時間內(nèi)運行。2.問答題.二叉查找樹屬于減治策略的三個變種中的哪一個的應(yīng)用？什么情況下二叉查找樹表現(xiàn)出最差的效率？此時的查找和插入算法的復(fù)雜性如何？.何謂為多項式算法？如何將一MonteCarlo算法轉(zhuǎn)化為LasVegas算法？.構(gòu)造AVL樹和2-3數(shù)的主要目的是什么？它們各自有什么樣的查找和插入的效率？.寫出0/1背包問題的一個多項式等價(PolynomialEquivalent)的判定問題，并說明為什么它們是多項式等價的。.下面問題是否屬于NP問題？為什么？問題表述：給定圖G=(N,4)中的兩個點p、q,整數(shù)c和3圖G中每條邊的長度電?及便利這條邊的時間小?,問圖G中是否存在一條由p到q的路徑，使得其長度大于c,且遍歷時間小3.分治題.寫出一個求解下列問題的分治算法，推導(dǎo)其時間復(fù)雜性并與蠻力法相比較。給定互不相等的n個數(shù)的一個序列???1。九，若其中某兩個數(shù)四和由?的關(guān)系為：＞%且iV/,則稱七和內(nèi)?是逆序的。要求計算該序列中的逆序個數(shù)，即具有逆序關(guān)系的元素對的總數(shù)目。.A［l,…,可為一個整數(shù)序列，A中的整數(shù)a如果在A中出現(xiàn)次數(shù)多余［n/2j,那么。稱為多數(shù)元素。例如，在序列1,3,2,334,3中3是多數(shù)元素，因為出現(xiàn)了4次，大于［7/2］。求A的多數(shù)元素問題的蠻力算法復(fù)雜性如何？設(shè)計一個具有變治思想的算法，提高蠻力算法的效率，寫出偽代碼并分析其事件復(fù)雜性。4.動態(tài)規(guī)劃題.某工廠調(diào)查了解市場情況，估計在今后四個月內(nèi)，市場對其產(chǎn)品的需求量如下表所示。時期（月）需要量（產(chǎn)品單位）12342324已知：對每個月來講，生產(chǎn)一批產(chǎn)品的固定成本費為3（千元），若不生成，則為零。每生產(chǎn)單位產(chǎn)品的成本費為1（千元）。同時、在任何一個月內(nèi)，生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個單位。又知：每單位產(chǎn)品的庫存費用為每月0?5（千元），同時要求在第一個月開始之初，及在第四個月末，均無產(chǎn)品庫存。問：在滿足上述條件下，該廠應(yīng)如何安排各個時期的生產(chǎn)與庫存，使所花的總成本費用最低？寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式，和手工求解的詳細步驟及結(jié)果。.用動態(tài)規(guī)劃方法手工求解以下問題有8萬元的投資可以投給3個過目，每個項目在不同筒子數(shù)額下（以萬元為單位）的利潤如下表投資額盈利項目012345678項目105154080909598100項目20515406070737475項目30426404550515253請安排投資計劃，使總的利潤最大。寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式和手工求解的詳細步驟及結(jié)構(gòu)。5.分支定界題i.用分支定界法求解以下問題：某部門欲建立聯(lián)通分布于五個區(qū)的共50個站點的有線通訊網(wǎng)絡(luò)，每兩個站點之間的線路敷設(shè)費用由對成矩陣C給出，任意兩站點之間敷設(shè)線路需建設(shè)的地井數(shù)目由對稱矩陣U給出。設(shè)計一線路敷設(shè)總費用為最小的無環(huán)網(wǎng)絡(luò)，使得徐建設(shè)的總地井數(shù)目不超過UMAX,且需跨區(qū)敷設(shè)的線路總數(shù)目不超過DMAX（個站點所屬的區(qū)由向量D給出）。1）說明你是如何構(gòu)造搜索樹的。（要求是二叉搜索樹）2）說明算法遍歷搜索樹的原則。（何時以及如何前進、分支、回溯、剪枝等等）3）你設(shè)計的分支定界算法的“界”是什么，他為什么是正確的和有效的？4）寫出偽代碼。2.用分支定界法求解以下問題：A國與B國之間尚未直接通商。與A國直接通商的有20個國家（Cl,C2, C20）；與B國直接通商的為另外30個國家（C21,C22C50）o上述50個國家之間并不是每兩個國家都直接通商，任意兩國之間的貿(mào)易稅率由對稱矩陣R給出，其中8代表兩國不能直接通商。A國某公司與B國一公司欲通過某幾個中間國家的公司完成一筆貿(mào)易，各個國家的進出口貿(mào)易通關(guān)等手續(xù)所需辦理時間由向量T給出。請安排一中轉(zhuǎn)貿(mào)易計劃，使得該交易所產(chǎn)生的向各中轉(zhuǎn)國繳納的稅費最低，