一九九七年度高级程序员级下午试题

试题二..joxue.
阅读以下说明和流程图，回答问题1至问题3，将解答写在答卷的对应栏内。..joxue.
[说明]..joxue.
本流程图用来实现一组正整数的加权舍位平衡。已知正整数组..joxue.
A(a1,a2,…，an)..joxue.

满足条件a1= (n>3)。现将数组A中的每个数舍P位（P为正整数）后，得到另一正整数数组..joxue.
B(b1,b2,…,bn)..joxue.
它满足如下条件：..joxue.
１.b1是a1舍P位后四舍五入所得，即b1=INT(a1/10p0.5) ..joxue.
２.b1 = ..joxue.
３.bi=INT(ai/10P)+ei(i=2,3,…,n), 其中ei取值为0或1，当ei=1时，称ei是第i项数据的进位..joxue.
４.ei(i=2,3,……,n)之值根据余数MOD（ai,10P）乖上权fi(fi>0)后的数值大小来决定（其算法见流程图），..joxue.
权fi存放在数组F中。..joxue.
其中INT是取整数函数，MOD是余数函数。例如正整数78965舍P=3位，则..joxue.
INT（78965/103）=78..joxue.
MOD（78965，103）=965..joxue.
[问题1]..joxue.
填充流程图中①～④ ，把解答写在答卷纸的相应位置上。..joxue.
[问题2]..joxue.
若 N=5，P=1，A=（1586，985，26，247，328）..joxue.
F=（1，1，1，1，1）..joxue.
则数组B的值是多少？..joxue.
[问题3]..joxue.
若N=3，P=1，A=（41，16，25），F=（1，0，0），则数组B的值是多少？..joxue.

试题三..joxue.
阅读以下说明和流程图,回答问题1至问题3,将解答写在答卷的对应栏内。..joxue.
[说明]..joxue.
下面给出的是某房产管理系统的一套分层数据流图。其功能描述如下：..joxue.
系统随时根据住房送来的入信单更新信户基本信息文件；..joxue.
每月初系统根据物业管理委员会提供的月附加费（例如清洁费、的保安费、的大楼管理费等�）表和房租调整表，..joxue.
计算每家住户的月租费（包括月附加费），向住户发出交费通知单。住户交费时，系统输入交费凭证，核对后..joxue.
输出收据给住户；..joxue.
系统定期向物业管理委员会提供住房分配表和交费情况表；..joxue.
住户因分户或换房，在更新住户基本信息文件的同时，系统应立即对这些住户做月租费计算，以了结分户或换..joxue.
房前的房租。..joxue.
假定题中提供的顶层图是正确的，请回答下列问题：..joxue.
[问题1]..joxue.
指出哪张图中的哪些文件可不必画出。..joxue.
[问题2]..joxue.
指出在哪些图中遗漏了哪些数据流。回答时请用如下形式之一：..joxue.
××图中遗漏了××加工（或文件）流向××加工（或文件）的××数据流；..joxue.
××图中加工××遗漏了输入（或输出）数据流××。..joxue.
[问题3]..joxue.
指出加工2图中加工2.3能检查出哪些不合格交费凭证。..joxue.
[流程图]..joxue.
顶层图..joxue.

