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

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

在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。

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