【正文】 nt colored[CN][N],bordering[N][N]。n)。 i++) for (j = 0。 i++) { printf(“Enter areas to link %d area(0 to next).\n”,i)。 while (j = 0) { if(i != j) bordering[i][j] = bordering[j][i] = 1。 else printf(“No Solution.\n”)。 colored[color][i] 答 bordering[c][i] == 1 amp。其中 bordering[c][i] 可寫成 bordering[i][c]。 ? （ 3）（ 3分） colored[color][c++] 答 colored[color][c] 給 2 分。 答 colored[color][… ] 給 1 分。函數(shù)對元素 d[i] 有兩種可能的選擇方案： 1998年下午試題七 ? 1．考慮元素 d[i]被包含在新的部分元素序列中的可能性。 ? 2．考慮元素 d[i]不被包含在新的部分元素序列中的可能性。 1998年下午試題七 ? main() { int i， j， n， total， s， d。 printf(“輸入 n！ /n”)。 i＜ n。 if( d 1 || d total) { printf(“出錯(cuò)，請重新輸入！ \n”)。 } s ? sum (int i,int total,int sigma,int rear,int d[],int t) { int j。 j++)。 j++) if (flg[j]) printf(“+%d”,d[j])。 rear+sigma = total) sum(i+1,total,_(2)_,reard[i],d,n)。 reard[i]+sigma = total) sum(i+1,total,__(4)__,reard[i],d,n)。程序中， n種物品被順序編號為 0..n1。double value。 //物品的考慮狀態(tài)： 0不選， 1將被考慮， 2曾被選中 double tw。 printf(Enter number of matter. )。 scanf(%1f, amp。 values of matters.)。a[k].weight, amp。 k n。 twv[i].tw = tw。 *tv = twv[i].tv。 k n。 while(i = 0) { look(i, amp。 switch (f) { case 1: twv[i].flg++。 for(k = 0。 totv += a[k].value tw + a[i].weight i+1,tw+a[i].weight,tv case 0: i。 i++。 k++) opts[k] = twv[k].flg != 0。 } tva[i].value maxv i+1,tw,tva[i].value 2022年試題 1112 ? 遞歸算法的執(zhí)行過程 ,一般來說 ,可先后分成__(11)__和 __(12)__兩個(gè)階段。貪心算法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎业阶顑?yōu)解而窮盡所有可能所耗費(fèi)的大量時(shí)間。程序中用 1～ 4表示四種顏色 。 for ( i = 0 。 } 2022年下午試題五 ? int back( int *ip, int color[] ) //回溯 { int c = 4 。 color[*ip] = 1 。 j i 。amp。 k++ ) if ( colorOK( _(3)_ ) ) return k 。 i N 。 while ( 1 ) { if ( ( c =_(4)_ ) == 0 ){c = back( amp。 i++ 。i , color ) 。 } 2022年試題 11 ? 算法是對問題求解過程的一類精確描述，算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本操作在限定時(shí)間內(nèi)執(zhí)行有限次來實(shí)現(xiàn)的，這說明算法具有 _11_特性。 5. 輸出：一個(gè)算法應(yīng)具有一個(gè)或多個(gè)輸出。 ? A. T1(n) = nlog2n + 100log2n B. T2(n) = 2nlog2n 100log2n C. T3(n) = n2 100log2n D. T4(n) = 4nlog2n 100log2n ? A 先考慮最高階，再考慮相同階的系數(shù) 2022年試題 1 21 ? 對于給定的一組關(guān)鍵字（ 12， 2， 16， 30， 8， 28， 4， 10， 20， 6， 18），按照下列算法進(jìn)行遞增排序，寫出每種算法第一趟排序后得到的結(jié)果：快速排序（選第一個(gè)記錄為基準(zhǔn)元素）得到 __(19)__，二路歸并排序得到__(21)__， ? (19) A. 10,6,18,8,4,2,12,20,16,30,28 ? B. 4,2,6,10,8,12,28,30,20,16,18 C. 2,4,6,8,10,12,16,18,20,28,30 ? D. 6,10,8,28,20,18,2,4,12,30,16 (21) A. 2,12,16,8,28,30,4,6,10,18,20 ? B. 2,12,16,30,8,28,4,10,6,20,18 C. 12,2,16,8,28,30,4,6,10,28,18 ? D. 12,20,6,18,4,16,30,8,28 ? 答案： 19： B 21： B 2022年下午試題五 ? 程序說明： “ 背包問題 ” 的基本描述是：有一個(gè)背包，能盛放的物品總重量為 S，設(shè)有 N件物品，其重量分別為 w1， w2， ...， wn，希望從 N件物品中選擇若干件物品，所選物品的重量之和恰能放入該背包，即所選物品的重量之和等于 S。結(jié)構(gòu)KNAPTP表示經(jīng)過考查的物品 2022年下午試題五 ? int knap ( int s， int n) //遞歸算法 {if ( s== 0) return 1； if ( s0 || ( s0 amp。 rep ) { if( ==0 ) k = 1； //已求得一組解 else if ( 0 || =0 ) rep = 0； else { =_(4)_； =1； __(5)__ = x； } } (4) w[] (5) stack[++top] if ( !k ) {rep = 1； while ( top = 1 amp。 !k 2022年下午試題五 ? main() { if ( knap(S， N) ) printf( “OK!\n” )； else printf( “NO!\n” )； } 2022年試題 9 ? 將兩個(gè)長度為 n的遞增有序表歸并成一個(gè)長度為 2n的遞增有序表，最少需要進(jìn)行關(guān)鍵字比較 __(9)__次。 void sam() { int n=2。 ? ? C ? 概率算法允許算法在執(zhí)行過程中可隨機(jī)地選擇下一個(gè)計(jì)算步驟。 ? ? B 2022年 11月試題 5758 ? 在下列算法設(shè)計(jì)方法中， __(57)__在求解問題的過程中并不從整體最優(yōu)上加以考慮，而是做出在當(dāng)前看來是最好的選擇。 ? ? ? A A 2022年 5月試題 5354 ? 為在狀態(tài)空間樹中 _(53)_，可以利用 LC檢索（ Least Cost Search）快速找到一個(gè)答案結(jié)點(diǎn)。 ? (i， j)=Dk1(i， j)+C(i， j) (i， j)=min{Dk1(i， j)， Dk1(i， j)+C(i， j)} (i， j)=Dk1(i， k)+Dk1(k， j) (i， j)=min{Dk1(i， j)， Dk1(i， k)+Dk1(k， j)} ? D 2022年 5月 下午試題四 ? [說明 ]假設(shè)需要將 N個(gè)任務(wù)分配給 N個(gè)工人同時(shí)去完成，每個(gè)人都能承擔(dān)這 N個(gè)任務(wù)，但費(fèi)用不同。 2022年 5月下午試題四 ? include define N 8 //N表示任務(wù)數(shù)和工人數(shù) int c[N][N]。 if (__(1)__amp。iN。 i ++ ) //分配任務(wù) k if ( worker[i]==0 amp。 plan(_(4)_,cost + c [ k ] [ i ])。 for(i = 0。 temp [ i ] = 0。c[ i ] [ j ])。 i N。 ? A. T(n)=T(n1)+1 B. T(n)=2T(n1) C. T(n)=2T(n1)+1 D. T(n)=2T(n+1)+1 ? F(int n){ if n==1 Move(1)。 } } C B 2022年 11月試題 5556 ? 利用貪心法求解背包問題時(shí)， _（ 55） ___能夠確保獲得最優(yōu)解。 ? A．分治法 B．貪心法 C．動(dòng)態(tài)規(guī)劃方法 D．分支 限界 ? A． 3 B． 4 C． 5 D． 6 ? C D 2022年 5月試題 59 ? 設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式 T(n)=2T(n/2)+n表示，則該算法的時(shí)間復(fù)雜度為 （ 59） 。 ? (59)A. 希爾排序 B. 直接插入排序 C. 快速排序 D. 堆排序 ? (60)A. 冒泡排序 B. 插入排序 C. 快速排序 D. 堆排序 ? D C 2022年 11月下午試題四 ? 閱讀以下說明和圖，填補(bǔ)流程圖中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。 ? (2) 每條裝配線有 n 個(gè)工位，第一條裝配線的工位為 S0,0, S0,1, … , S0,n1, 第二條裝 配線的工位為 S1,0, S1,1, … , S1,n1。 ? (5) x0 和 x1 表示裝配結(jié)束后，汽車分別從裝配線 0 和裝配線 1 下線所需要的時(shí)間。 算法中使用的 f[i][j]表示從開始點(diǎn)到 Si,j 處的最短裝配時(shí)間。以上的找零錢方法采用了 （ 62）策略。現(xiàn)采用貪心策略實(shí)現(xiàn)用盡可能少的基站覆蓋所有的房子。 ? A. 貪心 B. 分而治之 C. 動(dòng)態(tài)規(guī)劃 D. 試探＋回溯 ? A 2022年 11月試題 64 ? 關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系， （ 64） 是正確的。圖 41是基于貪心策略求解該問題的流程圖。 jobi能插入數(shù)組 J的 充要條件 是： jobi和數(shù)組 J中已有作業(yè)均能在其期限之內(nèi)完成。 k = 1i = 2( 1 ) r = k ( 2 ) amp。 d [ i ] r ?q = kq = r + 1 ?J [ q + 1 ] = J [ q ] 。 5 220 2022年 11月下午試題四 2022年 11月下午試題四 ? 【 問題 3】 (2分 ) 對于本題的作業(yè)處理問題，用圖 41的貪心算法策略，能否求得最高收益？ (6) 。 ? （ 63） A. 5 B. 6 C. 7 D. 8 ? （ 64） ? C B 2022年 5月試題下午試題四 ? 說明：快速排序是一種典型的分治算法。 2. 遞歸求解：通過遞歸的調(diào)用快速排序，對子數(shù)組 A[p..q1]和 A[q+1..r]分別排序。下標(biāo)小于或等于 i的元素的值小于或等于樞軸元素的值 j：循環(huán)控制變量，表示數(shù)組元素下標(biāo) 2022年 5月試題下午試題四 ? QUICKSORT(A, p, r){ if (p r){ q = PARTITION(A,p,r) 。 i = p – 1。 交換 A[i]和 A[j] } } 交換 （ 1） 和 （ 2） //（ 1）和（ 2）答案可互換，但兩空全部答對方可