试题四..joxue.
在COMET型计算机上可以使用试卷上所附的CASL汇编语言。阅读下列程序说明和CASL程序，将应填入__(n)__..joxue.
处的字句，写在答卷的对应栏内。..joxue.
[程序说明]..joxue.
本子程序将一个非负二进整数翻译成五位十进整数字符。..joxue.
进入子程序时，在GR0中给出被翻译的非负二进整数，在GR2中给出存放五位十进整数数字字符的起始地址。..joxue.
十进制数字字符用ASCII码表示。当结果小于五位时，左边无空白符替换；当二进整数为零时，在（GR2）+4中..joxue.
存放0的ASCII码。..joxue.
数字字符0至9的ASCII码是48至57，空白符的ASCII码是32。..joxue.
[程序]..joxue.
START..joxue.
LEA GR1，0..joxue.
LEA GR3，32..joxue.
L1 ____(1)____..joxue.
JPZ L2..joxue.
ST GR3,0,GR2..joxue.
LEA GR2,1,GR2..joxue.
LEA GR1,1,GR1..joxue.
JNZ L1..joxue.
L2 ___(2)___..joxue.
L3 ___(3)___..joxue.
JMI L4..joxue.
SUB GR0,SN0,GR1..joxue.
LEA GR3,1,GR3..joxue.
___(4)___..joxue.
L4 ST GR3,0,GR2..joxue.
LEA GR2,1,GR2..joxue.
LEA GR1,1,GR1..joxue.
___(5)___..joxue.
JNZ L2..joxue.
RET..joxue.
SON NC 10000..joxue.
DC 1000..joxue.
DC 100..joxue.
DC 10..joxue.
DC 1..joxue.
END..joxue.

试题五..joxue.
阅读以下程序说明和FORTRAN程序，将应填入__(n)__处的字句，写在答卷的对应栏内。..joxue.
[程序说明]..joxue.
对称矩阵通常只需存储其下三角部分，例如，下列对称矩阵..joxue.
可用一维数组（1，2，3，4，5，6，7，8，9，10）存储其下三角部分。N阶对称矩阵下三角部分的元素个数..joxue.
为(N*N+N)/2。..joxue.
本子程序用来计算N阶对称矩阵A的平方B，B也是一个N阶对称矩阵。程序中X，Y是分别存入A，B下三角部分..joxue.
的一维数组。..joxue.
[程序]..joxue.
SUBROUTINE P（X，Y，N）..joxue.
INTEGER X（N*N+N）/2，Y（N*N+N）/2），S..joxue.
M=1..joxue.
DO 10 JJ=__(1)__..joxue.
DO 10 II =__(2)__..joxue.
I=II..joxue.
J=JJ..joxue.
L=__(3)__..joxue.
S=0..joxue.
DO 30 K=1,N..joxue.
S=S+X(I)*X(J)..joxue.
IF(____(4)____)THEN..joxue.
I=I+L..joxue.
ELSE..joxue.
I=I+1..joxue.
ENDIF..joxue.
IF(____(5)____)THEN..joxue.
J=J+L..joxue.
ELSE..joxue.
J=J+1..joxue.
ENDIF..joxue.
L=L-1..joxue.
30 CONTINUE..joxue.
Y(M)-S..joxue.
M=M+1..joxue.
CONTINUE..joxue.
END..joxue.

试题六..joxue.
阅读以下程序说明和C程序，将应填入__(n)__ 处的字句，写在答卷的对应栏内。..joxue.
[程序说明]..joxue.
某系统由n个部件组成，这些部件被物理地分成若干个分离的部件组。同一组内的两件部件i和j，它们或直接..joxue.
相连，或间接相连（部件i和部件j间接相连是指在这两件部件之间有一个部件相连序列，其中部件i和j分别..joxue.
与这相连序列中的某个部件直接相连）。系统的n个部件被统一编号为0，1，…，n-1。本程序输入所有直接..joxue.
相连的部件号对，分别求出系统各分离部件组中的部件号并输出。..joxue.
程序根据输入的直接相连的两件部件号，建立n个链表，其中第i个链表的首指针为s[i]..joxue.
，其结点是与部件i直接相连的所有部件号。..joxue.
程序依次处理各链表。在处理s[i]链表中，用top工作链表重新构造s[i]链表，使s[i]链表对应系统中的一个..joxue.
部件组，其中结点按部件号从小到大连结。..joxue.
[程序]..joxue.
# include ..joxue.
#define N 100..joxue.
typeef struct node{..joxue.
int data;..joxue.
struct node *link;..joxue.
} NODE;..joxue.
NODE*s[N];..joxue.
int i,j,n,t;..joxue.
NODE *q,*p,*x,*y,*top;..joxue.
main()..joxue.
{ printf(“Enter number of parts.”);..joxue.
scanf(“%d”,&n);..joxue.
for(i=0;idata=j; p->link=s[i]; s[i]=p;..joxue.
p=(NODE *)malloc(sizeof(NODE));..joxue.
P->data=i; p->link=s[j]; s[j];=p;..joxue.
}..joxue.
for(i=0;idata]!=NULL)..joxue.
{ /将j链表也移入工作链表*/..joxue.
for(p=s[j];p->link ！=NULL;p=p->link);..joxue.
p->link=top; top=s[j];____(3)____;..joxue.
}..joxue.
/*在重新生成的第i链表中寻找当前结点的插入点*/..joxue.
for(y=s[i];____(4)____;x=y,y=y->link);..joxue.
if(y!=NULL && y ->data= =q->data)..joxue.
free(q);/*因重新生成的第i链表已有当前结点，当前结点删除* /..joxue.
else { /* 当前结点插入重新生成的i链表*/..joxue.
____(5)____；..joxue.
if(y= =s[i]) s[i]=q;..joxue.
else x->link=q;..joxue.
}..joxue.
}..joxue.
for(i=0;idata);..joxue.
q=p->link; free(p); p=q;..joxue.
}..joxue.
printf(“\n”);..joxue.
}..joxue.
}..joxue.

