【字體：大 小】1997年高級程序員下午試題及答案

1997年高級程序員下午試題及答案

spks.exam8.com　來源：考試吧（m.1glr.cn）　更新：2005-4-13 0:38:00　軟件水平考試　考試論壇

試題五

     閱讀以下程序說明和 FORTRAN 程序，將應(yīng)填入__(n)__處的字句，寫在答卷的對應(yīng)欄內(nèi)。

    [程序說明]

    對稱矩陣通常只需存儲其下三角部分，例如，下列對稱矩陣

|	1	2	3	4	|
|	2	5	6	7	|
|	3	6	8	9	|
|	4	7	9	11	|

    可用一維數(shù)組（1，2，3，4，5，6，7，8，9，10）存儲其下三角部分。N 階對稱矩陣下三角部分的元素個數(shù)為 ( N * N + N ) / 2 。 本子程序用來計算 N 階對稱矩陣 A 的平方 B，B 也是一個 N 階對稱矩陣。程序中 X，Y 是分別存入 A，B 下三角部分的一維數(shù)組。

    [程序] S
    UBROUTINE P（X，Y，N） INTEGER X（N*N+N）/2，Y（N*N+N）/2），S M=1 DO 10 JJ=__(1)__   DO 10 II =__(2)__     I=II     J=JJ     L=__(3)__     S=0     DO 30 K=1,N       S=S+X(I)*X(J)       IF(____(4)____) THEN         I=I+L       ELSE         I=I+1       ENDIF       IF(____(5)____) THEN         J=J+L       ELSE         J=J+1       ENDIF       L=L-1 30    CONTINUE    Y(M)-S    M=M+1 10 CONTINUE END

試題六

    閱讀以下程序說明和 C 程序，將應(yīng)填入__(n)__ 處的字句，寫在答卷的對應(yīng)欄內(nèi)。

    [程序說明]

    某系統(tǒng)由 n 個部件組成，這些部件被物理地分成若干個分離的部件組。同一組內(nèi)的兩件部件 i 和 j，它們或直接相連，或間接相連（部件 i 和部件 j 間接相連是指在這兩件部件之間有一個部件相連序列，其中部件 i 和 j 分別與這相連序列中的某個部件直接相連）。系統(tǒng)的 n 個部件被統(tǒng)一編號為 0，1，…，n-1。本程序輸入所有直接相連的部件號對，分別求出系統(tǒng)各分離部件組中的部件號并輸出。 程序根據(jù)輸入的直接相連的兩件部件號，建立 n 個鏈表，其中第 i 個鏈表的首指針為 s[i]，其結(jié)點是與部件 i 直接相連的所有部件號。 程序依次處理各鏈表。在處理 s[i] 鏈表中，用 top 工作鏈表重新構(gòu)造 s[i] 鏈表，使 s[i] 鏈表對應(yīng)系統(tǒng)中的一個部件組，其中結(jié)點按部件號從小到大連結(jié)。

    [程序]

     # include #define N 100 typeef struct node{ int data;   struct node *link; } NODE; NODE * s[N]; int i,j,n,t; NODE *q,*p,*x,*y,*top; main() { printf(“Enter number of parts.”); scanf(“%d”,&n); for(i=0; i<n; i++) printf(“Enter pairs.\n”); white (scanf(“%d%d”,&i,&j) == 2) { /*輸入相連部件對，生成相連部件結(jié)點鏈表*/ p = (NODE *)malloc(sizeof(NODE)); p->data = j; p->link = s[i]; s[i] = p; p = (NODE *)malloc(sizeof(NODE)); P->data = i; p->link = s[j]; s[j] = p; } for(i = 0;i < n; i++)  /* 順序處理各鏈表 */ for(top = s[i],____(1)____;top != NULL;) { /*將第 i 鏈表移入top工作鏈表，并順序處理工作鏈表的各結(jié)點*/ q = top; ____(2)____; if (s[j = q->data] != NULL) { /將 j 鏈表也移入工作鏈表*/ for(p = s[j]; p->link != NULL; p = p->link); p->link = top; top = s[j];____(3)____; } /* 在重新生成的第 i 鏈表中尋找當(dāng)前結(jié)點的插入點 */ for(y = s[i]; ____(4)____; x = y,y = y->link); if(y != NULL && y->data == q->data) free(q);/*因重新生成的第i鏈表已有當(dāng)前結(jié)點，當(dāng)前結(jié)點刪除* / else { /* 當(dāng)前結(jié)點插入重新生成的i鏈表*/ ____(5)____； if(y == s[i]) s[i] = q; else x->link = q; } } for(i = 0;i < n; i++) { /* 輸出結(jié)果 */ if (s[i] == NULL) continue; for(p = s[i]; p != NULL;) { printf(“\t%d”,p->data); q = p->link; free(p); p = q; } printf(“\n”); } }


