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

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

11、概率算法的一個(gè)根本特征是對(duì)所求解問(wèn)題的同一實(shí)例用同一概率算法，求解兩次可能得到完全不同的效果。1、貪心算法的核心是排序（×）2、貪心算法對(duì)所有問(wèn)題都能得到整體最優(yōu)解（√）3、0/1背包問(wèn)題和背包問(wèn)題都可以用貪心法求解（×）4、概率算法在執(zhí)行過(guò)程中每一計(jì)算步驟都是確定的（×）1、為什么分治法與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)中？答：因?yàn)榉种畏▽?duì)原問(wèn)題分小之后的子問(wèn)題與原問(wèn)題在特性上保持一致，只是規(guī)?？s小，這正好符合遞歸函數(shù)的性質(zhì)。5分2、表達(dá)回溯法解題通常的三個(gè)步驟。①針對(duì)所給問(wèn)題，定義問(wèn)題的解空間②確定易于搜索的解空間構(gòu)造③以深度優(yōu)先的方式并且在搜索過(guò)程中用剪枝函數(shù)防止無(wú)效搜索3分3、表達(dá)回溯法與分支限界算法的異同之處。都是在問(wèn)題的過(guò)約束條件，而分支限界法不僅通過(guò)約束條件，而且通過(guò)目標(biāo)函數(shù)的限界來(lái)減少無(wú)效搜索，回溯法采用深度優(yōu)先策略，而分支限界法狀態(tài)空間樹(shù)上搜索解，但求解目標(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、說(shuō)出優(yōu)先隊(duì)列式分支限界法解題的詳細(xì)步驟。①針對(duì)所給問(wèn)題，定義問(wèn)題的解空間②定義上界和下界③以先廣后深的方式搜索狀態(tài)空間樹(shù)，并且在搜索過(guò)程中用剪枝函數(shù)防止無(wú)效搜索7、說(shuō)出教材中所介紹的五種主要算法，并對(duì)每一種算法舉出一個(gè)典型。求解的例子（不必寫出每種詳細(xì)解法過(guò)程）。分治法、動(dòng)態(tài)規(guī)劃、貪心法、回溯法、分支限界法（1，1，0，0，1）、（1，0，1，1）、（0，0，1，0，0，1）分別對(duì)應(yīng)于：5+10+15=305+12+13=3012+18=30實(shí)際生成的狀態(tài)空間樹(shù)2、某公司訂購(gòu)4箱海