2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-算法設(shè)計(jì)與分析筆試考試歷年高頻考點(diǎn)試題摘選含答案第1卷一.參考題庫(kù)(共75題)1.數(shù)據(jù)結(jié)構(gòu)與算法里，可以用什么語(yǔ)句完成迭代算法（）A、for語(yǔ)句B、while語(yǔ)句C、do-while語(yǔ)句D、switch語(yǔ)句2.可以用兩個(gè)下標(biāo)定義的數(shù)組，稱(chēng)為二維數(shù)組。3.數(shù)據(jù)結(jié)構(gòu)與算法里，屬于不穩(wěn)定排序的是（）。A、快速排序B、冒泡排序C、直接插入排序D、希爾排序4.數(shù)據(jù)結(jié)構(gòu)與算法里，斐波那契數(shù)列的第5項(xiàng)的值是（）。A、1B、2C、5D、85.冒泡排序核心思想是（）。A、比較不相鄰記錄，如果逆序則交換B、比較相鄰記錄，如果逆序則交換正C、隨機(jī)比較兩個(gè)記錄，如果逆序則交換D、都不對(duì)6.數(shù)據(jù)結(jié)構(gòu)與算法中，裝填因子是哈希表的一個(gè)重要參數(shù)，它反映哈希表的裝滿(mǎn)程度。7.數(shù)據(jù)結(jié)構(gòu)與算法里，直接插入排序是穩(wěn)定排序，且時(shí)間復(fù)雜度是O（n*n）。8.考慮背包問(wèn)題：n=6，物品重量W=（1，5，2，3，6，1），價(jià)值P=（15，59，21，30，60，5），背包載重量C＝10。能放進(jìn)背包的物品價(jià)值最大為（）。A、101B、110C、115D、1209.大整數(shù)乘積算法是用（）來(lái)設(shè)計(jì)的。10.0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）11.數(shù)據(jù)結(jié)構(gòu)與算法里，不是插入排序的有（）。A、直接插入排序B、希爾排序C、冒泡排序D、快速排序12.概率算法大致分為哪幾類(lèi)？13.簡(jiǎn)單選擇排序算法中，每一趟選擇最小的記錄的過(guò)程，則每一趟排序的時(shí)間復(fù)雜度是（）A、O（n）B、O（n*n）C、O（1）D、O（n*log2n）14.數(shù)據(jù)結(jié)構(gòu)與算法里，參數(shù)是兩個(gè)的字符串處理函數(shù)有那些？（）。A、strlenB、strcpyC、strcatD、strcmp15.漸進(jìn)算法分析是指（）A、算法在最佳情況、最差情況和平均情況下的代價(jià)B、當(dāng)規(guī)模逐步往極限方向增大時(shí)，對(duì)算法資源開(kāi)銷(xiāo)“增長(zhǎng)率”上的簡(jiǎn)化分析C、數(shù)據(jù)結(jié)構(gòu)所占用的空間D、在最小輸入規(guī)模下算法的資源代價(jià)16.數(shù)據(jù)結(jié)構(gòu)與算法里，以下算法時(shí)間復(fù)雜度是O（n*n）的是（）。A、冒泡排序B、直接插入排序C、折半查找D、希爾排序17.數(shù)據(jù)結(jié)構(gòu)與算法里，O（n）是以下哪種算法的復(fù)雜度（）。A、順序查找B、順序表刪除元素C、順序表插入元素D、單鏈表查找第i個(gè)元素18.strlen計(jì)算字符串長(zhǎng)度時(shí)候不計(jì)算’/0’在內(nèi)。19.有以下程序，執(zhí)行后輸出結(jié)果應(yīng)為：（） A、456B、258C、369D、78920.先序遍歷一顆二叉排序樹(shù)的順序是（）。A、左子樹(shù)根結(jié)點(diǎn)右子樹(shù)B、根結(jié)點(diǎn)左子樹(shù)右子樹(shù)C、左子樹(shù)右子樹(shù)根結(jié)點(diǎn)D、都不對(duì)21.以下代碼的功能是：（） A、其他三項(xiàng)都不對(duì)B、求1--100的和C、求1--100的奇數(shù)和D、求1--100的偶數(shù)和22.數(shù)據(jù)結(jié)構(gòu)與算法里，折紙算法是一種（）方法解決的問(wèn)題。A、迭代B、窮舉C、遞推D、分治23.數(shù)據(jù)結(jié)構(gòu)與算法里，屬于穩(wěn)定排序的有（）。A、冒泡排序B、直接插入排序C、希爾排序D、改進(jìn)的冒泡排序24.已知while的基本語(yǔ)法如下：其中表達(dá)式是循環(huán)條件，語(yǔ)句為循環(huán)體。則表達(dá)式可以為（）A、關(guān)系表達(dá)式B、邏輯表達(dá)式C、算數(shù)表達(dá)式D、常量值25.已知定義數(shù)組inta[5]={1，2}；則執(zhí)行printf（"%d"，a[3]）；語(yǔ)句是（）A、1B、2C、3D、026.關(guān)于是否能查找到特定元素，下列選項(xiàng)中說(shuō)法正確的是（）。A、若查找表中存在特定元素稱(chēng)為查找失敗B、若查找表中存在特定元素稱(chēng)為查找成功C、若查找表中存在特定元素稱(chēng)為查找中D、若查找表中存在特定元素稱(chēng)為未找到27.蝸牛爬井問(wèn)題不屬于（）類(lèi)型算法解決的問(wèn)題。A、迭代問(wèn)題B、遞歸問(wèn)題C、分治問(wèn)題D、窮舉問(wèn)題28.兩個(gè)整數(shù)的最小公倍數(shù)的求解一般以先求出它們的最大公約數(shù)，計(jì)算方法是兩數(shù)相乘除以最大公約數(shù)。29.青蛙過(guò)河問(wèn)題，若沒(méi)有石柱只有荷葉，那么可過(guò)的青蛙數(shù)量應(yīng)比荷葉的數(shù)量多一個(gè)。30.已知序列X={x1，x2，…，xm}，序列Y={y1，y2，…，yn}，使用動(dòng)態(tài)規(guī)劃算法求解序列X和Y的最長(zhǎng)公共子序列，其最壞時(shí)間復(fù)雜度為（）。A、O（m*n）B、O（m+n）C、O（m*2n）D、O（n*2m）31.有一維數(shù)組定義：inta[5]={5，3，8，1，6}，請(qǐng)問(wèn)想引用8這個(gè)元素，以下那個(gè)引用是正確的（）A、a[3]B、a[2]C、a[0]D、a[1]32.數(shù)據(jù)結(jié)構(gòu)與算法里，快速排序是（）的一種。A、插入排序B、選擇排序C、交換排序D、歸并排序33.希爾排序是一種不穩(wěn)定排序，那么原因是（）。A、存在不相鄰記錄的交換B、存在相鄰記錄的交換C、存在相同關(guān)鍵字的記錄D、存在著記錄順序的一次調(diào)換34.數(shù)據(jù)結(jié)構(gòu)與算法里，30個(gè)記錄進(jìn)行冒泡排序，使用未改進(jìn)的冒泡排序，則需要（）趟排序才能完成排序。A、29B、30C、28D、2735.下面程序執(zhí)行后的結(jié)果是（） A、28B、34C、40D、1036.程序是（）用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。37.最大效益優(yōu)先是（）的一搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法38.數(shù)據(jù)結(jié)構(gòu)與算法里，程序的輸出結(jié)果不可能是（） A、2B、3C、1D、639.數(shù)據(jù)結(jié)構(gòu)與算法里，以下屬于哈希函數(shù)的構(gòu)造方法的是（）。A、直接定址法B、哈希再散列法C、線(xiàn)性探測(cè)再散列法D、二次探測(cè)再散列法40.備忘錄方法是那種算法的變形。（）A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法41.以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為（）。42.希爾排序是一種選擇排序，也不穩(wěn)定排序，時(shí)間復(fù)雜度是O（n3/2）。43.簡(jiǎn)述分治法與動(dòng)態(tài)規(guī)劃法的異同。44.有n個(gè)獨(dú)立的作業(yè){1，2，..，n}，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的處理時(shí)間為ti。現(xiàn)約定，任何作業(yè)可以在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的作業(yè)。多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成（n>m）。對(duì)于多級(jí)調(diào)度問(wèn)題，使用以下哪種貪心策略比較合適（）A、作業(yè)從小到大依次分配給空閑的機(jī)器B、作業(yè)從大到小依次分配給空閑的機(jī)器C、每個(gè)機(jī)器分配一樣的作業(yè)數(shù)D、使用以上幾種貪心策略都能找到最優(yōu)解，所以都合適45.遞歸是函數(shù)自身嗲用自身，根據(jù)調(diào)用的方式分為直接遞歸和間接遞歸。46.數(shù)據(jù)結(jié)構(gòu)與算法里，求兩個(gè)數(shù)的最大公約數(shù)，依照方式不同其時(shí)間復(fù)雜度可能是（）A、O（n）B、O（log2n）C、O（n*n）D、O（1）47.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，改進(jìn)的冒泡排序的任一趟排序過(guò)程中，如果沒(méi)有發(fā)生（），則說(shuō)明已經(jīng)有序；排序完畢。A、數(shù)據(jù)交換B、數(shù)據(jù)刪除C、數(shù)據(jù)增加D、都不對(duì)48.數(shù)據(jù)結(jié)構(gòu)與算法里，若查找表中不存在特定元素，稱(chēng)（）。A、查找失敗B、查找成功C、不確定D、都不對(duì)49.設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。 （1）請(qǐng)給出一個(gè)解決方法，并分析其復(fù)雜性。 （2）把n個(gè)元素等分為兩組A1和A2，分別求這兩組的最大值和最小值，然后分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素至多兩個(gè)元素為止。這是什么方法的思想？請(qǐng)給出該方法的算法描述，并分析其復(fù)雜性。50.數(shù)據(jù)結(jié)構(gòu)中，下列選項(xiàng)中符合折半查找的前提的是（）。A、順序存儲(chǔ)B、記錄有序C、記錄無(wú)序D、鏈?zhǔn)酱鎯?chǔ)51.while是實(shí)現(xiàn)循環(huán)結(jié)構(gòu)，do..while是實(shí)現(xiàn)選擇結(jié)構(gòu)。52.數(shù)據(jù)結(jié)構(gòu)與算法里，查找沒(méi)有查找失敗的可能性。53.數(shù)據(jù)結(jié)構(gòu)與算法里，程序調(diào)用自身的編程技巧就是數(shù)組54.數(shù)據(jù)結(jié)構(gòu)與算法中，在排序中，對(duì)于關(guān)鍵字相等的記錄，排序前后相對(duì)位置不變。這時(shí)稱(chēng)排序?yàn)椋ǎ、穩(wěn)定排序B、不穩(wěn)定排序C、不確定是穩(wěn)定排序還是不穩(wěn)定排序D、基數(shù)排序55.哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）56.數(shù)據(jù)結(jié)構(gòu)與算法里，break語(yǔ)句是調(diào)整語(yǔ)句可英語(yǔ)與下面那些語(yǔ)句中。（）A、while語(yǔ)句B、if語(yǔ)句C、if-else語(yǔ)句D、if-else-if語(yǔ)句57.數(shù)據(jù)結(jié)構(gòu)與算法中，負(fù)載因子（裝填因子）是哈希表的一個(gè)重要參數(shù)，它反映哈希表的裝滿(mǎn)程度，該值越大則發(fā)生沖突可能性越大。58.衡量算法時(shí)間效率的方法有哪兩種？請(qǐng)敘述。59.設(shè)有n個(gè)活動(dòng)的集合s={1，2，…，n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。si，fi分別為活動(dòng)i的開(kāi)始時(shí)間和結(jié)束時(shí)間，活動(dòng)i和j相容當(dāng)且僅當(dāng)si>=fj或者sj>=fi。應(yīng)怎樣對(duì)這n個(gè)活動(dòng)進(jìn)行安排才能令最多的活動(dòng)可以使用資源？（）。A、最早結(jié)束的活動(dòng)優(yōu)先安排B、最先開(kāi)始的活動(dòng)優(yōu)先安排C、占用資源時(shí)間最少的活動(dòng)優(yōu)先安排D、占用資源時(shí)間最長(zhǎng)的活動(dòng)優(yōu)先安排60.冒泡排序是不穩(wěn)定的排序。61.在一個(gè)4×4的方格的棋盤(pán)上，將數(shù)字1到15代表的15個(gè)棋子以任意的順序置入各方格中，空出一格。要求通過(guò)有限次的移動(dòng)，把一個(gè)給定的初始狀態(tài)變成目標(biāo)狀態(tài)。移動(dòng)的規(guī)則是：每次只能把空格周?chē)乃母駭?shù)字（棋子）中的任意一個(gè)移入空格，從而形成一個(gè)新的狀態(tài)。為了有效的移動(dòng)，設(shè)計(jì)了估值函數(shù)C1（x），表示在結(jié)點(diǎn)x的狀態(tài)下，沒(méi)有到達(dá)目標(biāo)狀態(tài)下的正確位置的棋子的個(gè)數(shù)。 請(qǐng)使用該估計(jì)函數(shù)，對(duì)圖示的初始狀態(tài)，給出使用分支限界方法轉(zhuǎn)換到目標(biāo)狀態(tài)的搜索樹(shù)。 62.數(shù)據(jù)結(jié)構(gòu)與算法里，小明的煩惱問(wèn)題的算法使用下列哪些技術(shù)項(xiàng)（）。A、二維數(shù)組B、循環(huán)嵌套C、分支判斷D、遞歸63.for語(yǔ)句完全可以替代while語(yǔ)句。64.優(yōu)先隊(duì)列可用（）數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。65.數(shù)據(jù)結(jié)構(gòu)與算法里，查找的結(jié)果可能在集合中也可能不在集合中，分別稱(chēng)為（）。A、查找失敗B、查找成功C、不確定D、都不對(duì)66.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，就性能而言，希爾排序的時(shí)間復(fù)雜度是（）。A、O（n*n）B、O（nlog2n）C、O（n）D、O（n3/2）67.整數(shù)5和10的最大公約數(shù)是（）。A、10B、5C、30D、5068.數(shù)據(jù)結(jié)構(gòu)與算法里，for循環(huán)的小括號(hào)中的三個(gè)表達(dá)式分別是（）A、初值B、條件C、增量D、以上選項(xiàng)都不是69.數(shù)據(jù)結(jié)構(gòu)與算法里，冒泡排序與快速排序都是插入排序。70.一組長(zhǎng)度為11的整型關(guān)鍵字為{11，21，12，34，43，45，54，65，67，78，89}，通過(guò)哈希函數(shù)H（key）=keyMOD11映射到長(zhǎng)度為11的哈希表中，裝填因子為（）A、1B、2C、3D、471.已知Ak=（aij（k））ri*ri+1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序。（要求：給出計(jì)算步驟）72.冒泡排序的時(shí)間復(fù)雜度是O（n*n）。73.數(shù)據(jù)結(jié)構(gòu)與算法中，屬于插入排序的有（）。A、希爾排序B、直接插入排序C、冒泡排序D、簡(jiǎn)單選擇排序74.數(shù)據(jù)結(jié)構(gòu)與算法里，以下經(jīng)典著作中，哪本記載了最早的雞兔同籠問(wèn)題（）A、孫子算經(jīng)B、孫子兵法C、九章算術(shù)D、九章算經(jīng)75.當(dāng)上下限表達(dá)式相等時(shí)，我們使用下列哪種表示法來(lái)描述算法代價(jià)？（）A、大O表示法B、大Ω表示法C、Θ表示法D、小o表示法第2卷一.參考題庫(kù)(共75題)1.關(guān)于循環(huán)結(jié)構(gòu)使用描述正確的是（）A、用do-while語(yǔ)句構(gòu)成的循環(huán)，在while后的表達(dá)式為零時(shí)結(jié)束循環(huán)B、for結(jié)構(gòu)與while結(jié)構(gòu)都是先執(zhí)行后判斷，do..while是先判斷后執(zhí)行C、for循環(huán)可以嵌套for循環(huán)D、for（表達(dá)式1；表達(dá)式2；表達(dá)式3）語(yǔ)法格式中表達(dá)式1表示的是循環(huán)初始值2.對(duì)于下列二分搜索算法，正確的是（）A、B、C、D、3.二叉排序樹(shù)的（）上結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值。A、左子樹(shù)B、右子樹(shù)C、左子樹(shù)和右子樹(shù)D、都不對(duì)4.chars1[100]="ABC"，s2[100]="abc"；則strcmp（s1，s2）的結(jié)果是（）。A、是0B、是1C、是-1D、不確定5.請(qǐng)畫(huà)出用回溯法解4皇后問(wèn)題的解空間樹(shù)和搜索空間樹(shù)。6.冒泡排序若在一趟排序中沒(méi)有記錄交換則停止。這樣能加快排序的速度。7.數(shù)據(jù)結(jié)構(gòu)與算法里，while循環(huán)屬于當(dāng)型循環(huán)，其循環(huán)變量的初值寫(xiě)在（）A、while語(yǔ)句{}中的第一句B、while語(yǔ)句{}中的最后一句C、while語(yǔ)句的上面D、while語(yǔ)句的下面8.素?cái)?shù)是只能被1和它本身整除的整數(shù)，那么下面不是素?cái)?shù)的是（）。A、13B、15C、27D、349.分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)0-1背包問(wèn)題。要求：說(shuō)明所使用的算法策略；寫(xiě)出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。10.回文字符串是正反都一樣的英文字符串，那么下面不是回文字符串的應(yīng)為（）。A、XYZZB、XYZXYZC、XXMXXD、MMNMMN11.數(shù)據(jù)結(jié)構(gòu)與算法里，下列數(shù)字不是完數(shù)的是（）A、7B、6C、28D、9912.蒙特卡羅算法是（）的一種。A、分支界限算法B、概率算法C、貪心算法D、回溯算法13.簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度與快速排序的不一樣。14.以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為（）A、分支界限算法B、概率算法C、貪心算法D、回溯算法15.數(shù)據(jù)結(jié)構(gòu)與算法里，返回值是char*的字符串處理函數(shù)有（）。A、strlenB、strcpyC、strcatD、strcmp16.數(shù)據(jù)結(jié)構(gòu)與算法里，荷蘭國(guó)旗算法的基本寫(xiě)法循環(huán)中套分支結(jié)構(gòu)。17.求下列函數(shù)的漸近表達(dá)式： n2+10n-1；14+5/n+1/n2；18.數(shù)據(jù)結(jié)構(gòu)與算法里，迭代算法的時(shí)間復(fù)雜度不可能是O（n）。19.數(shù)據(jù)結(jié)構(gòu)與算法里，循環(huán)語(yǔ)句中加break的作用的是（）A、break用于循環(huán)語(yǔ)句的作用是結(jié)束本層循環(huán)B、break用于循環(huán)語(yǔ)句的作用是結(jié)束本次循環(huán)，繼續(xù)下一下循環(huán)C、break不能用于switch語(yǔ)句D、break語(yǔ)句不能用do-while語(yǔ)句開(kāi)會(huì)20.簡(jiǎn)述分支限界法及其算法思想。21.秦始皇吞并六國(guó)使用的遠(yuǎn)交近攻，逐個(gè)擊破的連橫策略采用了以下哪種算法思想？（）A、遞歸；B、分治；C、迭代；D、模擬。22.數(shù)據(jù)結(jié)構(gòu)與算法里，順序表的查找有順序查找和（）。A、折半查找B、線(xiàn)性查找C、隨機(jī)查找D、索引查找23.數(shù)據(jù)結(jié)構(gòu)與算法里，折半查找的時(shí)間復(fù)雜度是（）。A、O（1）B、O（log2n）C、O（n*n）D、O（n）24.簡(jiǎn)單選擇排序每趟排序可能出現(xiàn)多次記錄交換。25.簡(jiǎn)述分支限界法與回溯法的異同。26.數(shù)據(jù)結(jié)構(gòu)中，二叉排序樹(shù)的右子樹(shù)也應(yīng)該一定是棵二叉排序樹(shù)。27.回文字符串的非遞歸算法：用系統(tǒng)函數(shù)解決的方式，需要用到哪些系統(tǒng)函數(shù)（）。A、strcpyB、strcatC、strcmpD、strrev28.數(shù)據(jù)結(jié)構(gòu)與算法里，指針做參數(shù)時(shí)，屬于（）。A、值傳遞B、地址傳遞C、函數(shù)傳遞D、遞歸調(diào)用29.8和12的公約數(shù)有哪些（）A、4B、2C、3D、130.6是完數(shù)，其因子包括（）A、1B、2C、3D、631.有以下程序，程序運(yùn)行后的輸出結(jié)果應(yīng)為：（） A、11B、19C、13D、2032.數(shù)據(jù)結(jié)構(gòu)與算法里，順序表的查找分為：順序查找和折半查找。33.計(jì)算一個(gè)算法時(shí)間復(fù)雜度通常可以計(jì)算（）、（）或計(jì)算步驟。34.下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（）A、數(shù)值概率算法B、舍伍德算法C、拉斯維加斯算法D、蒙特卡羅算法35.希爾排序是一種插入排序，也不穩(wěn)定排序，時(shí)間復(fù)雜度是O（n3/2）。36.修改圖的m-著色的回溯算法，找到一個(gè)解，算法就結(jié)束。37.定義二維數(shù)組intarr[4][2]如果全部元素輸出，共需要輸出6個(gè)元素38.建立計(jì)算模型的目的是為了使（）。39.在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是（）A、回溯法B、分支限界法C、回溯法和分支限界法D、回溯法求解子集樹(shù)問(wèn)題40.在0-1背包問(wèn)題中，若各物品依重量遞增序排列時(shí)，其價(jià)值恰好依遞減序排列，對(duì)這個(gè)特殊的0-1背包問(wèn)題，設(shè)計(jì)一個(gè)有效的算法找出最優(yōu)解。（描述你的算法即可，無(wú)需證明算法的正確性）41.ACM算法的素?cái)?shù)和計(jì)算中，sum變量用于累加素?cái)?shù)之和，那么它的初值應(yīng)賦值為（）A、0B、1C、100D、不賦初值42.下列哪一種算法不是隨機(jī)化算法（）A、蒙特卡羅算法B、拉斯維加斯算法C、動(dòng)態(tài)規(guī)劃算法D、舍伍德算法43.廣度優(yōu)先是（）的一搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法44.請(qǐng)解釋什么是P問(wèn)題，NP問(wèn)題。45.對(duì)于符號(hào)三角問(wèn)題，符號(hào)三角形的第一行有n個(gè)符號(hào)。符號(hào)可以為“＋”或“－”，以下每一行的符號(hào)由上行得到，2個(gè)同號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“－”。如下圖所示（第一行有4個(gè)符號(hào)的符號(hào)三角中的其中的一個(gè)）： 請(qǐng)畫(huà)出使用回溯法求解第一行有4個(gè)符號(hào)（即n＝4）時(shí)，解空間樹(shù)的形狀。46.給定一序列試a1，a2，…，an，利用合并排序?qū)π蛄邪瓷蜻M(jìn)行排序，編程實(shí)現(xiàn)。47.數(shù)據(jù)結(jié)構(gòu)與算法里，冒泡排序和（）都屬于交換排序。A、快速排序B、直接插入排序C、簡(jiǎn)單選擇排序D、希爾排序48.關(guān)于回溯搜索法的介紹，下面（）是不正確描述。A、回溯法有“通用解題法”之稱(chēng)，它可以系統(tǒng)地搜索一個(gè)問(wèn)題的所有解或任意解B、回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法C、回溯算法在生成解空間的任一結(jié)點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否可能包含問(wèn)題的解，如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向祖先結(jié)點(diǎn)回溯D、回溯算法需要借助隊(duì)列這種結(jié)構(gòu)來(lái)保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑49.數(shù)據(jù)結(jié)構(gòu)與算法里，從時(shí)間復(fù)雜度的角度來(lái)看，快速排序的時(shí)間復(fù)雜度是（）。A、O（n*n）B、O（nlog2n）C、O（1）D、都不對(duì)50.下面程序是用來(lái)描述用while實(shí)現(xiàn)求100以?xún)?nèi)的偶數(shù)和。下面步聚順序應(yīng)為（） （1）定義循環(huán)變量i及累積求和變量sum，初始化變量的值 （2）套用while循環(huán)結(jié)構(gòu)實(shí)現(xiàn)求100以?xún)?nèi)偶數(shù)和 （3）分析循環(huán)四要素 初始值=2終值=100步長(zhǎng)：+1循環(huán)體：判斷是否是偶數(shù)，加法 （4）輸出1-100之間偶數(shù)和的結(jié)果A、1-2-3-4B、1-3-2-4C、1-4-2-3D、4-3-2-151.數(shù)據(jù)結(jié)構(gòu)中，二叉排序樹(shù)的第4層多有多少個(gè)結(jié)點(diǎn)（）。A、2B、4C、8D、152.數(shù)據(jù)結(jié)構(gòu)與算法里，小明的煩惱問(wèn)題的核心代碼利用（）實(shí)現(xiàn)的。A、遞歸算法B、循環(huán)嵌套C、單層循環(huán)D、只用了分支結(jié)構(gòu)53.小明的煩惱核心代碼是使用（）實(shí)現(xiàn)的。A、遞歸算法B、循環(huán)嵌套C、單層循環(huán)D、只用了分支結(jié)構(gòu)54.經(jīng)典算法之窮舉法的優(yōu)點(diǎn)（）A、算法簡(jiǎn)單B、邏輯清晰C、易于理解D、程序易于實(shí)現(xiàn)55.有0-1背包問(wèn)題如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n為物品個(gè)數(shù)，c為背包載重量，P表示物品的價(jià)值，W表示物品的重量。請(qǐng)問(wèn)對(duì)于此0-1背包問(wèn)題，應(yīng)如何選擇放進(jìn)去的物品，才能使到放進(jìn)背包的物品總價(jià)值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），單位重量物品價(jià)值（7.5，2.67，1.5，0.8，0.375，0.1）56.簡(jiǎn)述用計(jì)算機(jī)求解問(wèn)題的步驟。57.關(guān)于裝填因子，以下說(shuō)法正確的是（）。A、哈希表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。B、若散列表的負(fù)載因子（裝填因子）α58.分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（）。A、最小堆B、最大堆C、棧D、數(shù)組59.雞兔同籠的算法是采用經(jīng)典算法之窮舉法解決的60.Hanoi塔問(wèn)題如下圖所示。現(xiàn)要求將塔座A上的的所有圓盤(pán)移到塔座B上，并仍按同樣順序疊置。移動(dòng)圓盤(pán)時(shí)遵守Hanoi塔問(wèn)題的移動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法正確的為：（） A、B、C、D、61.窮舉法缺點(diǎn)是：運(yùn)算量較大只適合于“有幾種組合”“是否存在”求解不定方程等類(lèi)型的問(wèn)題求解62.數(shù)據(jù)結(jié)構(gòu)與算法里，籠子里有若干只雞和兔。從上面數(shù)，有8個(gè)頭，從下面數(shù)，有26只腳，雞和兔各有幾只？（）A、兔有5只，雞有3只。B、兔有3只，雞有5只。C、兔有4只，雞有4只。D、兔有2只，雞有6只。63.數(shù)據(jù)結(jié)構(gòu)中，折半查找需要記錄是鏈?zhǔn)酱鎯?chǔ)并且有序。64.通過(guò)鍵盤(pán)輸入一個(gè)高精度的正整數(shù)n（n的有效位數(shù)≤240），去掉其中任意s個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。 65.數(shù)據(jù)結(jié)構(gòu)與算法里，排序是（）A、排將一批無(wú)序的記錄（數(shù)據(jù)）重新排列成按關(guān)鍵字有序的記錄序列的過(guò)程B、將正序的記錄（數(shù)據(jù)）排成倒序的即記錄C、將倒序的記錄（數(shù)據(jù)）排成正序的即記錄D、以上都不對(duì)66.數(shù)據(jù)結(jié)構(gòu)與算法里，一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件（）時(shí)，遞歸前進(jìn)。A、滿(mǎn)足B、不滿(mǎn)足C、超出D、以上三項(xiàng)都不對(duì)67.下列算法中通常以自底向上的方式求解最優(yōu)解的是（）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法68.回溯算法和分支限界法的問(wèn)題的解空間樹(shù)不會(huì)是（）A、有序樹(shù)B、子集樹(shù)C、排列樹(shù)D、無(wú)序樹(shù)69.小明的煩惱問(wèn)題，電話(huà)號(hào)存儲(chǔ)的字符是使用（）存儲(chǔ)的。A、一維數(shù)組B、二維數(shù)組C、指針變量D、整型變量70.與順序查找算法相比，折半查找算法的時(shí)間復(fù)雜性有多大程度的降低？它是如何提高算法的效率的？71.數(shù)據(jù)結(jié)構(gòu)與算法中，簡(jiǎn)單選擇排序存在不相鄰的元素之間的交換，所有它是（）。A、不穩(wěn)定排序B、穩(wěn)定排序C、不確定D、都不對(duì)72.子程序的遞歸邊界應(yīng)是i等于多少的時(shí)候。（） A、是0B、是1C、是2D、是373.數(shù)據(jù)結(jié)構(gòu)與算法里，比孫子算經(jīng)中的雙層循環(huán)解決的雞兔同籠問(wèn)題的時(shí)間復(fù)雜度高的是（）A、O（n*n*n）B、O（2^n）^表示冪C、O（n!）D、O（n^n）^表示冪74.一個(gè)直接或間接調(diào)用自身的算法稱(chēng)為（）算法。 出自于“平衡子問(wèn)題”的思想，通常分治法在分割原問(wèn)題，形成若干子問(wèn)題時(shí)，這些子問(wèn)題的規(guī)模都大致（）。75.數(shù)據(jù)結(jié)構(gòu)與算法里，以下關(guān)于負(fù)載因子說(shuō)法正確的是（）A、哈希表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。B、負(fù)載因子（裝填因子）是散列表的一個(gè)重要參數(shù)，它反映散列表的裝滿(mǎn)程度。C、散列法的平均檢索長(zhǎng)度不隨表中結(jié)點(diǎn)數(shù)目的增加而增加，而是隨負(fù)載因子的增大而增大。D、若散列表的負(fù)載因子（裝填因子）α第1卷參考答案一.參考題庫(kù)1.參考答案：A,B,C2.參考答案：正確3.參考答案：A,D4.參考答案：C5.參考答案：B6.參考答案：正確7.參考答案：正確8.參考答案：B9.參考答案：分治法10.參考答案：A11.參考答案：C,D12.參考答案：數(shù)值概率算法，蒙特卡羅（MonteCarlo）算法，拉斯維加斯（LasVegas）算法和舍伍德（Sherwood）算法。13.參考答案：A14.參考答案：B,C,D15.參考答案：B16.參考答案：A,B17.參考答案：A,B,C,D18.參考答案：正確19.參考答案：C20.參考答案：B21.參考答案：D22.參考答案：A23.參考答案：A,B,D24.參考答案：A,B,C,D25.參考答案：D26.參考答案：B27.參考答案：B,C,D28.參考答案：正確29.參考答案：正確30.參考答案：A31.參考答案：B32.參考答案：C33.參考答案：A34.參考答案：A35.參考答案：B36.參考答案：算法37.參考答案：A38.參考答案：B,C,D39.參考答案：A40.參考答案：B41.參考答案：回溯法42.參考答案：錯(cuò)誤43.參考答案： 分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是： 將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。 兩者的不同點(diǎn)是： 適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。而用分治法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往是互相獨(dú)立的。44.參考答案：B45.參考答案：正確46.參考答案：A,B47.參考答案：A48.參考答案：A49.參考答案：（1）基本思想：從頭到尾逐個(gè)掃描，紀(jì)錄最大和最小元素。 輸入：具有n個(gè)元素的數(shù)組 輸出：最大值和最小值 步驟： 50.參考答案：A,B51.參考答案：錯(cuò)誤52.參考答案：錯(cuò)誤53.參考答案：錯(cuò)誤54.參考答案：A55.參考答案：B56.參考答案：A57.參考答案：正確58.參考答案： 有事前分析法和事后分析法兩種。 事后分析法：先將算法用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)，然后度量程序的運(yùn)行時(shí)間。 事前分析法：算法的時(shí)間效率是問(wèn)題規(guī)模的函數(shù)，假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和函數(shù)f（n）的增長(zhǎng)率相同，則可記作： T（n）=O（f（n）） 稱(chēng)T（n）為算法的漸進(jìn)時(shí)間復(fù)雜度。簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。59.參考答案：C60.參考答案：錯(cuò)誤61.參考答案：62.參考答案：A,B,C63.參考答案：正確64.參考答案：堆65.參考答案：A,B66.參考答案：D67.參考答案：B68.參考答案：A,B,C69.參考答案：錯(cuò)誤70.參考答案：A71.參考答案：求解矩陣為： 因此，最佳乘積序列為（A1A2）（（A3A4）（A5×A6）），共執(zhí)行乘法2010次。72.參考答案：正確73.參考答案：A,B74.參考答案：A75.參考答案：C第2卷參考答案一.參考題庫(kù)1.參考答案：A,C,D2.參考答案：D3.參考答案：A4.參考答案：C5.參考答案： 解空間樹(shù)： 用回溯法的搜索空間樹(shù)： 6.參考答案：正確7.參考答案：C8.參考答案：B,C,D9.參考答案：（1）貪心算法O（nlog（n）） 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿(mǎn)為止。 具體算法可描述如下： （2）動(dòng)態(tài)規(guī)劃法O（nc） M（i，j）是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m（i，j）的遞歸式如下。 （3）回溯法O（2n） 10.參考答案：A,B,D11.參考答案：A,D12.參考答案：B13.參考答案：正確14.參考答案：D15.參考答案：B,C16.參考答案：正確17.參考答案： ①因?yàn)椋海挥蓾u近表達(dá)式的定義易知： n2是n2+10n-1的漸近表達(dá)式。 ②因?yàn)椋海?由漸近表達(dá)式的定義易知：14是14+5/n+1/n2的漸近表達(dá)式。18.參考答案：錯(cuò)誤19.參考答案：A20.參考答案： 這是一種用于求解組合優(yōu)化問(wèn)題的排除非解的搜索算法。類(lèi)似于回溯法，分枝定界法在搜索解空間時(shí)，也經(jīng)常使用樹(shù)形結(jié)構(gòu)來(lái)組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹(shù)結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來(lái)搜索這些樹(shù)。因此，可以很容易比較回溯法與分枝定界法的異同。相對(duì)而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。 算法思想：分枝限界（branchandbound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過(guò)程才結(jié)束。 有兩種常用的方法可用來(lái)選擇下一個(gè)E-節(jié)點(diǎn)（雖然也可能存在其他的方法）： 1）先進(jìn)先出（FIFO）即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活 節(jié)點(diǎn)表的性質(zhì)與隊(duì)列