試題七

    閱讀以下程序說明和 FORTRAN 程序，將應(yīng)填入__(n)__處的字句，寫在答卷的對應(yīng)欄內(nèi)。

    [程序說明]

    本子程序?qū)崿F(xiàn)地圖的著鈀。在地圖上，一個國家所著的顏色必須與所有相鄰的國家所著的顏色不同。現(xiàn)已證明，僅需四種不同的顏色就能解決地圖的著色 若地圖上有 N 個國家，分別用 1 至 N 編號。子程序中用數(shù)組 INDEX（N，2）和 BORDER（M）存放 N個國家的相鄰情況。INDEX（I，1）和 INDEX（I，2）分別表示與第 I 國相鄰的國家編號在數(shù)組 BORDER中 的起始位置和終止位置，即這些鄰國的編號存放在 BORDER（INDEX（I，1））至 BORDER（INDEX（I，2））中。

    例如，對應(yīng)于圖 1 所示的地圖，數(shù)級 INDEX 和 BORDER 具有如下值：

| 1 4 | | 5 6 | INDEX= | 7 10 | | 11 13 | | 14 16 | 　 BORDER =（2，3，4，5，1，3，1，2，4，5，1，3，5，1，3，4）

　 子程序中分別用 1，2，3，4 代表四種不同顏色，著色結(jié)果存放在數(shù)組 COLOR 中，即數(shù)組元素 COLOR(I)的值為第 I 個國家所著的顏色。 子程序采用試控法找解。首先從第 I 個國家著第一種顏色開始，順序為各個國家尋找著色方案。對第  I 個國家，當(dāng)為它找到一種未被它的相鄰國家著色的顏色時，就用該顏色對此國家著色，并準(zhǔn)備處理下一國家；當(dāng)不能為它找到一個未被它的相鄰國家著色的顏色時，就回溯——即改變第 I-1 個國家的著色方案。直至最終為全部國家找到著色方案。

    [程序]

    SUBROUTINE P(INDEX，BORDER，COLOR，N，M) INTEGER INDEX(N，2)，BORDER(M)，COLOR(N) DO 10 I=1，N 10    COLOR(I)=0 I=1 40    IF（__(1)__）THEN K=COLOR(I)+1 30      IF(__(2)__)THEN J=INDEX(I,1) 20         IF(J.LE.INDEX(I,2)) THEN IF(__(3)__) THEN J=J+1 GOTO 20 ELSE K=K+1 ____(4)____ ENDIF ____(5)____ I=I+1 GOTO 40 ENDIF COLOR(I)=0 _____(6)_____ GOTO 40 ENDIF IF(I.EQ.0)THEN WRITE(*,*)’NO SOLUTION’ ENDIF END

