湖北工業(yè)大學(xué)在職研究生《算法分析試題及答案》

湖北工業(yè)大學(xué)2014年在職攻讀碩士學(xué)位課程考試（考查）試題考試（考查）科目算法分析與設(shè)計(jì)學(xué)位類(lèi)別工程碩士說(shuō)明：1.試題版面為標(biāo)準(zhǔn)A4，各題標(biāo)題字號(hào)為黑體5號(hào)字，題干字號(hào)為標(biāo)準(zhǔn)宋體5號(hào)字2.答案必須寫(xiě)在答題紙上，寫(xiě)在試卷上無(wú)效。分治法有那幾個(gè)步驟組成？（10分）給出貪婪法的設(shè)計(jì)方法描述。（10分）請(qǐng)畫(huà)出四皇后問(wèn)題的搜索樹(shù)。（10分）請(qǐng)描述分支與限界法的基本思想。（10分）隨機(jī)算法有哪些類(lèi)型？（10分）給出如下算法，請(qǐng)分析時(shí)間復(fù)雜度。（10分）1.Typegame(Typegroup[],intn)2.{3.intj,i=n;4.while(i>1){5.i=i/2;6.for(j=0;j<i;j++)7.if(comp(group[j+i],group[j]);8.group[j]=group[j+i];9.}10.returngroup[0];11.}請(qǐng)畫(huà)出5、8、4、9、3、6、7、2等數(shù)據(jù)采用快速排序算法的執(zhí)行過(guò)程。（10分）請(qǐng)畫(huà)出下圖的克魯斯卡爾算法執(zhí)行過(guò)程。（10分）請(qǐng)給出搜索過(guò)程中可能生成的結(jié)點(diǎn)數(shù)的估計(jì)算法。（10分）解向量的第個(gè)分量的取值范圍為有限集；cons(node,x)判斷結(jié)點(diǎn)的兒子結(jié)點(diǎn)是否滿足約束條件，若滿足為真，否則為假；表達(dá)式：表示在結(jié)點(diǎn)下滿足約束條件的第個(gè)分量的取值集合；sizeof(T)求取集合的元素個(gè)數(shù)；choose(T)從集合T中隨機(jī)地選取一個(gè)元素。估計(jì)回溯法在搜索過(guò)程中所生成的結(jié)點(diǎn)總數(shù)。請(qǐng)給出求取整數(shù)因子的Pollard算法。（10分）輸入：整數(shù)n輸出：整數(shù)n的因子考試（考查）科目算法分析與設(shè)計(jì)分治法有那幾個(gè)步驟組成？（10分）分治法在每一層遞歸上都有三個(gè)步驟：分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。給出貪婪法的設(shè)計(jì)方法描述。（10分）貪婪法的基本思路：從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法，一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以不要回溯。實(shí)現(xiàn)該算法的過(guò)程：從問(wèn)題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個(gè)解元素；由所有解元素組合成問(wèn)題的一個(gè)可行解；請(qǐng)畫(huà)出四皇后問(wèn)題的搜索樹(shù)。（10分）88292419133565145403561250341816558606349535514162036322225302759575452484643413864624691123262831333739424447571012151721x1=1x1=4x1=2x1=3234134124123342423341413241412231312434232434131424121323121請(qǐng)描述分支與限界法的基本思想。（10分）分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。

在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(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)被加入活結(jié)點(diǎn)表中。

此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。其基本思想：在問(wèn)題的邊帶權(quán)的解空間樹(shù)中進(jìn)行廣度優(yōu)先搜索，找一個(gè)回答結(jié)點(diǎn)使其對(duì)應(yīng)路徑的權(quán)最?。ㄗ畲螅?。當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性擴(kuò)展它的所有兒子，將那些滿足約束條件且最小耗費(fèi)函<=目標(biāo)函數(shù)限界的兒子，插入活動(dòng)結(jié)點(diǎn)表中，再?gòu)幕顒?dòng)結(jié)點(diǎn)表中取下一結(jié)點(diǎn)同樣擴(kuò)展。直到找到所需的解或活動(dòng)結(jié)點(diǎn)表為空為止。隨機(jī)算法有哪些類(lèi)型？（10分）Sherwood算法：確定型算法在最壞情況下的時(shí)間復(fù)雜度與其在平均情況下的時(shí)間復(fù)雜度有較大差異；引入隨機(jī)性來(lái)消除或減少問(wèn)題好壞實(shí)例之間的這種差別；精髓不是避免算法的最壞情況發(fā)生，而是設(shè)法消除這種最壞情形行為與特定實(shí)例之間的關(guān)聯(lián)性.LasVegas算法：對(duì)于找不到有效算法的某些問(wèn)題，可使用LasVegas算法來(lái)求解，可能會(huì)很快找到問(wèn)題的一個(gè)解；一旦得到問(wèn)題的一個(gè)解，一定是正確的。但是，這種算法所作隨機(jī)性決策可能導(dǎo)致找不到解；可通過(guò)多次調(diào)用同一LasVegas算法來(lái)增加得到問(wèn)題解的概率。MonteCarlo算法：確定性算法還是隨機(jī)算法都無(wú)法保證每次得到正確的解；MonteCarlo算法以高概率給出正確解通常無(wú)法判定一個(gè)具體解是否正確；可通過(guò)重復(fù)調(diào)用同一個(gè)MonteCarlo算法多次來(lái)提高獲得正確解的概率。給出如下算法，請(qǐng)分析時(shí)間復(fù)雜度。（10分）1.Typegame(Typegroup[],intn)2.{3.intj,i=n;4.while(i>1){5.i=i/2;6.for(j=0;j<i;j++)7.if(comp(group[j+i],group[j]);8.group[j]=group[j+i];9.}10.returngroup[0];11.}請(qǐng)畫(huà)出5、8、4、9、3、6、7、2等數(shù)據(jù)采用快速排序算法的執(zhí)行過(guò)程。（10分）請(qǐng)畫(huà)出下圖的克魯斯卡爾算法執(zhí)行過(guò)程。（10分）請(qǐng)給出搜索過(guò)程中可能生成的結(jié)點(diǎn)數(shù)的估計(jì)算法。（10分）解向量的第個(gè)分量的取值范圍為有限集；cons(node,x)判斷結(jié)點(diǎn)的兒子結(jié)點(diǎn)是否滿足約束條件，若滿足為真，否則為假；表達(dá)式：表示在結(jié)點(diǎn)下滿足約束條件的第個(gè)分量的取值集合；sizeof(T)求取集合的元素個(gè)數(shù)；choose(T)從集合T中隨機(jī)地選取一個(gè)元素。估計(jì)回溯法在搜索過(guò)程中所生成的結(jié)點(diǎn)總數(shù)。IntEstimate(STypex){intk=0,m=1,r=1;do{SetType;If(!sizeof(T))Returnm;R=r*sizeof(T);m=m+r;xi=choose(T);i++;}while(1);}請(qǐng)給出求取整數(shù)因子的Pollard算法。（10分）輸入：整數(shù)n輸出：整數(shù)n的因子(defunfactorial(n);;;階乘

(setfm1)

(loopforifrom1tondo

(setfm(*mi)))

m)(defunexpmod(baseexpmodulo)

;;;冪取模

(if(=exp0)

1

(if(evenpexp)

(mod(expt(expmodbase(/exp2)modulo)2)modulo)

(mod(*base(expmodbase(-exp1)modulo))modulo))))

(defunpolla