【字体：大 小】1997年高级程序员下午试题及答案

1997年高级程序员下午试题及答案

spks.exam8.com　来源：考试吧（www.exam8.com）　更新：2005-4-13 0:38:00　软件水平考试　考试论坛

试题五

     阅读以下程序说明和 FORTRAN 程序，将应填入__(n)__处的字句，写在答卷的对应栏内。

    [程序说明]

    对称矩阵通常只需存储其下三角部分，例如，下列对称矩阵

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

    可用一维数组（1，2，3，4，5，6，7，8，9，10）存储其下三角部分。N 阶对称矩阵下三角部分的元素个数为 ( N * N + N ) / 2 。 本子程序用来计算 N 阶对称矩阵 A 的平方 B，B 也是一个 N 阶对称矩阵。程序中 X，Y 是分别存入 A，B 下三角部分的一维数组。

    [程序] 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 程序，将应填入__(n)__ 处的字句，写在答卷的对应栏内。

    [程序说明]

    某系统由 n 个部件组成，这些部件被物理地分成若干个分离的部件组。同一组内的两件部件 i 和 j，它们或直接相连，或间接相连（部件 i 和部件 j 间接相连是指在这两件部件之间有一个部件相连序列，其中部件 i 和 j 分别与这相连序列中的某个部件直接相连）。系统的 n 个部件被统一编号为 0，1，…，n-1。本程序输入所有直接相连的部件号对，分别求出系统各分离部件组中的部件号并输出。 程序根据输入的直接相连的两件部件号，建立 n 个链表，其中第 i 个链表的首指针为 s[i]，其结点是与部件 i 直接相连的所有部件号。 程序依次处理各链表。在处理 s[i] 链表中，用 top 工作链表重新构造 s[i] 链表，使 s[i] 链表对应系统中的一个部件组，其中结点按部件号从小到大连结。

    [程序]

     # 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) { /*输入相连部件对，生成相连部件结点链表*/ 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工作链表，并顺序处理工作链表的各结点*/ 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 链表中寻找当前结点的插入点 */ for(y = s[i]; ____(4)____; x = y,y = y->link); if(y != NULL && y->data == q->data) free(q);/*因重新生成的第i链表已有当前结点，当前结点删除* / else { /* 当前结点插入重新生成的i链表*/ ____(5)____； if(y == s[i]) s[i] = q; else x->link = q; } } for(i = 0;i < n; i++) { /* 输出结果 */ 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 程序，将应填入__(n)__处的字句，写在答卷的对应栏内。

    [程序说明]

    本子程序实现地图的着钯。在地图上，一个国家所着的颜色必须与所有相邻的国家所着的颜色不同。现已证明，仅需四种不同的颜色就能解决地图的着色 若地图上有 N 个国家，分别用 1 至 N 编号。子程序中用数组 INDEX（N，2）和 BORDER（M）存放 N个国家的相邻情况。INDEX（I，1）和 INDEX（I，2）分别表示与第 I 国相邻的国家编号在数组 BORDER中 的起始位置和终止位置，即这些邻国的编号存放在 BORDER（INDEX（I，1））至 BORDER（INDEX（I，2））中。

    例如，对应于图 1 所示的地图，数级 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 代表四种不同颜色，着色结果存放在数组 COLOR 中，即数组元素 COLOR(I)的值为第 I 个国家所着的颜色。 子程序采用试控法找解。首先从第 I 个国家着第一种颜色开始，顺序为各个国家寻找着色方案。对第  I 个国家，当为它找到一种未被它的相邻国家着色的颜色时，就用该颜色对此国家着色，并准备处理下一国家；当不能为它找到一个未被它的相邻国家着色的颜色时，就回溯——即改变第 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 程序，将应填入__(n)__处的字句，写在答卷的对应栏内。

    [程序说明]

    一个相连的区域被不规则地分割成 n 个不同的小区域；每个小区域与若干其它小区域相邻接。现用 cn 种不同颜色为该区域着色，要求每个小区域着同一种颜色，相邻小区域着不同颜色。 设小区域被顺序编号为 0，1，…，n-1。每个小区域与其它小区域的邻接关系用两维数组 bordering 表示，元素 bordering[i][j] 表示 i 号小区域与 j 号小区域之间的邻接关系：

	0	j 小区域与 i 小区域不邻接
bordering[i][j]=
	1	j 小区域与 i 小区域相邻接

程序中，把计算结果存入于两维数组 colored 中，颜色编号为 0,1,…,cn-1,元素 colored[coler][j] 的含义是:

	0	j 小区域不用颜色 color 着色
colored[color][j]=
	1	j 小区域用颜色 color 着色

　 函数 colorcountry(bordering,colored,n,cn) 根据所给的小区域邻接关系数组 bordering、小区域个数 n 、颜色数 cn，将找到的着色方案记录在数组 colored 中。函数采用试探法找解。首先从第一个小区域着第一种颜色开始顺序为各小区域找着色方案。对某个小区域，当为它找到一种未被它的相邻小区域着色的颜色时，就用该颜色对该小区域着色，并准备处理下一个小区域。当不能为某个小区域找到一个未被它的相邻小区域着色的颜色时，就回溯。如最终为全部小区域找到着色方案，函数返回 1；否则，函数返回0。 程序假定小区域个数不超过 20，颜色数为 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++)  /* 设置所有区域均未着色 */ for(i = 0;i < n; i++) colored[coler][i] = 0; c = 0; /*从第1个小区域开始*/ color = 0; /*从着第1种颜色开始试控*/ while (c < n)  { /*还未对全部小区域着色时循环*/ while(___(1)___)/*顺序对每种颜色作试探*/ {/*检查当前颜色是否已被某相邻小区域着色*/ for (i = 0, used = 0; !used && i<c; i++) if(____(2)____) used = 1; if (!used) break; /*当前颜色未被相邻小区域着色*/ color++ } if (!used) { /* 找到一种可用颜色，用此色着色，并准备处理下一个小区域 */ ____(3)____ = 1; color = 0; }else{ /* 未找到一种可用颜色，回溯 */ c--; if (c < 0) return 0; /*发现没有解的情况*/ for(color = 0; ____(4)____; color++); ____(5)____ = 0 } } return 1; } print(int colored[][N],int n,int cn) /* 输出结果 */ { 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分) 检查发货单中非法销售代号、非法商品代号、数量*单价≠金额等错误。

答“检查发货单的合法性”得 2 分

（2）(4分) “删除发货文件中已做收款标记的所有记录”

或“将未收到款的记录重新组成新发货文件”。

（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 （入住单校验）的数据流。

② 加工 1 子图中，加工 1.6（制作住房分配报告）遗漏了输出数据流：住房分配表。

③ 加工 2 子图中，加工 2.1（计算月租费）遗漏了输入数据流：月附加费表。

④ 加工 2 子图中，加工 2.4（制作收据）遗漏了输出数据流：收据。

注：答对 1 点得 3 分，答对 2 点得 6 分，答对3或4点得8分。未答下划线部分的内容时，另共扣 1 分。

（3）（4分）

① （2分） 交费凭证中有非法字符

② （2分） 交费文件中不存在与之对应的交费凭证

试题四（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