試題八

    閱讀以下程序說明和 C 程序，將應(yīng)填入__(n)__處的字句，寫在答卷的對應(yīng)欄內(nèi)。

    [程序說明]

    一個相連的區(qū)域被不規(guī)則地分割成 n 個不同的小區(qū)域；每個小區(qū)域與若干其它小區(qū)域相鄰接�，F(xiàn)用 cn 種不同顏色為該區(qū)域著色，要求每個小區(qū)域著同一種顏色，相鄰小區(qū)域著不同顏色。 設(shè)小區(qū)域被順序編號為 0，1，…，n-1。每個小區(qū)域與其它小區(qū)域的鄰接關(guān)系用兩維數(shù)組 bordering 表示，元素 bordering[i][j] 表示 i 號小區(qū)域與 j 號小區(qū)域之間的鄰接關(guān)系：

	0	j 小區(qū)域與 i 小區(qū)域不鄰接
bordering[i][j]=
	1	j 小區(qū)域與 i 小區(qū)域相鄰接

程序中，把計算結(jié)果存入于兩維數(shù)組 colored 中，顏色編號為 0,1,…,cn-1,元素 colored[coler][j] 的含義是:

	0	j 小區(qū)域不用顏色 color 著色
colored[color][j]=
	1	j 小區(qū)域用顏色 color 著色

　 函數(shù) colorcountry(bordering,colored,n,cn) 根據(jù)所給的小區(qū)域鄰接關(guān)系數(shù)組 bordering、小區(qū)域個數(shù) n 、顏色數(shù) cn，將找到的著色方案記錄在數(shù)組 colored 中。函數(shù)采用試探法找解。首先從第一個小區(qū)域著第一種顏色開始順序為各小區(qū)域找著色方案。對某個小區(qū)域，當(dāng)為它找到一種未被它的相鄰小區(qū)域著色的顏色時，就用該顏色對該小區(qū)域著色，并準(zhǔn)備處理下一個小區(qū)域。當(dāng)不能為某個小區(qū)域找到一個未被它的相鄰小區(qū)域著色的顏色時，就回溯。如最終為全部小區(qū)域找到著色方案，函數(shù)返回 1；否則，函數(shù)返回0。 程序假定小區(qū)域個數(shù)不超過 20，顏色數(shù)為 4。

    [程序]

    #include #define n 20 #define CN 4 int colorcountry(int bordering[][N], int colored[][N], int n,int cn) { int color,used,i,c; for(color = 0; color < cn; color++)  /* 設(shè)置所有區(qū)域均未著色 */ for(i = 0;i < n; i++) colored[coler][i] = 0; c = 0; /*從第1個小區(qū)域開始*/ color = 0; /*從著第1種顏色開始試控*/ while (c < n)  { /*還未對全部小區(qū)域著色時循環(huán)*/ while(___(1)___)/*順序?qū)γ糠N顏色作試探*/ {/*檢查當(dāng)前顏色是否已被某相鄰小區(qū)域著色*/ for (i = 0, used = 0; !used && i<c; i++) if(____(2)____) used = 1; if (!used) break; /*當(dāng)前顏色未被相鄰小區(qū)域著色*/ color++ } if (!used) { /* 找到一種可用顏色，用此色著色，并準(zhǔn)備處理下一個小區(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 cn) /* 輸出結(jié)果 */ { char *colortbl[] = {“RED”,”BLUE”,”GREEN”,”YELLOW”}; int color,i; for(color = 0; color < cn; color++) { printf(“\n%s;\n”,colortb1[color]); for(i = 0;i<n; 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”,&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(“&d”,&j); while (j >= 0) { if(i != j) bordering[i][j] = bordering[j][i] = 1; scanf(“%d”,&j); } } if(colorcountry(bordering,colored,n,CN)) print(colored,n,CN); else printf(“No Solution.\n”); }  

                                 答案

試題一（15分）

（1）(3分) 檢查發(fā)貨單中非法銷售代號、非法商品代號、數(shù)量*單價≠金額等錯誤。

答“檢查發(fā)貨單的合法性”得 2 分

（2）(4分) “刪除發(fā)貨文件中已做收款標(biāo)記的所有記錄”

或“將未收到款的記錄重新組成新發(fā)貨文件”。

（3）(4分) “刪除收款文件中的所有記錄”

或“刪除已收到款的記錄”

