2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-算法設(shè)計(jì)與分析筆試參考題庫(kù)含答案

“人人文庫(kù)”水印下載源文件后可一鍵去除，請(qǐng)放心下載?。▓D片大小可任意調(diào)節(jié)）2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-算法設(shè)計(jì)與分析筆試參考題庫(kù)含答案“人人文庫(kù)”水印下載源文件后可一鍵去除，請(qǐng)放心下載！第1卷一.參考題庫(kù)(共75題)1.關(guān)于裝填因子，以下說(shuō)法正確的是（）。A、哈希表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。B、若散列表的負(fù)載因子（裝填因子）α2.以下英文字符串中是回文字符串的應(yīng)該是（）。A、123321B、11223311C、123213D、1231233.一根繩子有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-124.數(shù)據(jù)結(jié)構(gòu)與算法里，荷蘭國(guó)旗算法的基本寫(xiě)法循環(huán)中套分支結(jié)構(gòu)。5.運(yùn)算符%的計(jì)算：表達(dá)式3%7和7%3的結(jié)果分別是（）A、11B、24C、31D、736.羽毛球隊(duì)有男女運(yùn)動(dòng)員各n人。給定兩個(gè)n×n的矩陣P和Q。P[i][j]是男運(yùn)動(dòng)員i和女運(yùn)動(dòng)員j配合組成混合雙打的競(jìng)賽優(yōu)勢(shì)，Q[i][j]是女運(yùn)動(dòng)員i和男運(yùn)動(dòng)員j配合的競(jìng)賽優(yōu)勢(shì)。由于技術(shù)配合或心理狀況等各種因素的影響，P[i][j]并不一定等于Q[j][i]。 采用回溯法設(shè)計(jì)一個(gè)算法，計(jì)算男女運(yùn)動(dòng)員最佳搭配的配對(duì)法，使得各組男女雙方競(jìng)賽優(yōu)勢(shì)乘積的總和達(dá)到最大。7.哪種排序可能發(fā)生：在最后一趟排序開(kāi)始之前，所有記錄均不在其最終位置上（）。A、直接插入排序B、簡(jiǎn)單選擇排序C、冒泡排序D、快速排序8.荷蘭國(guó)旗問(wèn)題，定義交換兩個(gè)元素的函數(shù)，參數(shù)為指針，請(qǐng)問(wèn)當(dāng)參數(shù)為指針類(lèi)型的函數(shù)，其傳遞屬于（）。A、值傳遞B、地址傳遞C、形參傳遞D、實(shí)參傳遞9.數(shù)據(jù)結(jié)構(gòu)中，O（n）是以下哪種算法的復(fù)雜度（）。A、順序查找B、順序表刪除元素C、順序表插入元素D、單鏈表查找第i個(gè)元素10.下列算法中通常以自頂向下的方式求解最優(yōu)解的是（）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法11.在一個(gè)6×6的棋盤(pán)上，共放置12顆棋子，每個(gè)格子最多只能放一個(gè)棋子，要求每一行，每一列以及兩條主對(duì)角線上恰好都是兩顆棋子。請(qǐng)用回溯法輸出所有可能的布局。在不考慮對(duì)稱(chēng)的情況下，共有多少種布局？12.利用概率的性質(zhì)計(jì)算近似值的隨機(jī)算法是（），運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是（）。13.數(shù)據(jù)結(jié)構(gòu)與算法里，二叉排序樹(shù)的右子樹(shù)也應(yīng)該是棵二叉排序樹(shù)14.算法是由若干條指令組成的有窮序列，且要滿足輸入、（）、確定性和（）四條性質(zhì)。15.數(shù)據(jù)結(jié)構(gòu)與算法中，屬于插入排序的有（）。A、希爾排序B、直接插入排序C、冒泡排序D、簡(jiǎn)單選擇排序16.數(shù)據(jù)結(jié)構(gòu)與算法里，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度是（）A、O（n*n）B、O（nlog2n）C、O（1）D、都不對(duì)17.數(shù)據(jù)結(jié)構(gòu)與算法里，循環(huán)結(jié)構(gòu)是用來(lái)描述可以重復(fù)執(zhí)行的程序。18.scanf語(yǔ)句用于格式化輸出的，例如%d是輸出整型數(shù)據(jù)的。19.數(shù)據(jù)結(jié)構(gòu)與算法里，O（n）是以下哪種算法的復(fù)雜度（）。A、順序查找B、順序表刪除元素C、順序表插入元素D、單鏈表查找第i個(gè)元素20.若有說(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]21.數(shù)據(jù)結(jié)構(gòu)與算法里，動(dòng)態(tài)查找的典型工具是（），請(qǐng)將不是這個(gè)答案的選項(xiàng)選上。A、二叉排序樹(shù)B、棧C、數(shù)組D、隊(duì)列22.數(shù)據(jù)結(jié)構(gòu)中，二叉排序的的哪些遍歷序列，不能得到一個(gè)升序序列，或非遞減有序序列。（）A、先序序列B、中序遍歷C、后序遍歷D、按層次遍歷序列23.數(shù)據(jù)結(jié)構(gòu)與算法里，快速排序在（）情況下，不利于發(fā)揮其長(zhǎng)處。A、完全亂序B、基本有序C、雜亂無(wú)章D、都不對(duì)24.C語(yǔ)言中，continue的作用是（）A、結(jié)束本次循環(huán)，繼續(xù)下一次循環(huán)B、結(jié)束本層循環(huán)C、結(jié)束本次循環(huán)，不繼續(xù)下一次循環(huán)D、與case搭檔，跳出switch語(yǔ)句25.概率算法有數(shù)值概率算法、舍伍德算法和（）、（）。26.用回溯法解布線問(wèn)題時(shí)，求最優(yōu)解的主要程序段如下：如果布線區(qū)域劃分為n×m的方格陣列，擴(kuò)展每個(gè)結(jié)點(diǎn)需O（1）的時(shí)間，L為最短布線路徑的長(zhǎng)度，則算法共耗時(shí)（O（mn）），構(gòu)造相應(yīng)的最短距離需要（O（L））時(shí)間。27.下列各步驟的先后順序是（）。 ①調(diào)試程序 ②分析問(wèn)題 ③設(shè)計(jì)算法 ④編寫(xiě)程序28.以下代碼的執(zhí)行結(jié)果是：（） A、是0B、是24C、是6D、是12029.冒泡排序按照各種分類(lèi)可以是（）。A、穩(wěn)定排序B、交換排序C、內(nèi)排序30.分支限界法是一種既帶有（）又帶有（）的搜索算法。31.數(shù)據(jù)結(jié)構(gòu)與算法里，下列選項(xiàng)中關(guān)于穩(wěn)定排序說(shuō)法正確的是（）。A、穩(wěn)定排序是指對(duì)于關(guān)鍵字相等的記錄，排序前后相對(duì)位置不變B、穩(wěn)定排序是指對(duì)于關(guān)鍵字相等的記錄，排序前后相對(duì)位置可以變化C、穩(wěn)定排序是指排序是指將記錄變成無(wú)序的32.有若干只雞兔同在一個(gè)籠子里，從上面數(shù)，有35個(gè)頭；從下面數(shù)，有94只腳。求籠中各有幾只雞和兔？（）A、雞有23只，兔有12只B、雞有12只，兔有23只C、雞有20只，兔有15只D、雞有15只，兔有20只33.一個(gè)人有一捆草，一只羊，一頭老虎。他想把草、羊、老虎運(yùn)過(guò)河。但是老虎要吃羊，羊要吃草。他要羊不吃草，虎不吃羊。完整運(yùn)過(guò)去。請(qǐng)問(wèn)應(yīng)怎樣運(yùn)？試寫(xiě)出完整的搬運(yùn)步驟。34.設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H（key）=key%p，則p最好選擇（）。A、小于等于m的最大奇數(shù)B、小于等于m的最大素?cái)?shù)C、小于等于m的最大偶數(shù)D、小于等于m的最大合數(shù)35.希爾排序就分類(lèi)而言屬于（）A、歸并排序B、選擇排序C、交換排序D、插入排序36.有n個(gè)獨(dú)立的作業(yè){1，2，..，n}，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的處理時(shí)間為ti?，F(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)解，所以都合適37.定義二維數(shù)組intarr[4][2]如果全部元素輸出，共需要輸出6個(gè)元素38.回文字符串算法，不可以判斷一串漢字字符串是否是回文。39.最大效益優(yōu)先是（）的一搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法40.Olay教授正在為一家石油公司咨詢(xún)，該公司正在計(jì)劃建造一條由東向西的石油主管道，該管道要穿過(guò)一片有n口井的油田，從每口井中都有一條噴油管沿最短路徑與主管道直接相連（噴油管道為南北方向）。 給定各個(gè)井的X坐標(biāo)和Y坐標(biāo)，Olay教授要如何才能選擇最佳主管道的位置（即：使各噴油管長(zhǎng)度之和最?。?？ 41.什么是P類(lèi)問(wèn)題？什么是NP類(lèi)問(wèn)題？請(qǐng)描述集合覆蓋問(wèn)題的近似算法的基本思想。42.數(shù)據(jù)結(jié)構(gòu)與算法里，冒泡排序N個(gè)記錄需要N-1趟排序，就可以完成排序。43.排序和查找是經(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。44.數(shù)據(jù)結(jié)構(gòu)中，動(dòng)態(tài)查找的常用方法是二叉排序樹(shù)。45.數(shù)據(jù)結(jié)構(gòu)與算法里，屬于先預(yù)測(cè)型的循環(huán)有，即先判斷決定是否去循環(huán)（）A、whileB、do-whileC、forD、switch46.數(shù)據(jù)結(jié)構(gòu)與算法里，希爾排序又稱(chēng)為（）。A、縮小增量排序B、二分插入排序C、多路歸并排序D、錦標(biāo)賽排序47.數(shù)據(jù)結(jié)構(gòu)與算法里，在C語(yǔ)言中，有以下二維數(shù)組的定義inta[4][5]；如想引用第五個(gè)元素，則書(shū)寫(xiě)（）。A、a[4]B、a[5]C、a[0][4]D、a[1][5]48.屬于1-10000以?xún)?nèi)的完數(shù)的是（）A、13B、28C、7D、49849.N個(gè)記錄是有序的使用什么查找效率更高（）A、順序查找B、折半查找C、分塊查找D、隨機(jī)查找50.chars1[100]="ABC"，s2[100]="abc"；則strcmp（s1，s2）的結(jié)果是（）。A、是0B、是1C、是-1D、不確定51.哈夫曼編碼可利用（）算法實(shí)現(xiàn)。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法52.數(shù)據(jù)結(jié)構(gòu)與算法里，若有函數(shù)定義如下：則以下涉及上述函數(shù)的說(shuō)明語(yǔ)句錯(cuò)誤的（） A、doublefun（intx）；B、doublefun（inty）；C、intfun（intx，inty）；D、doublefun（inta，intb）；53.假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量M=150，使用回溯方法求解此背包問(wèn)題。請(qǐng)寫(xiě)出狀態(tài)空間搜索樹(shù)并計(jì)算各個(gè)節(jié)點(diǎn)處的界限函數(shù)值，最后給出裝載方案及背包中物品的重量和價(jià)值。 54.數(shù)據(jù)結(jié)構(gòu)與算法里，若查找表中不存在特定元素，稱(chēng)（）。A、查找失敗B、查找成功C、不確定D、都不對(duì)55.二叉排序樹(shù)是否可能是一棵完全二叉樹(shù)（）。A、不可能B、可能C、不確定能不能D、都不對(duì)56.數(shù)據(jù)結(jié)構(gòu)與算法里，A函數(shù)調(diào)用B函數(shù)，B函數(shù)又調(diào)用了A函數(shù)，這種調(diào)用是（），下列選項(xiàng)不是正確答案的是（）。A、直接遞歸B、間接遞歸C、非遞歸D、嵌套調(diào)用57.數(shù)據(jù)結(jié)構(gòu)與算法里，斐波那契數(shù)列的第5項(xiàng)的值是（）。A、1B、2C、5D、858.對(duì)于如下描述的背包問(wèn)題，請(qǐng)計(jì)算最終裝入背包的最大價(jià)值和以及各個(gè)物品裝入背包的數(shù)量。 背包容量：C＝50千克。3件物品。物品1重20千克，價(jià)值100元；物品2重20千克，價(jià)值120元；物品3重30千克，價(jià)值90元。59.對(duì)以下代碼描述正確的是（） A、循環(huán)執(zhí)行4次B、循環(huán)條件第1次就不成立，所以循環(huán)體一次也不執(zhí)行C、循環(huán)執(zhí)行5次D、循環(huán)次數(shù)不確定60.若哈希表的裝填因子α<1，則可避免沖突的產(chǎn)生。61.請(qǐng)寫(xiě)出用回溯法解裝載問(wèn)題的函數(shù)。裝載問(wèn)題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi。裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。62.數(shù)據(jù)結(jié)構(gòu)與算法里，散列表的地址區(qū)間為0-17，散列函數(shù)為H（K）=Kmod17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。則元素59存放在散列表中的地址是（）A、8B、9C、10D、1163.數(shù)據(jù)結(jié)構(gòu)與算法中，設(shè)哈希表長(zhǎng)為14，哈希函數(shù)是H（key）=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是（）。A、8B、9C、5D、364.求證：log（n!）=Θ（nlogn）。65.分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)0-1背包問(wèn)題。要求：說(shuō)明所使用的算法策略；寫(xiě)出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。66.負(fù)載因子（裝填因子）是哈希表的一個(gè)重要參數(shù)，它反映哈希表的裝滿程度，該值越大則發(fā)生沖突可能性越大。67.給定已按升序排好序的n個(gè)元素a[0：n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。 據(jù)此容易設(shè)計(jì)出二分搜索算法，橫線處填（） 68.簡(jiǎn)單選擇排序、快速排序都是不穩(wěn)定排序。69.優(yōu)先隊(duì)列通常用（）數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。A、棧B、堆C、隊(duì)列D、二叉查找樹(shù)70.簡(jiǎn)單選擇排序每趟排序可能出現(xiàn)多次記錄交換。71.數(shù)據(jù)結(jié)構(gòu)中，由同一類(lèi)型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合稱(chēng)為（）。A、數(shù)據(jù)庫(kù)B、查找表C、檢索器72.數(shù)據(jù)結(jié)構(gòu)與算法中，希爾排序就穩(wěn)定性和內(nèi)外排序而言，屬于（）。A、穩(wěn)定排序B、不穩(wěn)定排序C、內(nèi)排序D、外排序73.以下能正確定義一維數(shù)組的選項(xiàng)是（）A、intnum[]；B、intnum[0..100]；C、#defineN5intnum[N]；D、ntN=100；intnum[N]；74.求證：O（f（n））+O（g（n））=O（max{f（n），g（n）}）。75.回溯法是一種既帶有（）又帶有（）的搜索算法。第2卷一.參考題庫(kù)(共75題)1.數(shù)據(jù)結(jié)構(gòu)與算法里，雞兔同籠算法具有的特性包括（）A、有窮性B、確定性C、可行性D、正確性2.對(duì)于一維數(shù)組，訪問(wèn)其中的元素時(shí)，可隨機(jī)訪問(wèn)，只要制定的下標(biāo)不越界即可3.窮舉法也稱(chēng)枚舉法列舉所有可能，逐一試探。4.數(shù)據(jù)結(jié)構(gòu)與算法里，從排序的穩(wěn)定性來(lái)看，快速排序是（）。A、不穩(wěn)定排序B、穩(wěn)定排序C、不確定D、都不對(duì)5.用分割元素v將有n個(gè)元素的數(shù)組分割成元素大于v和小于v的兩部分，需要花多少時(shí)間（要講出道理）。6.一定范圍內(nèi)的完數(shù)求和的求解過(guò)程使用循環(huán)嵌套完成，其時(shí)間復(fù)雜度是（）A、O（1）B、O（n）C、O（log2n）D、O（n*n）7.程序調(diào)用自身的編程技巧稱(chēng)為遞歸，遞歸的英文是（）。A、returnB、recursionC、restartD、reverse8.數(shù)據(jù)結(jié)構(gòu)中，二叉排序樹(shù)是（）經(jīng)常使用的方式。A、靜態(tài)查找B、動(dòng)態(tài)查找C、隨機(jī)查找D、跳躍查找9.有9個(gè)村莊，其坐標(biāo)位置如下表所示： 現(xiàn)在要蓋一所郵局為這9個(gè)村莊服務(wù)，請(qǐng)問(wèn)郵局應(yīng)該蓋在（）才能使到郵局到這9個(gè)村莊的總距離和最短。A、（4.5，0）B、（4.5，4.5）C、（5，5）D、（5，0）10.數(shù)據(jù)結(jié)構(gòu)與算法里，屬于內(nèi)排序的包含（）。A、快速排序B、冒泡排序C、直接插入排序D、希爾排序11.數(shù)據(jù)結(jié)構(gòu)與算法里，希爾排序又叫縮小增量排序，屬于基數(shù)排序的一種。12.簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法的基本步驟。13.設(shè)函數(shù)f1、f2和f3的處理時(shí)間分別為O（n）、O（n2）和O（1），分析下列流程的時(shí)間復(fù)雜性： 14.數(shù)據(jù)結(jié)構(gòu)與算法中，查找哈希表，解決沖突的方法包括（）。A、數(shù)字分析法B、除留余數(shù)法C、直接地址法D、線性探測(cè)再散列法15.編寫(xiě)計(jì)算斐波那契（Fibonacci）數(shù)列的第n項(xiàng)函數(shù)fib（n）。16.冒泡排序的每一趟的過(guò)程是要比較（）元素，如果逆序進(jìn)行交換。A、相鄰B、不相鄰C、首尾D、都不對(duì)17.數(shù)據(jù)結(jié)構(gòu)與算法里，冒泡排序是不穩(wěn)定的排序。18.數(shù)據(jù)結(jié)構(gòu)與算法里，查找的結(jié)果可能在集合中也可能不在集合中，分別稱(chēng)為（）。A、查找失敗B、查找成功C、不確定D、都不對(duì)19.T（n）表示當(dāng)輸入規(guī)模為n時(shí)的算法效率，以下算法效率最優(yōu)的是（）A、T（n）=T（n–1）+1，T（1）=1B、T（n）=2n2C、T（n）=T（n/2）+1，T（1）=1D、T（n）=3nlog2n20.一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件滿足時(shí)，遞歸（）A、進(jìn)行運(yùn)算B、返回C、前進(jìn)D、結(jié)束條件21.ACM算法的素?cái)?shù)算法可以（）來(lái)完成。A、使用for循環(huán)B、只用switch語(yǔ)句C、只用if語(yǔ)句D、只用printf語(yǔ)句22.int型數(shù)據(jù)與float型數(shù)據(jù)可以互相進(jìn)行強(qiáng)制轉(zhuǎn)換。23.實(shí)現(xiàn)合并排序利用的算法是（）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法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.二叉排序樹(shù)的（）上結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值。A、左子樹(shù)B、右子樹(shù)C、左子樹(shù)和右子樹(shù)D、都不對(duì)26.給定一個(gè)由n個(gè)數(shù)組成的序列，要求該序列的最長(zhǎng)單調(diào)上升子序列，請(qǐng)?jiān)O(shè)計(jì)對(duì)應(yīng)的算法并分析其時(shí)間復(fù)雜度，如果時(shí)間復(fù)雜度劣于O（nlogn）的，將其優(yōu)化為O（nlogn）時(shí)間復(fù)雜度的算法。27.請(qǐng)畫(huà)出用回溯法解n=3的0-1背包問(wèn)題的解空間樹(shù)和當(dāng)三個(gè)物品的重量為{20，15，10}，價(jià)值為{20，30，25}，背包容量為25時(shí)搜索空間樹(shù)。28.請(qǐng)畫(huà)出用回溯法解4皇后問(wèn)題的解空間樹(shù)和搜索空間樹(shù)。29.可以通過(guò)賦初值的方式確定數(shù)組元素的個(gè)數(shù)。30.Prim算法和Dijkstra算法選擇下一個(gè)節(jié)點(diǎn)的標(biāo)準(zhǔn)分別是什么？對(duì)于有負(fù)邊的無(wú)向圖，Prim算法和Dijkstra算法還能保證獲得最優(yōu)解嗎？31.有4個(gè)矩陣{A1，A2，A3，A4}，其中Ai與Ai＋1是可乘的，i=1，2，3，連乘積為A1A2A3A4。在這個(gè)四矩陣連乘積問(wèn)題中，請(qǐng)問(wèn)不同子問(wèn)題的個(gè)數(shù)總共有多少個(gè)，并請(qǐng)把所有的子問(wèn)題列出來(lái)。32.引用數(shù)組元素時(shí)，其數(shù)組下標(biāo)的數(shù)據(jù)類(lèi)型允許的是：整型常量或整型表達(dá)式33.下面關(guān)于NP問(wèn)題說(shuō)法正確的是（）A、NP問(wèn)題都是不可能解決的問(wèn)題B、P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中C、NP完全問(wèn)題是P類(lèi)問(wèn)題的子集D、NP類(lèi)問(wèn)題包含在P類(lèi)問(wèn)題中34.下面關(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)中35.數(shù)據(jù)結(jié)構(gòu)與算法里，較孫子算經(jīng)中的雙層循環(huán)解決的雞兔同籠問(wèn)題的時(shí)間復(fù)雜度低的是（）A、O（n*n）B、O（nlog2n）C、O（n*n*n）D、O（2^n）^表示冪36.算法設(shè)計(jì)的質(zhì)量指標(biāo)有哪些？37.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，就性能而言，希爾排序的時(shí)間復(fù)雜度是（）。A、O（n*n）B、O（nlog2n）C、O（n）D、O（n3/2）38.對(duì)布線問(wèn)題，以下（）是不正確描述。A、布線問(wèn)題的解空間是一個(gè)圖B、可以對(duì)方格陣列四周設(shè)置圍墻，即增設(shè)標(biāo)記的附加方格的預(yù)處理，使得算法簡(jiǎn)化對(duì)邊界的判定C、采用廣度優(yōu)先的標(biāo)號(hào)法找到從起點(diǎn)到終點(diǎn)的布線方案（這個(gè)方案如果存在的話）不一定是最短的D、采用先入先出的隊(duì)列作為活結(jié)點(diǎn)表，以終點(diǎn)b為擴(kuò)展結(jié)點(diǎn)或活結(jié)點(diǎn)隊(duì)列為空作為算法結(jié)束條件39.n個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水，水桶有大有小，請(qǐng)問(wèn)他們?cè)鯓优抨?duì)，才能使得總的排隊(duì)時(shí)間最短。（）A、水桶大的人先打水B、水桶小的人先打水C、按照什么順序都一樣D、先到的人先打水40.數(shù)據(jù)結(jié)構(gòu)中，下列選項(xiàng)中符合折半查找的前提的是（）。A、順序存儲(chǔ)B、記錄有序C、記錄無(wú)序D、鏈?zhǔn)酱鎯?chǔ)41.數(shù)據(jù)結(jié)構(gòu)與算法里，裝填因子又稱(chēng)為（）。A、負(fù)載因子B、平衡因子C、外力因子D、合力因子42.數(shù)據(jù)結(jié)構(gòu)與算法里，改進(jìn)的冒泡排序最好的情況是（），只需要一趟，發(fā)現(xiàn)無(wú)數(shù)據(jù)交換，就可以停止，排序完畢。A、記錄完全逆序B、記錄完全有序C、記錄雜亂無(wú)序D、都不對(duì)43.下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（）A、數(shù)值概率算法B、舍伍德算法C、拉斯維加斯算法D、蒙特卡羅算法44.函數(shù)的這種調(diào)用方式屬于（） A、窮舉B、遞歸C、迭代D、分治45.數(shù)據(jù)結(jié)構(gòu)中，下列選項(xiàng)中是折半查找的時(shí)間復(fù)雜度的是（）。A、O（1）B、O（log2n）C、O（n*n）D、O（n）46.數(shù)據(jù)結(jié)構(gòu)與算法里，與i=i*2；等價(jià)的語(yǔ)句是（）A、i+=2；B、i++；C、i=i*2；D、i**47.與順序查找算法相比，折半查找算法的時(shí)間復(fù)雜性有多大程度的降低？它是如何提高算法的效率的？48.數(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ǔ)句的下面49.一般背包問(wèn)題的貪心算法可以獲得最優(yōu)解嗎？物品的選擇策略是什么？50.數(shù)據(jù)結(jié)構(gòu)與算法里，變量height要比原來(lái)少15，則應(yīng)寫(xiě)成（）A、height-15B、height=15C、height=-15D、height-=1551.do..while條件為假時(shí)一次也不執(zhí)行循環(huán)體語(yǔ)句52.循環(huán)語(yǔ)句中，循環(huán)執(zhí)行次數(shù)是（） A、5B、100C、3D、453.30個(gè)記錄進(jìn)行冒泡排序，使用未改進(jìn)的冒泡排序，則需要（）趟排序才能完成排序。A、29B、30C、28D、2754.漢諾塔問(wèn)題是古老的問(wèn)題，不可以使用遞歸解決，最初是原型是印度的僧人移動(dòng)盤(pán)子的故事。55.數(shù)據(jù)結(jié)構(gòu)與算法里，計(jì)算完數(shù)和，有累加器名為sum，應(yīng)如何賦初值（）A、sum=0B、sum==0C、sum+=0；D、sum=1；56.貪心算法的基本要素是（）質(zhì)和（）性質(zhì)。57.在C語(yǔ)言中若有定義語(yǔ)句inta[6]按在內(nèi)存中的存放順序，a數(shù)組的第3個(gè)元素是（）A、[4]B、a[1]C、a[3]D、a[2]58.給出一個(gè)由n個(gè)數(shù)組成的序列A[1…n]，要求找出它的最長(zhǎng)單調(diào)上升子序列，設(shè)m[i]（1≤i≤n），表示以A[i]結(jié)尾的最長(zhǎng)單調(diào)上升子序列的長(zhǎng)度，則m[1]=1，m[i]（1A、m[i]=1+max{0，m[k]（A[k]B、m[i]=1+m[k]（k=i-1&&i>1）C、m[i]=1+max{0，m[k]（A[k]≤A[i]，1≤k<i）}D、m[i]=max{0，m[k]（A[k]59.對(duì)于含有n個(gè)元素的子集樹(shù)問(wèn)題，最壞情況下其解空間的葉結(jié)點(diǎn)數(shù)目為（）A、n!B、2nC、2n+1-1D、60.哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）61.數(shù)據(jù)結(jié)構(gòu)與算法里，交換排序和插入排序是沒(méi)有什么區(qū)別的。62.舍伍德算法總能求得問(wèn)題的（）。63.break語(yǔ)句格式中，使用正確的是（）A、while（條件）{break；}B、其它三項(xiàng)都不對(duì)C、for（；；）{break；}D、do{break；}while（條件）；64.數(shù)據(jù)結(jié)構(gòu)與算法里，從算法的設(shè)計(jì)要求上講，漢諾塔應(yīng)具有（）。A、有窮性B、確定性C、可行性D、可讀性65.若變量inti，intsum=0，要求程序段完成求1加到100的和的，能完成此操作的程序段不正確的是（）A、for（i=1；i66.數(shù)據(jù)結(jié)構(gòu)與算法里，順序表的查找有順序查找和（）。A、折半查找B、線性查找C、隨機(jī)查找D、索引查找67.數(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ì)68.雞兔同籠不僅僅限于孫子算經(jīng)中描述，也可以其它類(lèi)似問(wèn)題，如大人小孩吃面包的問(wèn)題，或者是大小油瓶的問(wèn)題。69.比較回溯法和分支限界法的搜索方式，哪種方法更適合找最優(yōu)解問(wèn)題？70.數(shù)據(jù)結(jié)構(gòu)與算法里，屬于不穩(wěn)定排序的是（）。A、快速排序B、冒泡排序C、直接插入排序D、希爾排序71.冒泡排序的時(shí)間復(fù)雜度是O（n*n）。72.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法73.希爾排序?qū)儆诓环€(wěn)定排序，而直接插入排序是穩(wěn)定排序。74.下述表達(dá)不正確的是（）A、n2/2+2n的漸進(jìn)表達(dá)式上界函數(shù)是O（2n）B、n2/2+2n的漸進(jìn)表達(dá)式下界函數(shù)是Ω（2n）C、logn3的漸進(jìn)表達(dá)式上界函數(shù)是O（logn）D、logn3的漸進(jìn)表達(dá)式下界函數(shù)是Ω（n3）75.冒泡排序的時(shí)間復(fù)雜度（）。A、O（n）B、O（n*n）C、O（1）D、都不對(duì)第1卷參考答案一.參考題庫(kù)1.參考答案：C,D2.參考答案：A3.參考答案：A4.參考答案：正確5.參考答案：C6.參考答案： 對(duì)于這個(gè)問(wèn)題，解空間如下： 在這個(gè)解空間中采用回溯方法，由于一個(gè)男隊(duì)員只能和一個(gè)女隊(duì)員搭檔，反之也同理，因此，對(duì)于搜索的第一步選定某男和某女，那么第二個(gè)男隊(duì)員就不能和第一個(gè)男隊(duì)員的女搭檔組合，因此，剪去改女隊(duì)員的分枝。 將男女隊(duì)員的競(jìng)賽優(yōu)勢(shì)乘積計(jì)算出來(lái)，然后將各組男女的優(yōu)勢(shì)乘積進(jìn)行相加。找出最大值。7.參考答案：A8.參考答案：B9.參考答案：A,B,C,D10.參考答案：C11.參考答案：12.參考答案：數(shù)值概率算法；蒙特卡羅算法13.參考答案：正確14.參考答案：輸出；有限性15.參考答案：A,B16.參考答案：A17.參考答案：正確18.參考答案：錯(cuò)誤19.參考答案：A,B,C,D20.參考答案：D21.參考答案：B,C,D22.參考答案：A,C,D23.參考答案：B24.參考答案：A25.參考答案：拉斯維加斯；蒙特卡羅26.參考答案：27.參考答案：②③④①28.參考答案：A29.參考答案：A,B,C30.參考答案：系統(tǒng)性；跳躍性31.參考答案：A32.參考答案：A33.參考答案： 1、運(yùn)羊； 2、運(yùn)草；把羊帶回。 3、運(yùn)虎； 4、運(yùn)羊。34.參考答案：B35.參考答案：D36.參考答案：B37.參考答案：錯(cuò)誤38.參考答案：正確39.參考答案：A40.參考答案： 這是中位數(shù)的應(yīng)用問(wèn)題。在順序統(tǒng)計(jì)的問(wèn)題中，中位數(shù)的應(yīng)用最廣，例如在X軸上有n個(gè)點(diǎn)，由左到右依次排列為X1，X2，…，Xn。 我們希望在x軸上尋找一點(diǎn)Xp，使得Xp與各點(diǎn)距離之和最小。這個(gè)問(wèn)題可以歸結(jié)為中位數(shù)問(wèn)題。即： 當(dāng)n為奇數(shù)時(shí)，Xp為X（n+1）/2，否則，Xp為 從這個(gè)例子出發(fā)，本題求主油管道的問(wèn)題也是類(lèi)似的。 由于主管道由東向西，因此，要使連接油井和主油管道的噴井管道最短，噴井管道必須南北走向，與主管道垂直，即主管道的最優(yōu)位置應(yīng)為一條Y＝Y(jié)k的水平線，問(wèn)題是Yk如何確定。 為了使Yk與各油井的Y坐標(biāo)Y1，Y2，…，Yn間的距離和最短，我們將Y1，…，Yn由小到大排序，選擇最中間的那個(gè)點(diǎn)作為Yk，（若油井為奇數(shù)，則取第（n+1）/2小的Y坐標(biāo)作為Yk，若油井為偶數(shù)，則取第n/2小的Y坐標(biāo)值與第（n/2+1）小的Y坐標(biāo)值的平均數(shù)作為Yk的值。 顯然，確定主油管道的最佳位置，實(shí)際上就是求n個(gè)油井的Y坐標(biāo)的中位數(shù)。41.參考答案：用確定的圖靈機(jī)可以在多項(xiàng)式實(shí)踐內(nèi)可解的判定問(wèn)題稱(chēng)為P類(lèi)問(wèn)題。 用不確定的圖靈機(jī)在多項(xiàng)式實(shí)踐內(nèi)可解的判定問(wèn)題稱(chēng)為P類(lèi)問(wèn)題。 集合覆蓋問(wèn)題的近似算法采用貪心思想：對(duì)于問(wèn)題，每次選擇F中覆蓋了盡可能多的未被覆蓋元素的子集S，然后將U中被S覆蓋的元素刪除，并將S加入C中，最后得到的C就是近似最優(yōu)解。42.參考答案：正確43.參考答案： （4）搜索18：首先與27比較，1827，在前半部分搜索；再次32比較，3129，此時(shí)只有一個(gè)元素，未找到，返回-1。 搜索135：首先與27比較，135>27，在前半部分搜索；再次32比較，135>32，在前半部分搜索；與135比較，相同，返回0。44.參考答案：正確45.參考答案：A,C46.參考答案：A47.參考答案：C48.參考答案：B49.參考答案：B50.參考答案：C51.參考答案：C52.參考答案：A,B,D53.參考答案： 按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA。將它們的序號(hào)分別記為1～7。則可生產(chǎn)如下的狀態(tài)空間搜索樹(shù)。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過(guò)如下方式求得： 在Q1處獲得該問(wèn)題的最優(yōu)解為（1，1，1，1，0，0，1），背包效益為170。即在背包中裝入物品F，B，G，D，A時(shí)達(dá)到最大效益，為170，重量為150。 54.參考答案：A55.參考答案：B56.參考答案：A,C,D57.參考答案：C58.參考答案： 物品1的單位重量?jī)r(jià)值為50元/千克；物品2的單位重量?jī)r(jià)值為60元/千克；物品3的單位重量?jī)r(jià)值為30元/千克。采用貪心算法解此背包問(wèn)題。 此時(shí)，貪心的策略是：每次選擇單位重量?jī)r(jià)值最大的物品。因此，首先選擇物品2，然后是物品1，最后是物品3，直至將背包裝滿。 物品2全部裝入背包，當(dāng)前背包中價(jià)值120元，背包占用20千克，剩余30千克； 物品1全部裝入背包，當(dāng)前背包中價(jià)值220元（120元＋100元），背包占用40千克，剩余10千克； 物品3的1/3被裝入背包，當(dāng)前背包中價(jià)值250元（120元＋100元＋90元×1/3），背包占用50千克（裝滿）。 因此，最終裝入背包的最大價(jià)值為250元，物品1和物品2都全部裝入，分別是20千克和20千克，物品3裝入1/3，是10千克。59.參考答案：C60.參考答案：錯(cuò)誤61.參考答案：62.參考答案：D63.參考答案：B64.參考答案：65.參考答案：（1）貪心算法O（nlog（n）） 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jì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） 66.參考答案：正確67.參考答案： ；；68.參考答案：正確69.參考答案：B70.參考答案：錯(cuò)誤71.參考答案：B72.參考答案：B,C73.參考答案：C74.參考答案：對(duì)于任意f1（n）∈O（f（n）），存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有≥n1，有f1（n）≤c1f（n）。 類(lèi)似地，對(duì)于任意g1（n）∈O（g（n）），存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n≥n2，有g(shù)1（n）≤c2g（n）。 75.參考答案：系統(tǒng)性；跳躍性第2卷參考答案一.參考題庫(kù)1.參考答案：A,B,C2.參考答案：正確3.參考答案：正確4.參考答案：A5.參考答案：至少需要對(duì)每個(gè)元素進(jìn)行一次比較運(yùn)算，運(yùn)算時(shí)間是O（n）。6.參考答案：D7.參考答案：B8.參考答案：B9.參考答案：C10.參考答案：A,B,C,D11.參考答案：錯(cuò)誤12.參考答案： 設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通常可按以下幾個(gè)步驟進(jìn)行： （1）劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序的（即無(wú)后向性），否則問(wèn)題就無(wú)法用動(dòng)態(tài)規(guī)劃求解。 （2）選擇狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。 （3）確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫(xiě)出來(lái)了。但事實(shí)上，我們常常是反過(guò)來(lái)做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來(lái)確定決策。 （4）寫(xiě)出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。 一般說(shuō)來(lái)，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡(jiǎn)單的。動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完