第=page1*2-11頁，共=sectionpages4*28頁第=page1*22頁，共=sectionpages4*28頁南陽理工學(xué)院試卷課程：《算法分析與設(shè)計(jì)》考核方式：（閉卷）課程性質(zhì)：_______________適用對(duì)象：題號(hào)一二三四五總分復(fù)核人滿分2020202020100得分單選題：（每題2分，共20分）（說明：將認(rèn)為正確答案的字母填寫在每小題后而的括號(hào)內(nèi)）評(píng)卷人得分1．算法具有五種特性分別是輸入、輸出、()、有限性、可行性。A．魯棒性；B．二義性；C．確定性；D．兼容性；2．0-1背包問題：n=6，W=10，v(1:6)=(15,59,21,30,60,5)，w(1:6)=(1,5,2,3,6,1）。該問題的最大價(jià)值為（）。A．101；B．110；C．115；D．120；3．使用子集樹解決0-1背包問題時(shí)算法的時(shí)間復(fù)雜度為（）。A．O(m2m)；B．O(n2n)；C．O(2mn)；D．O(2nm)；4．以下關(guān)于P類問題的描述正確的是（）A．存在多項(xiàng)式時(shí)間確定性算法的問題是P類問題；B．存在多項(xiàng)式時(shí)間確定性算法的判定問題是P類問題；C．存在多項(xiàng)式時(shí)間非確定性算法的問題是P類問題；D．存在多項(xiàng)式時(shí)間非確定性算法的判定問題是P類問題；5．一個(gè)正整數(shù)n是否為素?cái)?shù)的判定方法中的描述正確的是（）；A．如果(n-1)!modn=1，則n一定是素?cái)?shù)；B．如果(n-1)!modn=-1，則n一定是素?cái)?shù)；C．如果對(duì)于區(qū)間（0，n）之間的任何一個(gè)整數(shù)a，an-1modn=1，則n一定是素?cái)?shù)。D．如果同余方程在區(qū)間（0，n）之間的解只有1和n-1，則n一定是素?cái)?shù)。6．在n皇后問題中引入隨機(jī)化算法的方法中正確的是（）；A．隨機(jī)選取棋盤上的一個(gè)位置，只要和其它皇后不沖突即可；B．隨機(jī)選擇不同斜線的位置；C．隨機(jī)選擇不同列的位置；D．隨機(jī)選擇不同行的位置；7．在P不等于NP的前提下，以下關(guān)于P、NP和NP完全問題的關(guān)系描述錯(cuò)誤的是（）A．所有的P類問題都屬于NP類問題；B．所有的NP完全問題都屬于NP類問題；C．P類問題和NP完全問題有交集；D．NP完全問題中哪怕一個(gè)問題在多項(xiàng)式時(shí)間內(nèi)能夠解決，所有的NP類問題都能在多項(xiàng)式時(shí)間內(nèi)解決；8．給定隨機(jī)化算法A和任意小的正常數(shù)，算法A找到正確解的概率為p(0<p<1)，至少運(yùn)行（）次算法A，使得算法得到正確解的概率不小于。A．；B．；C．；D．；9．約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法步驟，以下描述不正確的是（）A．找出基本變量和非基本變量；B．判斷檢驗(yàn)數(shù)C是否為整數(shù)，如果是，算法無界結(jié)束；C．選入基變量；D．選離基變量；10．以下問題中，不屬于NP完全問題的是（）A．最短路徑的判定問題；B．漢諾塔問題；C．哈密頓回路問題；D．圖的m可著色判定問題二、填空題：（每空2分，共20分）評(píng)卷人得分1．貪心法的兩個(gè)基本要素是和。2．分治法的求解分為和兩大步驟。3．回溯法中講解了樹，排列樹和樹。4．分支限界法是以或的方式進(jìn)行搜索問題的解空間樹。5．隨機(jī)化算法分為四類，包括、蒙特卡羅算法、和舍伍德算法。三、簡(jiǎn)答題：（每題5分，共20分）評(píng)卷人得分1．簡(jiǎn)述算法設(shè)計(jì)的一般過程。2．簡(jiǎn)述貪心算法的基本思想和解題步驟。3．簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法的基本要素。4．簡(jiǎn)述回溯法和分支限界法的異同。四、綜合應(yīng)用題：（每題10分，共20分）評(píng)卷人得分1．采用快速排序的思想將給定序列T[1:9]={45，23，65，57，18，2，90，12，84}由小到大排序。(要求：先描述快速排序的思想，然后寫出首次分解得到兩個(gè)子問題的過程、遞歸的結(jié)果、子問題的解合并成原問題的解的過程)2．用動(dòng)態(tài)規(guī)劃法求最優(yōu)加工順序問題：有7個(gè)工件在第一臺(tái)機(jī)器和第二臺(tái)機(jī)器上的處理時(shí)間分別為[3，8，10，12，6，9，15]，[7，2，6，18，3，10，4]。（要求：先按求解步驟分為兩個(gè)序列，然后對(duì)序列排序合并，再寫具體的求解過程，指出最優(yōu)解）五、算法分析題：（每題10分，共20分）評(píng)卷人得分1.用分支限界法設(shè)計(jì)解決0-1背包問題：重量w=[3，5，2，1]，