或“對收款文件初始化”。

（4）(4分) 從收款文件到處理 7 的連線改成從日收款分類文件到處理 7 的連線。

試題二（15分）

（1） (9分)

① (2分) i : n

② (2分) i ：n

③ (2分) i ：n

④ (3分) k ：G 或 K ：b1-E 

答K ： G-1 給2分。

（2）(4分) 159，98，3，25，33

注：錯 1 個扣 1 分，錯4、5個不給分。

（3）(2分) 4，1，3

注：錯 1 個不給分。

試題三（15分）

（1）（3分） 0 層圖中的房租文件和交費文件是局部文件，可不必畫出。

注：多寫一個文件扣 1 分，少 1 個文件扣 2 分。

（2）（8分）

① 加工 1 子圖中，遺漏了從住戶基本信息文件到加工 1.1 （入住單校驗）的數(shù)據(jù)流。

② 加工 1 子圖中，加工 1.6（制作住房分配報告）遺漏了輸出數(shù)據(jù)流：住房分配表。

③ 加工 2 子圖中，加工 2.1（計算月租費）遺漏了輸入數(shù)據(jù)流：月附加費表。

④ 加工 2 子圖中，加工 2.4（制作收據(jù)）遺漏了輸出數(shù)據(jù)流：收據(jù)。

注：答對 1 點得 3 分，答對 2 點得 6 分，答對3或4點得8分。未答下劃線部分的內(nèi)容時，另共扣 1 分。

（3）（4分）

① （2分） 交費憑證中有非法字符

② （2分） 交費文件中不存在與之對應(yīng)的交費憑證

試題四（15分）

（1）（3分） CPL GRO，SNO，GR1 （用 CPA 指令也可）

（2）（3分） LEA GR3，48

答LEA GR3， 0給1分。

（3）（3分） CPL GRO，SNO，GR1 （用 CPA 指令也可）

（4）（3分） JMP L3

答 JPZ L3 或 JNZ L3 也可給 3 分。

（5）（3分） LEA GR4，-5，GR1

答 LEA GR4，-4，GR1 給 1 分

其中 GR4 可寫成 GR3。

試題六（15分）

（1）（3分）s [ i ] = NULL

答 s [ i ] = … 給 1 分。

（2）（3分）top = top ->link

答 top = … 給 1 分。

（3）（3分）s[j] = NULL

答 s[j] = … 給 1 分。

（4）（3分）y != NULL && y ->data < q->data 或 y && y ->data < q->data

答 y -> data < q->data && y 或 y->data < q->data 給 2 分。

答 y ! = NULL && y->data != q->data 給 2 分。

答 y -> data != q -> data 給 1 分。

（5）（3分）q->link = y

答 q->link = x->link給 2 分。

答 q->link = …給 1 分。

試題七（15分）

（1）（3分） 1，N

（2）（3分） JJ，N

（3）（3分） N-1

（4）（3分） K . LT . II

（5）（3分） K . LT . JJ

試題八（15分）

（1）（3分） color < cn

答 color < 4 給 3 分；答 color <= cn 給 2 分。

（2）（3分）bordering[c][i] && colored[color][i]

答 bordering[c][i] == 1 && colored[color][i] == 1 給 3 分。

答 bordering[c][i] * colored[color] [i] == 1 給 3 分，而將其中相等運算符“==”寫成賦值運算符“=”時，只給 1 分。其中 bordering[c][i] 可寫成 bordering[i][c]。運算符‘&&’左右只對一半給 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 分。

試題九

（1）（3分） I . GE . 1 .AND. I .LE. N

答I .LE. N給 2 分，答 I .GE. 1 給 1 分。

（2）（2分） K .LE. 4 或 K .LT. 5

（3）（3分） K .NE. COLOR(BORDER(J))

答 K .NE. …給 1 分，答….NE. COLOR(BORDER(J)) 給 2 分

（4）（2分） GOTO 30

（5）（3分） COLOR（I） = K

（6）（2分） I = I - 1