【文章內(nèi)容簡介】 0。 k n。 k++) scanf(%1f%1f, amp。a[k].weight, amp。a[k].value)。 maxv = find(a,n)。 for(k = 0。 k n。 k++) if(opts[k]) printf(%4d, k)。 printf(\nTotal value = %1f\n, maxv)。 } 1999年下午試題六 ? next(int i , double tw, double tv) //考慮 i號物品 { twv[i].flg = 1。 twv[i].tw = tw。 twv[i].tv = tv。 } ? look(int i, int *f, double *tw, double *tv) //取 i號物品在解中的狀態(tài)信息 { *f = twv[i].flg。 *tw = twv[i].tw。 *tv = twv[i].tv。 } ? double find (struct elem *a, int n ) { int i, k, f。 double maxv=0, tw, tv, totv= 。 for(k = 0。 k n。 k++)_(1)_。 next(0, , totv)。 i = 0。 while(i = 0) { look(i, amp。f, amp。tw, amp。tv)。 switch (f) { case 1: twv[i].flg++。 //先考慮被選中 if(_(2)_= limw) //選中可行嗎 if(in1) {//后面還有物品嗎 next(_(3)_)。 //置 i+1物品的狀態(tài) i++。} else if (tvmaxv) {//是更好的解嗎 maxv = tv。 for(k = 0。 k n。 k++) opts[k] = twv[k].flg != 0。} break。 totv += a[k].value tw + a[i].weight i+1,tw+a[i].weight,tv case 0: i。 break。 //不選，回退 default: //f == 2，曾被選中 twv[i].flg = 0。 if (_(4)_) //不選 i號物品可行嗎 if(in1) {//后面還有物品嗎 next(_(5)_)。 i++。} else {maxv = tv – a[i].value。 for(k = 0。 k n。 k++) opts[k] = twv[k].flg != 0。 i。 } break。 } } return maxv。 } tva[i].value maxv i+1,tw,tva[i].value 2022年試題 1112 ? 遞歸算法的執(zhí)行過程 ,一般來說 ,可先后分成__(11)__和 __(12)__兩個階段。 ? (11) ? (12) ? B B 2022年試題 1314 ? 若一個問題的求解既可以用遞歸算法 ,也可以用遞推算法 ,則往往用 __(13)__算法 ,因為__(14)__。 ? (13) ? (14) ? D A 2022年試題 15 ? 貪心算法是一種 ____的算法。 ? ,只求滿意 ? A。貪心算法一般可以快速得到滿意的解，因為它省去了為找到最優(yōu)解而窮盡所有可能所耗費(fèi)的大量時間。常以當(dāng)前情況為基礎(chǔ)做最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪心算法不要回溯。 2022年下午試題五 ? [程序 5說明 ]著名的四色定理指出任何平面區(qū)域圖均可用四種顏色著色 ,使相鄰區(qū)域著不同的顏色。本程序?qū)o定的區(qū)域圖找出所有可能的不超過四種顏色的著色方案。程序中用 1～ 4表示四種顏色 。要著色的 N個區(qū)域用 0～ N1編號 ,區(qū)域相鄰關(guān)系用 adj[][]矩陣表示 ,矩陣的 i行 j列的元素為 1,表示區(qū)域 i與區(qū)域 j相鄰；矩陣的 i行 j列的元素為 0,表示區(qū)域 i與區(qū)域 j不相鄰。數(shù)組 color[]用來存儲著色結(jié)果 , color[i]的值為區(qū)域 i所著顏色。 2022年下午試題五 ? include〈 〉 define N 10 void output(int color[])//輸出一種著色方案 { int i 。 for ( i = 0 。 i N 。 i++ ) printf( %4d , color[i] ) 。 printf( \n ) 。 } 2022年下午試題五 ? int back( int *ip, int color[] ) //回溯 { int c = 4 。 while ( c == 4 ){ if ( *ip = 0 ) return 0 。 //已回溯到 0號區(qū)域 (*ip) 。 c =_(1)_ 。 color[*ip] = 1 。 } return c 。//返回該區(qū)域原來的著色方案 } (1) color[*ip] 2022年下午試題五 ? //檢查區(qū)域 i 對顏色 c 的可用性 int colorOK( int i , int c , int[][N] , int color[ ] } { int j 。 for ( j = 0 。 j i 。 j++ } if ( __(2)__ ) return 0 。 return 1 。 } (2) adj[i][j] == 1 amp。amp。 color[j] == c 2022年下午試題五 ? //為區(qū)域 i選一種可著的顏色 int select( int i, int c, int adj[][N], int color[ ] ) { int k 。 for ( k = c 。 k = 4 。 k++ ) if ( colorOK( _(3)_ ) ) return k 。 return 0 。 } (3) i,k,adj,color ? int coloring( int adj[][N] ) //尋找各種著色方案 { int color[N] , i , c , t 。 for ( i = 0 。 i N 。 i++ ) color[i] = 1 。 i = c = 0 。 t = 0 。 while ( 1 ) { if ( ( c =_(4)_ ) == 0 ){c = back( amp。i , color) 。 if ( c == 0) return t 。 } else {_(5)_ 。 i++ 。 if ( i == N ) {output(color) 。 ++t。 c = back( amp。i , color ) 。 } else c = 0 。 } } } (4) select (i,c+1,adj,color) (5) color[i]=c 2022年下午試題五 ? void main() { int adj[N][N] = { {0,1,0,1,1,1,1,1,1,1}, {1,0,1,1,0,1,1,1,1,0}, {0,1,0,1,0,1,1,0,1,1}, {1,1,1,0,1,1,0,0,1,1}, {1,0,0,1,0,1,0,0,0,0}, {1,1,1,1,1,0,1,0,0,1}, {1,1,1,0,0,1,0,0,1,0}, {1,1,0,0,0,0,0,0,1,1}, {1,1,1,1,0,0,1,1,0,1}, {1,0,1,1,0,1,0,1,1,0} }。 printf( 共有 %d組解 .\n,coloring( adj ) ) 。 } 2022年試題 11 ? 算法是對問題求解過程的一類精確描述，算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本操作在限定時間內(nèi)執(zhí)行有限次來實現(xiàn)的，這說明算法具有 _11_特性。 ? A. 正確性 B. 確定性 C. 能行性 D. 健壯性 ? C 附：算法的性質(zhì) 1. 有窮性：一個算法必須保證在 有限 個操作步驟執(zhí)行后終止。一般指操作步驟或完成操作的時間在 合理 的范圍內(nèi) 2. 確定性：算法中每個步驟含義明確，無二義性。 3. 可行性：算法中描述的操作都可通過有限次的基本運(yùn)算來實現(xiàn) 4. 輸入：一個算法應(yīng)具有零個或多個輸入。 5. 輸出：一個算法應(yīng)具有一個或多個輸出。 2022年試題 12 ? 快速排序算法采用的設(shè)計方法是 ____。 ? A. 動態(tài)規(guī)劃法 (Dynamic Programming) B. 分治法 (Divide and Conquer) C. 回溯法 (Backtracking) D. 分枝定界法 (Branch and Bound) ? B 2022年試題 1314 ? 在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼算法可以用來構(gòu)造具有 ____的二叉樹，這是一種采用了 ____的算法。 ? A. 前綴碼 B. 最優(yōu)前綴碼 C. 后綴碼 D. 最優(yōu)后綴碼 ? A. 貪心 B. 分治 C. 遞推 D. 回溯 ? B A 2022年試題 17 ? 下述函數(shù)中漸進(jìn)時間最小的是 __(17)__ 。 ? 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é)果：快速排序（選第一個記錄為基準(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年下午試題五 ? 程序說明： “ 背包問題 ” 的基本描述是：有一個背包，能盛放的物品總重量為 S，設(shè)有 N件物品，其重量分別為 w1， w2， ...， wn，希望從 N件物品中選擇若干件物品，所選物品的重量之和恰能放入該背包，即所選物品的重量之和等于 S。 如下程序均能求得 “ 背包問題 ” 的一組解，其中程序 “ 背包問題 ” 的遞歸解法，而程序 “ 背包問題 ” 的非遞歸解法。 2022年下午試題五 ? include define N 7 define S 15 int w[N+1] = {0， 1， 4， 3， 4， 5， 2， 7}； typedef struct {int s； //背包剩余容量 int n。 //物品的下標(biāo) int job； //物品當(dāng)前狀態(tài) } KNAPTP； ? 程序中用棧來保存已考查過的物品。結(jié)構(gòu)KNAPTP表示經(jīng)過考查的物品 2022年下午試題五 ? int knap ( int s， int n) //遞歸算法