2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-算法設(shè)計(jì)與分析筆試歷年真題薈萃含答案（圖片大小可自由調(diào)整）第1卷一.參考題庫(kù)(共30題)1.下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（）A、數(shù)值概率算法B、舍伍德算法C、拉斯維加斯算法D、蒙特卡羅算法2.冒泡排序的時(shí)間復(fù)雜度（）。A、O（n）B、O（n*n）C、O（1）D、都不對(duì)3.數(shù)據(jù)結(jié)構(gòu)與算法中，從排序的大的分類(lèi)上講，屬于交換排序的是（）。A、簡(jiǎn)單選擇排序B、堆排序C、快速排序D、冒泡排序4.關(guān)于回溯算法和分支限界法，以下（）是不正確描述。A、回溯法中，每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)B、分支限界法中，活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)，在這些兒子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子加入活結(jié)點(diǎn)表中C、回溯法采用深度優(yōu)先的結(jié)點(diǎn)生成策略D、分支限界法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先（最大效益優(yōu)先）的結(jié)點(diǎn)生成策略5.下面關(guān)于break與continue描述正確的是。（）A、continue與break具有相同的效果B、continue在循環(huán)語(yǔ)句中具有中斷循環(huán)的作用C、continue語(yǔ)句可以在switch語(yǔ)句中使用D、continue與break都可以用于循環(huán)結(jié)構(gòu)中6.數(shù)據(jù)結(jié)構(gòu)與算法里，時(shí)間復(fù)雜度是O（n*n）的算法是（）。A、簡(jiǎn)單選擇排序B、順序查找C、折半查找D、快速排序7.數(shù)據(jù)結(jié)構(gòu)與算法里，算法的設(shè)計(jì)要求包括（）A、有窮性B、可讀性C、確定性D、可行性8.數(shù)據(jù)結(jié)構(gòu)與算法里，for循環(huán)和white循環(huán)的共同點(diǎn)是（）A、都是先執(zhí)行后判斷的循環(huán)B、都行先判斷后執(zhí)行的循環(huán)C、都屬于直到型循環(huán)D、都是分支結(jié)構(gòu)語(yǔ)句9.下圖是由14個(gè)“+”和14個(gè)“－”組成的符號(hào)三角形。2個(gè)同號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“－”。 在一般情況下，符號(hào)三角形的第一行有n個(gè)符號(hào)。符號(hào)三角形問(wèn)題要求對(duì)于給定的n，計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的“+”和“－”的個(gè)數(shù)相同。請(qǐng)針對(duì)符號(hào)三角形問(wèn)題設(shè)計(jì)一個(gè)盡可能高效的算法。10.請(qǐng)畫(huà)出用回溯法解n=3的0-1背包問(wèn)題的解空間樹(shù)和當(dāng)三個(gè)物品的重量為{20，15，10}，價(jià)值為{20，30，25}，背包容量為25時(shí)搜索空間樹(shù)。11.有以下程序，執(zhí)行后輸出的結(jié)果是（）。 A、58B、56C、45D、2412.算法是指解決問(wèn)題的（）或（）。13.簡(jiǎn)述分支限界法及其算法思想。14.以下關(guān)于數(shù)組的描述中，錯(cuò)誤的有：（）A、可以通過(guò)如下語(yǔ)句來(lái)完成對(duì)一個(gè)數(shù)組的輸入：inta[10]；scanf（"%d"，a）；B、可以通過(guò)如下語(yǔ)句來(lái)完成對(duì)一個(gè)數(shù)組的輸入：inta[10]；scanf（"%d"，&a）；C、若有inta[10]={6，7，8，9，10}；，則是將5個(gè)初值依次賦給a[0]至a[4]D、inta[9]；則數(shù)組a的下標(biāo)范圍是1-915.數(shù)據(jù)結(jié)構(gòu)與算法里，28是完數(shù)，除了1，2，4，14以外，因子還有（）A、21B、7C、6D、2816.冒泡排序的每一趟的過(guò)程是要比較（）元素，如果逆序進(jìn)行交換。A、相鄰B、不相鄰C、首尾D、都不對(duì)17.哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）18.排序和查找是經(jīng)常遇到的問(wèn)題。按照要求完成下題： （1）對(duì)數(shù)組A={15，29，135，18，32，1，27，25，5}，用快速排序方法將其排成遞減序； （2）請(qǐng)描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法； （3）給出上述算法的遞歸算法； （4）使用上述算法對(duì)（1）所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：18，31，135。19.數(shù)據(jù)結(jié)構(gòu)與算法里，折紙算法是一種（）方法解決的問(wèn)題。A、迭代B、窮舉C、遞推D、分治20.一根繩子有320米長(zhǎng)，每天截取12米，問(wèn)多少天后繩子長(zhǎng)度不足40米？其代碼編寫(xiě)如下：則填空處應(yīng)該填寫(xiě)的語(yǔ)句序列是（）A、len=len-12；B、len=len+12；C、len*=12；D、len-1221.數(shù)據(jù)結(jié)構(gòu)與算法里，冒泡排序是一種（），因?yàn)槊刻硕伎赡艽嬖谟涗浿g的互相交換。A、插入排序B、選擇排序C、交換排序D、歸并排序22.下面定義的一維數(shù)組并賦值正確的是（）。A、inta[2]={1，2，3}；B、inta[3]={1，2，3}；C、floata[3]={‘1’，’2’，’3’}；D、floata[3]={’1’，’a’，1.1}；23.若有說(shuō)明：inta[3][4]；，則對(duì)a數(shù)組元素的非法引用是：（）A、a[0][2*1]B、a[1][3]C、a[4-2][0]D、a[0][4]24.數(shù)據(jù)結(jié)構(gòu)與算法中，快速排序是（）的一種。A、插入排序B、選擇排序C、交換排序D、歸并排序25.設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H（k）=k%P，則P通常情況下最好選擇（）。A、99B、97C、91D、9326.判斷完數(shù)的算法，需要求因子之和，若累加器為sum，則sum應(yīng)該賦初值為（）A、sum=0；B、sum=i；C、sum=1；D、sum=sum；27.簡(jiǎn)述數(shù)值概率算法的作用。28.以下字符串中，是回文字符串的是（）。A、abcbaB、12321C、1221D、abcdef29.數(shù)據(jù)結(jié)構(gòu)與算法里，查找表是（）類(lèi)型的邏輯結(jié)構(gòu)。A、集合B、線性C、樹(shù)形D、圖形30.數(shù)據(jù)結(jié)構(gòu)與算法里，順序表的查找分為：順序查找和折半查找。第1卷參考答案一.參考題庫(kù)1.參考答案:C2.參考答案:B3.參考答案:C,D4.參考答案:A5.參考答案:D6.參考答案:A7.參考答案:B8.參考答案:B9.參考答案: 回溯法實(shí)現(xiàn) 對(duì)于符號(hào)三角形問(wèn)題，用n元組x[1：n]表示符號(hào)三角形的第一行的n個(gè)符號(hào)。當(dāng)x=1時(shí)，表示符號(hào)三角形的第一行的第i個(gè)符號(hào)為“+”號(hào)；當(dāng)x=0時(shí)，表示符號(hào)三角形的第一行的第i個(gè)符號(hào)為“-”號(hào)；1≤i≤n。由于x是二值的，所以在用回溯法解符號(hào)三角形問(wèn)題時(shí)，可以用一棵完全二叉樹(shù)來(lái)表示其解空間。在符號(hào)三角形的第一行的前i個(gè)符號(hào)x[1：i]確定后，就確定了一個(gè)由i*（i+1）/2個(gè)符號(hào)組成的符號(hào)三角形。下一步確定了x[i+1]的值后，只要在前面已確定的符號(hào)三角形的右邊加一條邊，就可以擴(kuò)展為x[1：i+1]所相應(yīng)的符號(hào)三角形。最終由x[1：n]所確定的符號(hào)三角形中包含的“+”號(hào)個(gè)數(shù)與“-”號(hào)個(gè)數(shù)同為n*（n+1）/4。因此在回溯搜索過(guò)程中可用當(dāng)前符號(hào)三角形所包含的“+”號(hào)個(gè)數(shù)與“-”號(hào)個(gè)數(shù)均不超過(guò)n*（n+1）/4作為可行性約束，用于剪去不滿足約束的子樹(shù)。 對(duì)于給定的n，當(dāng)n*（n+1）/2為奇數(shù)時(shí)，顯然不存在所包含的“+”號(hào)個(gè)數(shù)與“-”號(hào)個(gè)數(shù)相同的符號(hào)三角形。 復(fù)雜度分析 計(jì)算可行性約束需要O（n）時(shí)間，在最壞情況下有O（2n）個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號(hào)三角形問(wèn)題的回溯算法所需的計(jì)算時(shí)間為O（n2n）。10.參考答案: 解空間樹(shù)： 搜索空間樹(shù)： 11.參考答案:D12.參考答案:一種方法；一個(gè)過(guò)程13.參考答案: 這是一種用于求解組合優(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ì)列相同。 2）（優(yōu)先隊(duì)列）最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果查找一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來(lái)建立，下一個(gè)E-節(jié)點(diǎn)就是具有最小耗費(fèi)的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來(lái)構(gòu)造活節(jié)點(diǎn)表，下一個(gè)E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)。14.參考答案:A,B,C,D15.參考答案:B16.參考答案:A17.參考答案:B18.參考答案: （4）搜索18：首先與27比較，1827，在前半部分搜索；再次32比較，3129，此時(shí)只有一個(gè)元素，未找到，返回-1。 搜索135：首先與27比較，135>27，在前半部分搜索；再次32比較，135>32，在前半部分搜索；與135比較，相同，返回0。19.參考答案:A20.參考答案:A21.參考答案:C22.參考答案:B23.參考答案:D24.參考答案:C25.參考答案:B26.參考答案:A27.參考答案:常用于數(shù)值問(wèn)題的求解。這類(lèi)算法所得到的往往是近似解。而且近似解的精度隨計(jì)算時(shí)間的增加不斷提高。在許多情況下，要計(jì)算出問(wèn)題的精確解是不可能或沒(méi)有必要的，因此用數(shù)值概率算法可得到相當(dāng)滿意的解。28.參考答案:A,B,C29.參考答案:A30.參考答案:正確第2卷一.參考題庫(kù)(共30題)1.從排序的穩(wěn)定性上講，快速排序是穩(wěn)定排序。2.數(shù)據(jù)結(jié)構(gòu)與算法里，漢諾塔是一類(lèi)遞歸的算法，也應(yīng)具有算法的特性（）A、有窮性B、模糊性C、二義性D、正確性3.以下排序算法中，屬于交換排序的算法有（）A、希爾排序B、冒泡排序C、快速排序D、簡(jiǎn)單選擇排序4.寫(xiě)出0/1背包問(wèn)題的動(dòng)態(tài)規(guī)劃方程，并簡(jiǎn)要說(shuō)明。5.采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）6.--即自減，其意義是自身的值減去1。7.由于貪心算法是一種只顧眼前的步驟，而難以顧及全局步驟的算法，所以它通常表現(xiàn)出哪些特點(diǎn)？8.用動(dòng)態(tài)規(guī)劃算法解0-1背包問(wèn)題：n=5，w=[2，9，4，6，7]，p=[6，10，12，8，13]，c=15。9.數(shù)據(jù)結(jié)構(gòu)與算法里，冒泡排序是不穩(wěn)定的排序。10.數(shù)據(jù)結(jié)構(gòu)與算法里，漢諾塔算法具有哪些算法的特性（）A、有窮性B、確定性C、可行性D、輸入輸出11.有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)解，所以都合適12.整數(shù)7和9的最小公倍數(shù)是（）。A、7B、9C、21D、6313.有以下程序，輸出結(jié)果是（） A、3B、4C、5D、不確定14.盤(pán)子數(shù)量是4的漢諾塔問(wèn)題，需要移動(dòng)的步數(shù)是（）A、15B、16C、17D、1815.數(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ǔ)句16.Prim算法利用（）策略求解（）問(wèn)題，其時(shí)間復(fù)雜度是（）。17.算法的“確定性”指的是組成算法的每條（）是清晰的，無(wú)歧義的。18.冒泡排序和（）都屬于交換排序。A、快速排序B、直接插入排序C、簡(jiǎn)單選擇排序D、希爾排序19.給出一個(gè)賦權(quán)無(wú)向圖如下，求頂點(diǎn)S到T的最短路（直接在圖上用粗線畫(huà)出即可） 20.數(shù)據(jù)結(jié)構(gòu)與算法里，設(shè)fun（n）表示斐波那契數(shù)列的第n項(xiàng)的值，fun是函數(shù)名，n是整型參數(shù)，那么根據(jù)遞歸思想它應(yīng)等于（）。A、fun（n）+fun（n-1）B、fun（n-1）+fun（n-2）C、fun（n-1）*fun（n-2）D、fun（n-2）+fun（n-3）21.關(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)初始值22.簡(jiǎn)述分支限界法與回溯法的異同。23.希爾排序?qū)儆诓环€(wěn)定排序，而直接插入排序是穩(wěn)定排序。24.使用回溯法進(jìn)行狀態(tài)空間樹(shù)裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類(lèi)型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是（），只使用約束條件進(jìn)行裁剪的是（）。25.由分治法產(chǎn)生的子問(wèn)題往往是（），這就為使用（）提供了方便。26.按照排序中具有相同關(guān)鍵字的記錄在排序前后的相對(duì)位置是否發(fā)生改變，排序分為（）。A、穩(wěn)定排序B、不穩(wěn)定排序C、外部排序D、內(nèi)部排序27.實(shí)現(xiàn)合并排序利用的算法是（）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法28.改進(jìn)的冒泡排序的任一趟排序過(guò)程中，如果沒(méi)有發(fā)生（），則說(shuō)明已經(jīng)有序；排序完畢。A、數(shù)據(jù)交換B、數(shù)據(jù)刪除C、數(shù)據(jù)增加D、都不對(duì)29.若線性規(guī)劃問(wèn)題存在最優(yōu)解，它一定不在（）A、可行域的某個(gè)頂點(diǎn)上B、可行域的某條邊上C、可行域內(nèi)部D、以上都不對(duì)30.回文字符串的非遞歸算法：用系統(tǒng)函數(shù)解決的方式，需要用到哪些系統(tǒng)函數(shù)（）。A、strcpyB、strcatC、strcmpD、strrev第2卷參考答案一.參考題庫(kù)1.參考答案:錯(cuò)誤2.