昆明理工大學(xué)2021年算法分析與設(shè)計(jì)考研真題

昆明理工大學(xué)2021年[算法分析與設(shè)計(jì)]考研真題一、選擇題1、二分搜索算法是利用（）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法2、在下列算法中有時(shí)找不到問(wèn)題解的是（）。A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法3、以下不可以使用分治法求解的是（）。A棋盤(pán)覆蓋問(wèn)題B選擇問(wèn)題C歸并排序D0/1背包問(wèn)題4、下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法5、分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（）。A、最小堆B、最大堆C、棧D、數(shù)組6、回溯法的效率不依賴(lài)于下列哪些因素（）。A、滿足顯約束的值的個(gè)數(shù)B、計(jì)算約束函數(shù)的時(shí)間C、計(jì)算限界函數(shù)的時(shí)間D、確定解空間的時(shí)間7、（）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)8、分支限界法解旅行售貨員問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（）。A、最小堆B、最大堆C、棧D、數(shù)組9、下面問(wèn)題（）不能使用貪心法解決。A、單源最短路徑問(wèn)題B、N皇后問(wèn)題C、最小生成樹(shù)問(wèn)題D、背包問(wèn)題10、回溯法搜索狀態(tài)空間樹(shù)是按照（）的順序。A、中序遍歷B、廣度優(yōu)先遍歷C、深度優(yōu)先遍歷D、層次優(yōu)先遍歷11、下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（）。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)12、合并排序算法是利用（）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法13、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）14、實(shí)現(xiàn)最大子段和利用的算法是（）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法15、優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（）。A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)16、廣度優(yōu)先是（）的一搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法17、下列哪一種算法是隨機(jī)化算法（）。A、貪心算法B、回溯法C、動(dòng)態(tài)規(guī)劃算法D、舍伍德算法18、實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是（）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法19、能采用貪心算法求最優(yōu)解的問(wèn)題，一般具有的重要性質(zhì)為：（）。A、最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B、重疊子問(wèn)題性質(zhì)與貪心選擇性質(zhì)C、最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)D、預(yù)排序與遞歸調(diào)用20、常見(jiàn)的兩種分支限界法為（）。A、廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法B、隊(duì)列式（FIFO）分支限界法與堆棧式分支限界法C、排列樹(shù)法與子集樹(shù)法D、隊(duì)列式（FIFO）分支限界法與優(yōu)先隊(duì)列式分支限界法二、簡(jiǎn)答題1、請(qǐng)用數(shù)學(xué)化的語(yǔ)言來(lái)描述“最優(yōu)化原理”的概念。2、解釋什么是NP類(lèi)問(wèn)題。3、算法A和算法B解同一問(wèn)題，設(shè)算法A的時(shí)間復(fù)雜性滿足遞歸方程算法B的時(shí)間復(fù)雜性滿足遞歸方程，若要使得算法A時(shí)間復(fù)雜性的階高于算法B時(shí)間復(fù)雜性的階，a的最大整數(shù)值可取多少？4、比較分支限界法與回溯法的異同。5、旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。證明TSP問(wèn)題滿足最優(yōu)性原理。三、應(yīng)用題1、在Internet上的搜索引擎經(jīng)常需要對(duì)信息進(jìn)行比較，比如可以通過(guò)某個(gè)人對(duì)一些事物的排名來(lái)估計(jì)他（或她）對(duì)各種不同信息的興趣，從而實(shí)現(xiàn)個(gè)性化的服務(wù)。對(duì)于不同的排名結(jié)果可以用逆序來(lái)評(píng)價(jià)它們之間的差異。考慮1,2,…,n的排列i1i2…in，如果其中存在ij,ik，使得j<k但是ij>ik，那么就稱(chēng)(ij,ik)是這個(gè)排列的一個(gè)逆序。一個(gè)排列含有逆序的個(gè)數(shù)稱(chēng)為這個(gè)排列的逆序數(shù)。例如排列263451含有8個(gè)逆序：(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，它的逆序數(shù)就是8。顯然，由1,2,…,n構(gòu)成的所有n!個(gè)排列中，最小的逆序數(shù)是0，對(duì)應(yīng)的排列就是12…n；最大的逆序數(shù)是n(n?1)/2，對(duì)應(yīng)的排列就是n(n?1)…21。逆序數(shù)越大的排列與原始排列的差異度就越大。利用二分歸并排序算法設(shè)計(jì)一個(gè)計(jì)數(shù)給定排列逆序的分治算法，并對(duì)算法進(jìn)行時(shí)間復(fù)雜度的分析。2、有n個(gè)分別排好序的整數(shù)數(shù)組A0，A1,…,An－1，其中Ai含有xi個(gè)整數(shù)，i=0,1,…,n-1。已知這些數(shù)組順序存放在一個(gè)圓環(huán)上，現(xiàn)在要將這些數(shù)組合并成一個(gè)排好序的大數(shù)組，且每次只能把兩個(gè)在圓環(huán)上處于相鄰位置的數(shù)組合并。問(wèn)如何選擇這n-1次合并的次序以使得合并時(shí)總的比較次數(shù)達(dá)到最少。3、假設(shè)零錢(qián)系統(tǒng)的幣值是{1,p,p2,…,pn}，p>1，且每個(gè)錢(qián)幣的重量都等于1。設(shè)計(jì)一個(gè)最壞情況下時(shí)間復(fù)雜度最低的算法，使得對(duì)任何錢(qián)數(shù)y，該算法得到的零錢(qián)個(gè)數(shù)最少。說(shuō)明算法的主要設(shè)計(jì)思想，證明它的正確性，并給出最壞情況下的時(shí)間復(fù)雜度分析。4、用動(dòng)態(tài)規(guī)劃策略求解最長(zhǎng)公共子序列