2021年算法分析與設(shè)計(jì)期末考試試卷B卷

1、 3/32021年算法分析與設(shè)計(jì)期末考試試卷B卷 西南交通大學(xué)2015 2016學(xué)年第(一)學(xué)期考試試卷 課程代碼 3244152課程名稱 算法分析與設(shè)計(jì) 考試時(shí)間 120分鐘 閱卷教師簽字： _ 填空題(每空1分，共15分) 1、 程序是 (1) 用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。 2、 矩陣連乘問題的算法可由 (2) 設(shè)計(jì)實(shí)現(xiàn)。 3、 從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是 (3) 4、 大整數(shù)乘積算法是用 (4) 來設(shè)計(jì)的。 5、 貪心算法總是做出在當(dāng)前看來 (5) 的選擇。也就是說貪心算法并不從整體最優(yōu) 考慮，它所做出的選擇只是在某種意義上的 (6) o 6、 回溯法是一種

2、既帶有 (7) 又帶有 (8) 的搜索算法。 7、 平衡二叉樹對于查找算法而言是一種變治策略，屬于變治思想中的 (9) 類型 8、 在忽略常數(shù)因子的情況下，0、門和0三個(gè)符號中， (10) 提供了算法運(yùn)行時(shí) 間的一個(gè)上界。 9、 算法的“確定性”指的是組成算法的每條 (11) 是清晰的，無歧義的。 10、 冋題的(12) 是該冋題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 11、 算法就是一組有窮 (13)，它們規(guī)定了解決某一特定類型問題的 (14) o 12、 變治思想有三種主要的類型：實(shí)例化簡，改變表現(xiàn)， (15) o 、 _ L 線訂裝封密 線訂裝封密 、 _ 二 線訂裝封密 級班 選擇

3、題(每題2分，共20 分) 1、二分搜索算法是利用（）實(shí)現(xiàn)的算法。 A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法 2、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（）。 A、運(yùn)行速度快 B、占用空間少 C、時(shí)間復(fù)雜度低 D、代碼短 3、能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為：（） A.最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B ?重疊子問題性質(zhì)與貪心選擇性質(zhì) C ?最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì) D.預(yù)排序與遞歸調(diào)用 4、常見的兩種分支限界法為（） A、廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法； B、隊(duì)列式（FIFO ）分支限界法與堆棧式分支限界法； C 、排列樹法與子集樹法； D、隊(duì)列式（FIFO ）分支限界法與優(yōu)先隊(duì)列式分支限界法; 5、實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（） A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法 6、回溯法的效率不依賴于下列哪些因素（） A. 滿足顯約束的值的個(gè)數(shù) B. 計(jì)算約束函數(shù)的時(shí)間 C. 計(jì)算限界函數(shù)的時(shí)間 D. 確定解空間的時(shí)間 7、 A、子問題必須是一樣的 C、子問題的解可以合并 8、實(shí)現(xiàn)合并排序利用的算法是（ A、分治策略 B、動(dòng)態(tài)規(guī)劃法B、子