1997年度高级程序员级下午试卷
试题一阅读以下说明和流程图，回答问题1至问题4，将解答写在答卷的对应栏内。
[说明]
某公司将其生产的商品通过若干个销售点进行销售。销售点在收到商品后的规定时间内把货款汇给公司。
流程图描述了该公司发货、收款、催款的处理过程。其中部分文件和单据的格式如下：
商品文件：商品代号，商品名称，单价
销售点文件：销售点代号，销售点名称，地址
发货单：发货日期，销售点代号，商品代号，数量，金额
收款单：收款日期，销售点代号，商品代号，数量，金额，该商品的发货日期
处理 1～3 把当天的发货单合并到发货文件。处理
4～6 把当天的收款单合并到收款文件。处理 7 在发货文件中当天已收款的记录上加上已收款标记。处理
8 和处理 9
在月末执行一次，主要用于输出月发货报告、催款通知单、月收款报告。
[问题1]
详细写出流程图中商品文件和销售点文件对处理1的作用。
[问题2]
说明处理 8 为何要写发货文件。
[问题3]
说明处理 9 除制作月收款报告外还对收款文件做什么操作。
[问题4]
为了提高处理效率，流程图需作何改动。
试题二
阅读以下说明和流程图，回答问题
1 至问题 3，将解答写在答卷的对应栏内。
[说明]
本流程图用来实现一组正整数的加权舍位平衡。已知正整数组
A(a1,a2,…，an)
n
满足条件 a1=∑
(n≥3)。现将数组 A 中的每个数舍 P 位（P 为正整数）后，得到另一正整数数组
i=2
B(b1,b2,…,bn)
它满足如下条件：
1、b1是a1舍P位后四舍五入所得，即b1
= INT(a1/10P + 0.5)
n
2、b1
=∑bi
i=2
3、bi = INT(ai/10P) + ei(i =
2,3,…,n),
其中 ei 取值为 0 或 1，当 ei = 1时，称
ei 是第 i 项数据的进位
4、ei(i = 2,3,……,n)之值根据余数 MOD（ai,10P）乖上权
fi(fi≥0) 后的数值大小来决定（其算法见流程图），权
fi 存放在数组 F 中。
其中 INT 是取整数函数，MOD 是余数函数。例如正整数 78965 舍 P = 3 位，则
INT（78965/103）=78
MOD（78965，103）=965
[问题1]
填充流程图中①～④ ，把解答写在答卷纸的相应位置上。
[问题2]
若 N = 5，P = 1，A =（1586，985，26，247，328）
F =（1，1，1，1，1）
则数组B的值是多少？
[问题3]
若 N =
3，P = 1，A =（41，16，25），F =（1，0，0），则数组 B
的值是多少？
试题三
阅读以下说明和流程图,回答问题1至问题3,将解答写在答卷的对应栏内。
[说明]
下面给出的是某房产管理系统的一套分层数据流图。其功能描述如下：
（1）系统随时根据住房送来的入信单更新信户基本信息文件；
（2）每月初系统根据物业管理委员会提供的月附加费（例如清洁费、保安费、大楼管理费等）表和房租调整表，计算每家住户的月租费（包括月附加费），向住户发出交费通知单。住户交费时，系统输入交费凭证，核对后输出收据给住户；
（3）系统定期向物业管理委员会提供住房分配表和交费情况表；
（4）住户因分户或换房，在更新住户基本信息文件的同时，系统应立即对这些住户做月租费计算，以了结分户或换房前的房租。
假定题中提供的顶层图是正确的，请回答下列问题：
[问题1]
指出哪张图中的哪些文件可不必画出。
[问题2]
指出在哪些图中遗漏了哪些数据流。回答时请用如下形式之一：
1）×× 图中遗漏了 ×× 加工（或文件）流向 ×× 加工（或文件）的 ×× 数据流；
2）××
图中加工 ×× 遗漏了输入（或输出）数据流 ×× 。
[问题3]
指出加工
2 图中加工 2.3 能检查出哪些不合格交费凭证。
[流程图]
顶层图
试题四
在 COMET 型计算机上可以使用试卷上所附的
CASL 汇编语言。阅读下列程序说明和 CASL 程序，将应填入__(n)__处的字句，写在答卷的对应栏内。
[程序说明]
本子程序将一个非负二进整数翻译成五位十进整数字符。
进入子程序时，在GR0 中给出被翻译的非负二进整数，在 GR2 中给出存放五位十进整数数字字符的起始地址。
十进制数字字符用 ASCII 码表示。当结果小于五位时，左边无空白符替换；当二进整数为零时，在（GR2）+4中存放 0 的 ASCII 码。
数字字符 0
至 9 的 ASCII 码是 48 至 57，空白符的 ASCII 码是 32。
[程序]
START
LEA GR1，0
LEA GR3，32
L1 ____(1)____
JPZ L2
ST GR3,0,GR2
LEA GR2,1,GR2
LEA GR1,1,GR1
LEA GR4，-4，GR1
JNZ L1
L2 ___(2)___
L3 ___(3)___
JMI L4
SUB GR0,SN0,GR1
LEA GR3,1,GR3
___(4)___
L4 ST GR3,0,GR2
LEA GR2,1,GR2
LEA GR1,1,GR1
___(5)___
JNZ L2
RET
SON DC 10000
DC 1000
DC 100
DC 10
DC 1
END
试题五
阅读以下程序说明和
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 下三角部分的一维数组。
[程序]
SUBROUTINE 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);
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(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;
}
}
{ /* 输出结果 */
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，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(i = 0;i < n; i++) colored[coler][i] = 0;
c = 0; /*从第1个小区域开始*/
color = 0; /*从着第1种颜色开始试控*/
{ /*还未对全部小区域着色时循环*/
while(___(1)___)/*顺序对每种颜色作试探*/
{/*检查当前颜色是否已被某相邻小区域着色*/
for (i =
0, used = 0; !used &&
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;
{ printf(“\n%s;\n”,colortb1[color]);
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 (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”);
}