试题七..joxue.
阅读以下程序说明和FORTRAN程序，将应填入__(n)__处的字句，写在答卷的对应栏内。..joxue.
[程序说明]..joxue.
本子程序实现地图的着钯。在地图上，一个国家所着的颜色必须与所有相邻的国家所着的颜色不同。现已证明，..joxue.
仅需四种不同的颜色就能解决地图的着钯..joxue.
若地图上有N个国家，分别用1至N编号。子程序中用数组INDEX（N，2）和BORDER（M）存放N个国家的相邻情况。..joxue.
INDEX（I，1）和INDEX（I，2）分别表示与第I国相邻的国家编号在数组BORDER中的起始位置和终止位置，即..joxue.
这些邻国的编号存放在BORDER（INDEX（I，1））至BORDER（INDEX（I，2））中。例如，对应于图1所示的地图..joxue.
，数级INDEX和BORDER具有如下值：..joxue.
INDEX=..joxue.
BORDER-（2，3，4，5，1，3，1，2，4，5，1，3，5，1，3，4）..joxue.
子程序中分别用1，2，3，4代表四种不同颜色，着色结果存放在数组COLOR中，即数组元素COLOR（I）的值为..joxue.
第I个国家所着的颜色。..joxue.
子程序采用试控法找解。首先从第I个国家着第一种颜色开始，顺序为各个国家寻找着色方案。对第I个国家，..joxue.
当为它找到一种未被它的相邻国家着色的颜色时，就用该颜色对此国家着色，并准备处理下一国家；当不能为..joxue.
它找到一个未被它的相邻国家着色的颜色时，就回溯��即改变第I-1个国家的着色方案。直至最终为全..joxue.
部国家找到着色方案。..joxue.
[程序]..joxue.
SUBROUTINE P（INDEX，BORDER，COLOR，N，M）..joxue.
INTEGER INDEX（N，2），BORDER（M），COLOR（N）..joxue.
DO 10 I=1，N..joxue.
COLOR（I）=0..joxue.
I=1..joxue.
IF（__(1)__）THEN..joxue.
K=COLOR(I)+1..joxue.
IF(__(2)__)THEN..joxue.
J=INDEX(I,1)..joxue.
IF(J.LE.INDEX(I,2))THEN..joxue.
IF(__(3)__)THEN..joxue.
J=J+1..joxue.
GOTO 20..joxue.
ELSE..joxue.
K=K+1..joxue.
____(4)____..joxue.
ENDIF..joxue.
___-(5)____..joxue.
I=I+1..joxue.
GOTO 40..joxue.
ENDIF..joxue.
COLOR9I)=0..joxue.
_____(6)_____..joxue.
GOTO 40..joxue.
ENDIF..joxue.
IF(I.EQ.0)THEN..joxue.
WRITE(*,*)’NO SOLUTION’..joxue.
ENDIF..joxue.
END..joxue.

