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

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