【正文】 改等操作都需由數(shù)據(jù)庫管理員進(jìn)行完整性定義和安全性授權(quán)，由數(shù)據(jù)庫系統(tǒng)具體執(zhí)行。 1997年上午題第 5題 ? 答案 :3 5 6 7 9 1997年下午試題八 ? [程序說明 ]一個(gè)相連的區(qū)域被不規(guī)則地分割成 n 個(gè)不同的小區(qū)域；每個(gè)小區(qū)域與若干其它小區(qū)域相鄰接?，F(xiàn)用 種不同顏色為該區(qū)域著色，要求每個(gè)小區(qū)域著同一種顏色，相鄰小區(qū)域著不同顏色。 ? 設(shè)小區(qū)域被順序編號(hào)為 0， 1， … ， n1。每個(gè)小區(qū)域與其它小區(qū)域的鄰接關(guān)系用兩維數(shù)組 bordering 表示，元素 bordering[i][j] 表示 i 號(hào)小區(qū)域與 j 號(hào)小區(qū)域之間的鄰接關(guān)系： 0： j 小區(qū)域與 i 小區(qū)域不鄰接 1： j 小區(qū)域與 i 小區(qū)域相鄰接 1997年下午試題八 ? 程序中，把計(jì)算結(jié)果存入于兩維數(shù)組 colored 中，顏色編號(hào)為 0,1,… ,1,元素 colored[coler][j] 的含義是 :0： j 小區(qū)域不用顏色 color 著色 1： j 小區(qū)域用顏色 color 著色 ? 函數(shù) colorcountry(bordering,colored,n,) 根據(jù)所給的小區(qū)域鄰接關(guān)系數(shù)組 bordering、小區(qū)域個(gè)數(shù) n 、顏色數(shù) ，將找到的著色方案記錄在數(shù)組 colored 中。函數(shù)采用試探法找解。首先從第一個(gè)小區(qū)域著第一種顏色開始順序?yàn)楦餍^(qū)域找著色方案。對(duì)某個(gè)小區(qū)域，當(dāng)為它找到一種未被它的相鄰小區(qū)域著色的顏色時(shí)，就用該顏色對(duì)該小區(qū)域著色，并準(zhǔn)備處理下一個(gè)小區(qū)域。當(dāng)不能為某個(gè)小區(qū)域找到一個(gè)未被它的相鄰小區(qū)域著色的顏色時(shí)，就回溯。如最終為全部小區(qū)域找到著色方案，函數(shù)返回 1；否則，函數(shù)返回 0。 ? 程序假定小區(qū)域個(gè)數(shù)不超過 20，顏色數(shù)為 4。 ? include define n 20 define CN 4 ? int colorcountry(int bordering[][N], int colored[][N], int n,int ) { int color,used,i,c。 for(color = 0。 color 。 color++) //設(shè)置所有區(qū)域均未著色 for(i = 0。i n。 i++) colored[color][i] = 0。 c = 0。 //從第 1個(gè)小區(qū)域開始 color = 0。 //從著第 1種顏色開始試探 while (c n) { //還未對(duì)全部小區(qū)域著色時(shí)循環(huán) while(___(1)___)//順序?qū)γ糠N顏色作試探 {//檢查當(dāng)前顏色是否已被某相鄰小區(qū)域著色 for (i = 0, used = 0。 !used amp。amp。 ic。 i++) { if(____(2)____) used = 1。 if (!used) break。 //當(dāng)前顏色未被相鄰小區(qū)域著色 color++。} if (!used) //找到一種可用顏色，用此色著色，并準(zhǔn)備處理下一個(gè)小區(qū)域 {____(3)____ = 1。 color = 0。} else{ //未找到一種可用顏色，回溯 c。 if (c 0) return 0。 //發(fā)現(xiàn)沒有解的情況 for(color = 0。 ____(4)____。 color++) ____(5)____ = 0。 } } return 1。 } ? print(int colored[][N],int n,int ) //輸出結(jié)果 { char *colortbl[] = {“RED”,”BLUE”,”GREEN”,”YELLOW”}。 int color,i。 for(color = 0。 color 。 color++) { printf(“\n%s。\n”,colortb1[color])。 for(i = 0。in。 i++) if (colored[color][i]) printf(“\t%d”,i)。 printf(“\n”)。 } } ? int colored[CN][N],bordering[N][N]。 main() { int c,i,j,n。 printf(“Enter number of areas.”)。 scanf(“%d”,amp。n)。 printf(“Enter bordering:\n”)。 for (i = 0。i n。 i++) for (j = 0。j n。 j++) bordering[i][j] = 0 for(i = 0。i n。 i++) { printf(“Enter areas to link %d area(0 to next).\n”,i)。 scanf(“amp。d”,amp。j)。 while (j = 0) { if(i != j) bordering[i][j] = bordering[j][i] = 1。 scanf(“%d”,amp。j)。 } } if(colorcountry(bordering,colored,n,CN)) print(colored,n,CN)。 else printf(“No Solution.\n”)。 } ? （ 1）（ 3分） color 答 color 4 給 3 分；答 color = 給 2 分。 ? （ 2）（ 3分） bordering[c][i] amp。amp。 colored[color][i] 答 bordering[c][i] == 1 amp。amp。 colored[color][i] == 1 給 3 分。 答 bordering[c][i] * colored[color] [i] == 1 給 3 分，而將其中相等運(yùn)算符 “ ==”寫成賦值運(yùn)算符“ =”時(shí)，只給 1 分。其中 bordering[c][i] 可寫成 bordering[i][c]。 ‘ amp。amp。’左右只對(duì)一半給 2 分。 ? （ 3）（ 3分） colored[color][c++] 答 colored[color][c] 給 2 分。 答 colored[color][… ] 給 1 分。 答 c++ 給 1 分。 ? （ 4）（ 3分） colored[color][c] == 0 或 ! colored[color][c] 或 colored[color][c] !== 1 ? （ 5）（ 3分） colored[color ++][c] 答 colored[color][c] 給 2 分。 答 colored[color][… ] 給 1 分。 1998年下午試題七 ? [程序說明 ]本程序的函數(shù) sum(int i,int total， int sigma， int rear， int d[]， int n)用來從已知數(shù)組d的前 n個(gè)元素中找出所有部分元素序列之和等于total的元素序列，約定數(shù)組 d的元素都是正整數(shù)，且都小于等于 total。 ? 函數(shù) sum使用遞歸方法找出全部解答。參數(shù) i表示遞歸函數(shù)當(dāng)前考慮元素 d[i]，參數(shù) sigma是調(diào)用前已選取的部分序列的元素和 ，參數(shù) rear是后面還未考慮的那部分元素的元素和 。函數(shù)對(duì)元素 d[i] 有兩種可能的選擇方案： 1998年下午試題七 ? 1．考慮元素 d[i]被包含在新的部分元素序列中的可能性。如果在當(dāng)前部分元素序列之后接上 d[i]，新序列的元素和不超過 total，則函數(shù)將 d[i]包含在當(dāng)前部分元素序列中。如果新的部分元素序列的元素和等于 total時(shí)，新的部分元素序列就是一個(gè)解答，函數(shù)將其輸出；否則，若繼續(xù)考慮后面的元素還有可能找到解答時(shí)，函數(shù)就遞歸去考慮后面的元素，尋找解答。最后，函數(shù)應(yīng)恢復(fù)原來部分元素序列中不包含 d[i]的狀態(tài)。 ? 2．考慮元素 d[i]不被包含在新的部分元素序列中的可能性。如果繼續(xù)向 d[i]之后考慮還是有希望能得到和為 total的部分元素序列時(shí)，函數(shù)將新序列不包含 d[i]也作為一種可能的選擇，并遞歸去考慮后面的元素，尋找解答。 1998年下午試題七 ? ＃ include 〈 〉 ＃ define N 100 int a[N]。 int flg[N]。 1998年下午試題七 ? main() { int i， j， n， total， s， d。 printf(“輸入 total！ /n”)。 scanf(“%d”,amp。total)。 printf(“輸入 n！ /n”)。 scanf(“%d”,amp。n)。 for (s = i = 0。 i＜ n。) { printf (“輸入第 %d個(gè)元素 0且 =%d)\n”， i+1，total}。 scanf (“%d”， amp。d)。 if( d 1 || d total) { printf(“出錯(cuò)，請重新輸入！ \n”)。 continue； } s += a[i++] = d。 } sum(0， total， 0,__(5)__， a， n)。 printf (\n\n)。 } s ? sum (int i,int total,int sigma,int rear,int d[],int t) { int j。 //考慮 d[i]被包含在新的部分元素序列中的可能性 if (sigma + d[i] = total) ｛ flg[i] = 1。 //d[i]被考慮在被部分元素序列中 if(__(1)__ == total) // 輸出解 { for (j = 0。 flg[j] == 0。 j++)。 printf(“%4d = %d”， total， d[j])。 for(j++。 j = i。 j++) if (flg[j]) printf(“+%d”,d[j])。 printf(“\”)。 } else //考慮后面的元素有可能找到解答時(shí) if(in1 amp。amp。 rear+sigma = total) sum(i+1,total,_(2)_,reard[i],d,n)。 __(3)__。 } sigma + d[i] sigma + d[i] flg[i]=0 1998年下午試題七 //考慮元素 d[i]不被包含在新的部分元素序列中的可能性 if (in1 amp。amp。 reard[i]+sigma = total) sum(i+1,total,__(4)__,reard[i],d,n)。 } sigma 1999年下午試題六 ? 【 程序 6說明 】 本程序從 n種不同重量、不同價(jià)值的物品中選取一部分物品。要求在不超過限定重量 limw的前提下，使被選取的那些物品的總價(jià)值較大。這里約定 limw不超過 n種物品的重量總和，也沒有一種物品的重量超過 limw，并且各物品的價(jià)值都大于 0。程序中， n種物品被順序編號(hào)為 0..n1。 1999年下午試題六 ? include define N 100 double limw。 int opts[N]。 //存儲(chǔ)臨時(shí)最佳的選擇方案 struct elem { double weight。double value。 } a[N]。 //物品的重量和價(jià)值信息 int k, n。 struct { int flg。 //物品的考慮狀態(tài)： 0不選， 1將被考慮， 2曾被選中 double tw。 // 已達(dá)到的總重量 double tv。 // 期望的總價(jià)值 ｝ twv[N]。 // 當(dāng)前候選解中各物品的考慮狀態(tài)，以及候選解的狀態(tài) 1999年下午試題六 ? main() { double maxv, find()。 printf(Enter number of matter. )。 scanf(%d, amp。n)。 printf(Enter limit of weight. )。 scanf(%1f, amp。limw)。 printf(Enter weight amp。amp。 values of matters.)。 for (k =