试题八..joxue.
阅读以下程序说明和C程序，将应填入__(n)__处的字句，写在答卷的对应栏内。..joxue.
[程序说明]..joxue.
一个相连的区域被不规则地分割成n个不同的小区域；每个小区域与若干其它小区域相邻接。现用cn种不同颜..joxue.
色为该区域着色，要求每个小区域着同一种颜色，相邻小区域着不同颜色。..joxue.
设小区域被顺序编号为0，1，…，n-1。每个小区域与其它小区域的邻接关系用两维数组bordering表示，元..joxue.
素bordering[i][j]表示i号小区域与j 号小区域之间的邻接关系：..joxue.
0 j小区域与i小区域不邻接 ..joxue.
bordering[i][j]= ..joxue.
1 j小区域与i小区域相邻接..joxue.
程序中，把计算结果存入于两维数组colored中，颜色编号为0,1,…,cn-1,元素colored[coler][j]的含义是..joxue.
0 j小区域不用颜色color着色..joxue.
colored[color][j]=..joxue.
1 j小区域用颜色color着色..joxue.
函数colorcountry(bordering,colored,n,cn)根据所给的小区域邻接关系数组bordering、的小区域个数n 、的..joxue.
颜色数cn，将找到的着色方案记录在数组colored中。函数采用试探法找解。首先从第一个小区域着第一种颜..joxue.
色开始顺序为各小区域找着色方案。对某个小区域，当为它找到一种未被它的相邻小区域着色的颜色时，就用..joxue.
该颜色对该小区域着色，并准备处理下一个小区域。当不能为某个小区域找到一个未被它的相邻小区域着色的..joxue.
颜色时，就回溯。如最终为全部小区域找到着色方案，函数返回1；否则，函数返回0。..joxue.
程序假定小区域个数不超过20，颜色数为4。..joxue.
[程序]..joxue.
#include..joxue.
#define n 20..joxue.
#define CN 4..joxue.
int colorcountry(int bordering[][N], int colored[][N], int n,int cn)..joxue.
{ int color,used,i,c;..joxue.
for(color=0;colorn;i++)colored[color][i]=0;..joxue.
c =0; /*从第1个小区域开始*/..joxue.
color =0; /*从着第1种颜色开始试控*/..joxue.
while(cc;i++)..joxue.
if(____(2)____)used=1;..joxue.
if(!used)break; /*当前颜色未被相邻小区域着色*/..joxue.
color++..joxue.
}..joxue.
if(!used)..joxue.
{ /*找到一种可用颜色，用此色着色，并准备处理下一个小区域*/..joxue.
____(3)____=1; color=0;..joxue.
}else{/*未找到一种可用颜色，回溯*/..joxue.
c--;if (c<0)return 0; /*发现没有解的情况*/ for(color=0;____(4)____;color++); ____(5)____=0 } } return 1; } print(int colored[ ][n],int n,int cn) /*输出结果*/ { char *colort[ ]={“RED”,”BLUE”,”GREEN”,”YELLOW”}; int color,i; for(color=0;colorn;i++)..joxue.
if(colored[color][i]) printf(“\t%d”,i);..joxue.
printf(“\n”);..joxue.
}..joxue.
}..joxue.
int colored[CN][N],bordering[N][N];..joxue.
main()..joxue.
{ int c,i,j,n;..joxue.
printf(“Enter number of areas.”); scanf(“%d”,&n);..joxue.
printf(“Enter bordering:\n”);..joxue.
for(i=0;in;j++)bordering[i][j]=0;..joxue.
for(i=0;i0 to next).\n”,i);..joxue.
scanf(“&d”,&j);..joxue.
while(j>=0)..joxue.
{ if(i !=j) bordering[i][j]=bordering[j][i]=1;..joxue.
scanf(“%d”,&j);..joxue.
}..joxue.
}..joxue.
if(colorcountry(bordering,colored,n,CN))..joxue.
print(colored,n,CN);..joxue.
else printf(“No Solution.\n”);..joxue.