東北大學(xué)《算法設(shè)計(jì)與分析》試題與答案

算法設(shè)計(jì)與分析一、選擇題.算法的復(fù)雜性是（A）的度量，是評價(jià)算法優(yōu)劣的重要依據(jù)。時(shí)間效率算法效率空間效率輸出效率.衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C）。運(yùn)行速度快占用空間少時(shí)間復(fù)雜度低代碼短.算法分析的兩個(gè)主要方面是（A）?？臻g復(fù)雜度和時(shí)間復(fù)雜度正確性和簡單性可讀性程序復(fù)雜度.計(jì)算機(jī)算法指的是（C）。計(jì)算方法排序方法解決問題的方法和過程調(diào)度方法.多階段決策問題就是要在可以選擇的那些策略中間選取一個(gè)（A）策略使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果。最優(yōu)最差平衡任意.下列關(guān)于算法的說法中正確的有（C）個(gè)。（1）求解某一類問題的算法是唯一的；（2）算法必須在有限步操作后停止;（3）算法的每一步操作是明確的,不能有歧義或含義模糊;（4）算法執(zhí)行后一定產(chǎn)生確定的結(jié)果。A.1B.2C.3D.4.（C）是指算法執(zhí)行時(shí)所需計(jì)算機(jī)資源的多少,包括運(yùn)行時(shí)間和存儲空間兩個(gè)方面的要求。正確性可讀性效率D.健壯性.對于簡單的輸入,輸出和賦值語句,執(zhí)行時(shí)間為（A）。O（1）O（n）O（n*n）都不對.算法點(diǎn)的空間復(fù)雜度是指（A）。算法在執(zhí)行過程中所需的計(jì)算機(jī)存儲空間算法所處理的數(shù)據(jù)量算法程序中的語句或指令的條數(shù)算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù).算法點(diǎn)的時(shí)間復(fù)雜度是指（D）。算法的執(zhí)行時(shí)間算法所處理的數(shù)據(jù)量算法程序中的語句或指令的條數(shù)算法在執(zhí)行過程中所需要的基本運(yùn)算次數(shù).下列哪一種算法不是隨機(jī)化算法（C）。遺傳算法模擬退火算法動態(tài)規(guī)劃算法模特卡羅算法.下面不是動態(tài)規(guī)劃算法基本步驟的是（A）。找出最優(yōu)解的性質(zhì)構(gòu)造最優(yōu)解算出最優(yōu)解定義最優(yōu)解.下列是動態(tài)規(guī)劃算法基本要素的是（D）。定義最優(yōu)解構(gòu)造最優(yōu)解算出最優(yōu)解子問題重疊性質(zhì).采用廣度優(yōu)先策略搜索的算法是（A）。分支定界法動態(tài)規(guī)劃法貪婪法回溯法.通常以自底向上的方式求解最優(yōu)解的是（B）。分支定界法動態(tài)規(guī)劃法貪婪法回溯法.最優(yōu)性原理是（B）的基礎(chǔ)。分支定界法動態(tài)規(guī)劃法貪婪法回溯法.在對問題的解空間樹進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會成為活結(jié)點(diǎn)的是（B）?；厮莘ǚ种Фń绶ɑ厮莘ê头种Фń绶ɑ厮莘ㄇ蠼庾蛹瘶鋯栴}.下面不是分支定界法搜索方式的是（D）。廣度優(yōu)先最小耗費(fèi)優(yōu)先C.最大效益優(yōu)先D.深度優(yōu)先.下面（C）不是分支定界法的優(yōu)點(diǎn)?？梢郧蟮米顑?yōu)解平均速度快很少占內(nèi)存空間檢查子問題較少.二分搜索算法的時(shí)間復(fù)雜度（C）。O（logn*n）O（nlogn）O（logn）O（n）.使用分治法求解不需要滿足的條件是（A）。子問題必須是一樣的問題不能夠重復(fù)子問題的解可以合并原問題和子問題使用相同的方法解.與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題（A）。經(jīng)分解得到子問題往往不是互相獨(dú)立的經(jīng)分解得到子問題往往是互相獨(dú)立的經(jīng)分解得到子問題往往是互相交叉的經(jīng)分解得到子問題往往是任意的.直接或間接的調(diào)用自身的算法稱為（B）。貪婪算法遞歸算法迭代算法動態(tài)規(guī)劃算法.應(yīng)用分治法的兩個(gè)前提是（A）。問題的可分性和解的可歸并性問題的可分性和解的存在性問題的復(fù)雜性和解的可歸并性問題的可分性和解的復(fù)雜性.分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題(C)。問題規(guī)模相同，問題性質(zhì)相同問題規(guī)模相同，問題性質(zhì)不同問題規(guī)模不同，問題性質(zhì)相同問題規(guī)模不同，問題性質(zhì)不同.下面是貪婪算法的基本要素的是(C)。重疊子問題構(gòu)造最優(yōu)解貪婪選擇性質(zhì)定義最優(yōu)解二、問答題與算法運(yùn)行時(shí)所占用的存儲空間相關(guān)的因素有哪些？存儲算法本身所占的存儲空間；算法的輸入輸出數(shù)據(jù)所占的空間；算法在運(yùn)行過程中所需的輔助變量占用的存儲空間。遺傳算法有哪些理論基礎(chǔ)?數(shù)學(xué)基