《計算機(jī)算法基礎(chǔ)》試題及答案「完整版」

《計算機(jī)算法根底》試題及答案「完整版」1、算法是指解決問題的一種方法或一個過程，更嚴(yán)格地講，算法是由假設(shè)干條指令組成的有窮序列，且滿足下述4條性質(zhì)：輸入、輸出、確定性、有限性。2、算法的時間復(fù)雜性是指需要時間的量，它依賴于求解問題的要解的問題的規(guī)模、算法的輸入、算法本身的函數(shù)。4、選擇算法的一個重要準(zhǔn)那么是復(fù)雜性最低。5、一個直接或間接地調(diào)用身的算法稱為遞歸算法，一個使用函數(shù)自身定義的函數(shù)稱為遞歸函數(shù)，每個遞歸函數(shù)都必須有非遞歸定的的初始值。6、關(guān)于N個字符的哈夫曼算法的計算時間為O（nlogn）。7、回溯法解題時常遇到的兩類典型解空間是樹：a：排列、樹b：子集樹，假設(shè)問題有N個元素，其中樹通常有a2?個葉結(jié)點(diǎn)，其結(jié)點(diǎn)總個數(shù)為n！2^(n+1)-1，遍歷它的任何算法均需Ω（n?。│福??）的計算時間。8、一個問題能用動態(tài)規(guī)劃算法求解的兩個重要特征是最優(yōu)子構(gòu)造和計算重要性。9、回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它按照深度優(yōu)先用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹、用限界函數(shù)剪去不能得到最優(yōu)解的子樹優(yōu)先的策略對空間樹進(jìn)展搜索，通常采用如下兩種策略來防止無效搜索，提高回溯法的搜索效，其一是剪枝函數(shù)，其二是遞歸回溯，這兩類函數(shù)統(tǒng)稱為選代回溯。10、分支限界法最常見的兩種方式分別是隊列式（FIFO）分支限界法和優(yōu)先隊列式分支限界法。

11、概率算法的一個根本特征是對所求解問題的同一實(shí)例用同一概率算法，求解兩次可能得到完全不同的效果。1、貪心算法的核心是排序（×）2、貪心算法對所有問題都能得到整體最優(yōu)解（√）3、0/1背包問題和背包問題都可以用貪心法求解（×）4、概率算法在執(zhí)行過程中每一計算步驟都是確定的（×）1、為什么分治法與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計中？答：因?yàn)榉种畏▽υ瓎栴}分小之后的子問題與原問題在特性上保持一致，只是規(guī)?？s小，這正好符合遞歸函數(shù)的性質(zhì)。5分2、表達(dá)回溯法解題通常的三個步驟。①針對所給問題，定義問題的解空間②確定易于搜索的解空間構(gòu)造③以深度優(yōu)先的方式并且在搜索過程中用剪枝函數(shù)防止無效搜索3分3、表達(dá)回溯法與分支限界算法的異同之處。都是在問題的過約束條件，而分支限界法不僅通過約束條件，而且通過目標(biāo)函數(shù)的限界來減少無效搜索，回溯法采用深度優(yōu)先策略，而分支限界法狀態(tài)空間樹上搜索解，但求解目標(biāo)不同；回溯法只通采用先廣后深的策略。4、表達(dá)分支限界算法的分支和限界的涵意。分支：剪去不何能產(chǎn)生最優(yōu)答案結(jié)點(diǎn)限界：包括上界函數(shù)U和下界函數(shù)C*(X所有C*(X)>U的結(jié)點(diǎn)被殺死5、解釋什么是活結(jié)點(diǎn)，擴(kuò)展結(jié)點(diǎn)，死結(jié)點(diǎn)？

活結(jié)點(diǎn)：被激活后還未完全生成其兒子結(jié)點(diǎn)的結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)：當(dāng)前正在生成其兒子結(jié)點(diǎn)的結(jié)點(diǎn)死結(jié)點(diǎn)：已生成完其兒子結(jié)點(diǎn)的結(jié)點(diǎn)6、說出優(yōu)先隊列式分支限界法解題的詳細(xì)步驟。①針對所給問題，定義問題的解空間②定義上界和下界③以先廣后深的方式搜索狀態(tài)空間樹，并且在搜索過程中用剪枝函數(shù)防止無效搜索7、說出教材中所介紹的五種主要算法，并對每一種算法舉出一個典型。求解的例子（不必寫出每種詳細(xì)解法過程）。分治法、動態(tài)規(guī)劃、貪心法、回溯法、分支限界法（1，1，0，0，1）、（1，0，1，1）、（0，0，1，0，0，1）分別對應(yīng)于：5+10+15=305+12+13=3012+18=30實(shí)際生成的狀態(tài)空間樹2、某公司訂購4箱海