算法設(shè)計與分析-模擬題答案 2022年秋 中國地質(zhì)大學(xué)

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