算法設(shè)計與分析-模擬題答案 地質(zhì)大學2023年期末考試復習

《算法設(shè)計與分析》模擬題一.單選題1.下面關(guān)于程序和算法的說法錯誤的是（）A.算法必須在有窮時間終止B.程序是算法用某種程序設(shè)計語言的具體實現(xiàn)C.程序總是在有窮步的運算后終止D.算法可以使用自然語言描述,但要保證無歧義[正確答案選擇是]:C2.從長度為n的數(shù)組中多次查找數(shù)據(jù),使用（）方法好。A.順序查找B.隨機查找C.排序后折半查找D.無序查找[正確答案選擇是]:C3.待排序文件基本有序時,下面哪種排序方法,效率最高?A.堆排序B.快速排序C.冒泡排序D.歸并排序[正確答案選擇是]:C4.最大獨立集問題,如果在10億次每秒的計算機上運行,100年可以計算的圖的規(guī)模估計是?A.10B.50C.100D.150[正確答案選擇是]:B5.分塊查找256個元素的數(shù)組,分成（）塊最好?A.8B.16C.32D.64[正確答案選擇是]:B6.以下不可以使用分治法求解的是（）。A.循環(huán)賽日程表B.最接近點對問題C.最大子段和問題D.0/1背包問題[正確答案選擇是]:D7.備忘錄方法使用（）的遞歸方式。A.自頂向下B.自高到低C.自低到高D.自底向上[正確答案選擇是]:A8.分治算法與動態(tài)規(guī)劃算法的不同點是（）A.遞推關(guān)系B.子問題獨立C.最優(yōu)子結(jié)構(gòu)D.小問題易求解[正確答案選擇是]:B9.確定第i階段的收益函數(shù)和從第i階段出發(fā)到第n階段所獲得收益的最優(yōu)值,建立動態(tài)規(guī)劃基本方程。這種方法是（）A.正推B.反推C.自頂向下D.自底向上[正確答案選擇是]:B10.下面哪種函數(shù)不是回溯法中為避免無效搜索采取的策略A.遞歸函數(shù)B.剪枝函數(shù)C.限界函數(shù)D.約束函數(shù)[正確答案選擇是]:A11.NP類問題可以（）。A.多項式時間計算B.指數(shù)時間驗證C.多項式時間驗證D.指數(shù)時間計算[正確答案選擇是]:C12.實現(xiàn)二分搜索利用的算法是（）。A.分治策略B.動態(tài)規(guī)劃法C.貪心法D.回溯法[正確答案選擇是]:A13.獲得解不一定是正確解的算法是（）。A.蒙特卡羅算法B.拉斯維加斯算法C.舍伍德算法D.數(shù)值隨機算法[正確答案選擇是]:A14.下面不是備忘錄算法特點的是（）A.遞推關(guān)系B.自頂向下計算C.最優(yōu)子結(jié)構(gòu)D.子問題獨立[正確答案選擇是]:D15.通常我們講的時間復雜度是（）情況下的時間復雜度。A.平均B.最好C.最壞D.任意[正確答案選擇是]:C16.（）生成子集,便于實現(xiàn)集合的操作。A.增量構(gòu)造法B.二進制法C.位向量法D.法向量法[正確答案選擇是]:B17.把任意一個最優(yōu)解逐漸變?yōu)樨澬乃惴ǖ慕?不會影響其最優(yōu)性。這種證明方法是（）A.領(lǐng)先B.反證C.交換論證D.界[正確答案選擇是]:C18.最大獨立集問題,如果在10億次每秒的計算機上運行,當n=50時,需要計算的時間估計是?A.1小時B.24小時C.1年D.100年[正確答案選擇是]:D19.下面有關(guān)枚舉算法說法錯誤的是（）A.枚舉法適用于問題的小規(guī)模實例B.減少枚舉變量可以減少枚舉算法的時間復雜度。C.在某些問題實例中枚舉是唯一的解決方法。D.蠻力是枚舉算法的一種[正確答案選擇是]:D20.下面關(guān)于時間復雜度的描述錯誤的是（）A.時間復雜度是最復雜部分的運行時間B.時間復雜度是關(guān)鍵操作的運行時間C.時間復雜度是在最壞情況下運行時間D.時間復雜度是在平均情況下的運行時間[正確答案選擇是]:D21.下面關(guān)于貪心算法的說法錯誤的是（）A.貪心算法的思想是尋求局部最優(yōu)解,逐步達到全局最優(yōu)解B.貪心算法總能找到可行解,但未必是最優(yōu)解。C.貪心算法的思想是依據(jù)貪婪準則作出決策,逐步構(gòu)造解值。D.未來不影響過去指的是無后效性的性質(zhì)。[正確答案選擇是]:D22.下面有關(guān)說法錯誤的是（）A.倒推法是從后向前推解問題的方法.B.有些問題采用倒推法,容易理解和解決。C.循環(huán)用于重復性的工作。循環(huán)體的特點是:“以不變應(yīng)萬變”D.高階遞推方程需要使用換元迭代化簡為一階方程求解。[正確答案選擇是]:D23.減少子問題合并的時間,就是減少時間復雜度函數(shù)T(n)=aT(n/b)+f(n)中的（）值。A.aB.bC.f(n)D.n[正確答案選擇是]:C24.下列算法中通常以自底向上的方式求解最優(yōu)解的是（）。A.分治法B.動態(tài)規(guī)劃法C.貪心法D.回溯[正確答案選擇是]:B25.一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（）。A.重疊子問題B.最優(yōu)子結(jié)構(gòu)性質(zhì)C.貪心選擇性質(zhì)D.定義最優(yōu)解[正確答案選擇是]:B26.下面不是動態(tài)規(guī)劃算法特點的是（）A.自底向上計算B.無后效性C.子問題獨立D.子問題重疊[正確答案選擇是]:C27.回溯法和分支限界法的主要區(qū)別在于,回溯法求取（）.A.一個解B.極大解C.極小解D.一個解或所有解[正確答案選擇是]:D28.算法復雜度分析的兩種方法是（）A.事前分析和事后統(tǒng)計B.最壞情況的復雜度和最好情況的復雜度C.最壞情況的復雜度和平均復雜度D.最好情況的復雜度和平均復雜度[正確答案選擇是]:A29.log10=（）A.θB.OC.WD.o[正確答案選擇是]:A30.順序查找長度為n的線性表,平均查找長度為（）A.nB.n/2C.(n+1)/2D.(n-1)/2[正確答案選擇是]:C31.給定圖G=(V,E),|V|=n,|E|=m,其鄰接表的空間復雜度為（）A.θ(m+n)B.θ(n)C.θ(mn)D.θ(n^2)[正確答案選擇是]:A32.下面不是以空間換時間的方法有（）A.預處理B.預構(gòu)造C.動態(tài)規(guī)劃D.數(shù)據(jù)壓縮[正確答案選擇是]:D33.分塊查找256個元素的數(shù)組,每塊的最佳長度是（）。A.8B.16C.32D.64[正確答案選擇是]:C34.未來與過去無關(guān),指的是（）性質(zhì)。A.貪心選擇B.無后效性C.最優(yōu)子結(jié)構(gòu)D.重疊子問題[正確答案選擇是]:B35.下面有關(guān)遞歸與遞推的說法錯誤的是（）A.遞歸是逆向的,從大規(guī)模的問題逐步到小規(guī)模間題。B.遞推是正向的,從小規(guī)模的問題推解出大規(guī)模間題。C.遞歸表現(xiàn)為自己調(diào)用自己,遞推則沒有這樣的形式。D.一般來說,遞歸的效率高于遞推[正確答案選擇是]:D36.中印戰(zhàn)爭西山口戰(zhàn)役劉伯承提出的“打頭、截尾、剖腹、擊背”是（）思想。A.貪心B.分治C.遞推D.枚舉[正確答案選擇是]:B37.動態(tài)規(guī)劃和分治算法的共同點是（）A.最優(yōu)子結(jié)構(gòu)性質(zhì)B.重疊子問題性質(zhì)C.加速原理D.貪婪準則[正確答案選擇是]:A38.備忘錄與遞歸算法的不同點是（）A.遞推關(guān)系B.自頂向下計算C.從大到小計算D.子問題重疊的計算[正確答案選擇是]:D39.回溯算法和分支限界法的問題的解空間樹不會是（）。A.有序樹B.子集樹C.排列樹D.無序樹[正確答案選擇是]:D40.分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解,二者（）。A.求解目標不同,搜索方式相同B.求解目標不同,搜索方式也不同C.求解目標相同,搜索方式不同D.求解目標相同,搜索方式也相同[正確答案選擇是]:B41.0-1背包問題的枚舉算法,如果在萬億次每秒的計算機上運行,1年可以計算的問題規(guī)模估計是?A.40B.60C.30D.50[正確答案選擇是]:B42.折半查找長度為n的線性表,平均查找長度為（）A.nB.lognC.nlognD.(n+1)/2[正確答案選擇是]:B43.待排序文件基本有序時,下面哪種排序方法,效率最差?A.堆排序B.快速排序C.冒泡排序D.歸并排序[正確答案選擇是]:B44.f(n)=Ω(g(n)),則g(n)為f(n)的（）A.上界B.下界C.同階D.低階[正確答案選擇是]:B45.下面關(guān)于貪心算法錯誤的是（）A.貪心算法總能找到可行解,并且是最優(yōu)解。B.問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心或動態(tài)規(guī)劃算法求解的關(guān)鍵特征。C.貪心算法一般預處理后再進行最優(yōu)化選擇。D.貪心選擇中每一步的局部最優(yōu)解都構(gòu)成全局最優(yōu)解的一部分[正確答案選擇是]:A46.原問題的最優(yōu)解包含其子問題的最優(yōu)解,這是（）性質(zhì)A.貪心選擇B.無后效性C.最優(yōu)子結(jié)構(gòu)D.重疊子問題[正確答案選擇是]:B47.下面有關(guān)遞歸與循環(huán)的說法錯誤的是（）A.遞歸是比循環(huán)更靈活的重復操作的機制。B.遞歸是一種比循環(huán)更強、更好用的實現(xiàn)“重復操作”的機制。C.當問題需要“后進先出”的操作時,用遞歸算法更有效。D.遞歸方法相比循環(huán)方法大大地減少了算法的計算量。[正確答案選擇是]:D48.（）是貪心算法與動態(tài)規(guī)劃算法的共同點A.重疊子問題B.構(gòu)造最優(yōu)解C.貪心選擇性質(zhì)D.最優(yōu)子結(jié)構(gòu)性質(zhì)[正確答案選擇是]:D49.備忘錄與動態(tài)規(guī)劃算法的不同點是（）A.遞推關(guān)系B.自頂向下計算C.子問題重疊D.最優(yōu)子結(jié)構(gòu)[正確答案選擇是]:B50.下面不是影響回溯算法效率的主要因素的是（）A.滿足約束函數(shù)的x[k]值的個數(shù)B.x[k]的搜索順序C.優(yōu)先級D.上界函數(shù)約束的所有x[k]的個數(shù)[正確答案選擇是]:C二、填空題1.算法的每一條指令必須要有確切的含義,必須是清楚的、無二義的。[正確答案選擇是]:T2.如果一個算法能應(yīng)用于問題的任意實例,并保證得到正確解答,稱這個算法解答了該問題。[正確答案選擇是]:T3.證明算法不正確,需要證明對任意實例算法都不能正確處理。[正確答案選擇是]:F4.時間復雜度是指算法最好情況下的運行時間。[正確答案選擇是]:F5.f(n)=O(g(n))則2^f(n)=O(2^g(n))[正確答案選擇是]:T6.增量構(gòu)造法生成子集,便于實現(xiàn)集合的操作。[正確答案選擇是]:F7.如果圖G中每條邊的權(quán)重都是互不相同的,圖G可能存在多顆最小生成樹。[正確答案選擇是]:F8.貪心選擇的性質(zhì)是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。[正確答案選擇是]:T9.每個迭代算法原則上總可以轉(zhuǎn)換成與它等價的遞歸算法;反之不然。[正確答案選擇是]:T10.分治法將原問題分解為若干個規(guī)模較小,相互獨立,與原問題相似的子問題。[正確答案選擇是]:T11.SPFA算法是Bellman-Ford算法的一種隊列實現(xiàn),適用于稀疏圖。[正確答案選擇是]:T12.DAG動態(tài)規(guī)劃算法中正推的開始點是無入邊的頂點[正確答案選擇是]:T13.回溯算法中在一個擴展結(jié)點變成死結(jié)點之前,它一直是擴展結(jié)點。[正確答案選擇是]:F14.回溯法用限界函數(shù)剪去得不到最優(yōu)解的子樹[正確答案選擇是]:T15.優(yōu)先隊列式分支限界法以最小耗費的方式產(chǎn)生狀態(tài)空間樹的結(jié)點。[正確答案選擇是]:T16.給定網(wǎng)絡(luò)N=(V,E)的一個流f,任意一個節(jié)點滿足流出量等于流入量。[正確答案選擇是]:F17.給定二分圖G=<V,E>中無孤立點,|V|=n,其最大流算法求得最大流f,則G的最大獨立數(shù)=n-f[正確答案選擇是]:T18.拉斯維加斯算法肯定得到正確解或找不到解,一旦找到一個解,一定是正確解[正確答案選擇是]:T19.如果Y∈NP，NP完全問題X￡pY，則Y是NP完全問題。[正確答案選擇是]:T20.程序必須在有窮時間終止。[正確答案選擇是]:F21.算法可以使用自然語言描述,便于描述同一算法的多種含義。[正確答案選擇是]:F22.計算機每次求解只是針對一個實例求解,問題的描述針該問題的所有實例。[正確答案選擇是]:T23.f=o(g)當且僅當g=ω(f)[正確答案選擇是]:T24.如果一個NP完全問題能在多項式時間內(nèi)得到解決,那么P=NP。[正確答案選擇是]:T25.子集生成算法中一般需要對集合元素進行定序。[正確答案選擇是]:T26.如果e是圖G中權(quán)重最小的邊,它肯定是G的一顆最小生成樹的邊。[正確答案選擇是]:T27.貪心算法總能找到最優(yōu)解[正確答案選擇是]:F28.遞歸方程是遞歸函數(shù)的要素之一。[正確答案選擇是]:T29.Bellman算法計算時,如果對于所有的v有OPT(n,v)=OPT(n-1,v),那么沒有負環(huán)。[正確答案選擇是]:T30.Floyd算法適用于多源最短路徑,使用權(quán)矩陣代替鄰接矩陣。[正確答案選擇是]:T31.DAG動態(tài)規(guī)劃算法中反推的開始點是無出邊的頂點。[正確答案選擇是]:T32.回溯法搜索解空間時,在其它條件相當?shù)那疤嵯?讓可取值最少的x[i]優(yōu)先,可以減少計算。[正確答案選擇是]:T33.回溯法在任何時刻,算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。[正確答案選擇是]:T34.隊列式分支限界以最大效益優(yōu)先方式產(chǎn)生狀態(tài)空間樹的結(jié)點。[正確答案選擇是]:F35.使用限界函數(shù)作優(yōu)先級,第一個加入隊列的葉子就是最優(yōu)解[正確答案選擇是]:T36.如果存在割(A,B)使流值v(f)=割的容量cap(A,B),f為最大流。[正確答案選擇是]:T37.圖G是二分圖當且僅當G中無奇數(shù)長的環(huán).[正確答案選擇是]:T38.蒙特卡羅算法的結(jié)果未必正確,并且可能難以有效判定是否正確。[正確答案選擇是]:T39.算法是一步步正確解決問題的方法和策略。[正確答案選擇是]:T40.同一問題可能有幾種不同的算法,解題思路和解題速度也會顯著不同。[正確答案選擇是]:T41.好算法具有如下特性:當輸入規(guī)模加倍時,算法降低C倍,C為常數(shù)。[正確答案選擇是]:T42.O(f)+O(g)=O(f+g),因此并行語句時間復雜度是兩者的復雜度之和。[正確答案選擇是]:T43.f=ω(g)且g=ω(h)則f=ω(h)[正確答案選擇是]:T44.減少枚舉變量的值域可以減少枚舉算法的時間復雜度。[