1996年度程序员级下午试卷

阅读以下程序说明和 C 程序，将应填入程序中 （n） 处的字句，写在答卷的对应栏内。

[程序说明]

本程序为六个整型变量 A、B、C、D、E、F 输入整数，并按从大到小的顺序输出它们的名和值。如某次 A、B、C、D、E、F 的输入值为 3、2、5、7、4、6，则程序将输出：

D（7）F（6）C（5）E（4）A（3）B（2）

[程序]

#define N sizeof tbl/sizeof tbl[0]

m = N-1; /*采用冒泡法排序*/

white (m>0)

for( k = j = 0;j < m;j++) /*比较直至上轮循环的最后交换前*/

m =__(4)__;  /*本框填 m-1 不给分*/

试题二

 略（FORTRAN 程序，辛卜生公式）

试题三

阅读以下程序说明和C程序，将应填入程序中 （n） 处的字句，写在答卷的对应栏内。
[程序说明]

本程序将自然数 1，2，……，N² 按蛇形方式逐个顺序存入 N 阶矩阵。

例如，当 N = 3 和 4 时分别如图 3.1 和图 3.2。

从 a_n0 开始到 a_0n 为止（n = N-1）顺序填入自然数，交替地对每一斜列从左上元素向右下元素或从右下元素向左上元素存数。
[程序]

#include

#define SIZE 10

int a[SIZE] [SIZE], k;

main()

{ int i, j, n, N;

for (N = 3;N<=SIZE; N++)

{ k = 1;

makeArray (n = N-1);

printf (＂\nN = %d;\n＂,n+1);

for (i = 0;i<=n; i++)

{ for (j = 0; j<=n; j++)printf(＂%4d＂,a[i][j]);

printf (＂\n＂);

}

}

}

makeline (int row_start, int col_start, int row_end)

{ /*完成矩阵一条斜线的整数填写*/

int i, j, sign = ____(1)____;

for (i = row_start, j = col_start;____(2)____ >=0; i += sign,j += sign)

a[i][j] = k++;

}

makeArray (int n)

{ /* 完成矩阵每条斜线的整数填写*/

int d;

for (d = 1; d <= ___(3)___; d++)

if (d <= n);

if (d%2) makeline (____(4)____); else makeline(____(5)____);

else

if (d%2) makeline (____(6)____); else makeline(____(7)____);

}

试题四

阅读以下程序说明和 FORTRAN 程序，将应填入程序中 （n） 处的字句，写在答卷的对应栏内。
[程序说明]

子程序 ORDER 根据 N(N<100) 位选手的成绩

A(I)( I = 1, 2, …, N )

将每人的名次存入数组 B 的对应元素 B(I) 中。成绩高的选手名次在前，成绩相同的选手名次相同。若有 K 位选手名次相同，则下一位名次增加 K。例如，若 8 位选手的成绩依次为

35，36，35，40，38，37，38，34
则其名次依次为

6， 5， 6， 1， 2， 4， 2， 8
其中有两位并列第 2，其下一个名次为 4，没有第 3 名。

程序首先找出与成绩最高的一位或几位选手对应的下标，并将 B 数组的对应元素置为第 1 名。然后，检查是否还有名次未定的选手，如有，找出这些选手中成绩最高的一位或几位，将其名次存入 B 数组的对应元素，继续同样步骤，直到排定全部选手的名次。
[程序]

SUBROUTINT ORDER (A,B,N)

INTEGER A(N),B(N),T(100)

DO 10 I=1,N

10     B(I)=0

NUM=1

DO 50 I=1,N

60     IF(____(1)____)THEN

MAX=A(I)

K=1

T(K)=I

DO 30 J=I+1,N

IF ((B(J).EQ.0).AND.(A(J).GE.MAX))THEN

IF(A(J).GT.MAX)THEN

MAX=A(J)

____(2)____

ENDIF

____(3)____

____(4)____

ENDIF

30       CONTINUE

DO 40 J=1,K

40           ____(5)____=NUM

NUM =____(6)____

____(7)____

ENDIF

50  CONTINUE

END

试题五

阅读以下程序说明和 C 程序，将应填入程序中 （n） 处的字句，写在答卷的对应栏内。
[程序说明]

将 A、B、C、D、E、F 6个变量排成如图 5.1 所示的三角形，这 6 个变量分别取 [1，6] 上的整数，且互不相同。本程序找出使三角形三条边上的三个数之和相等的所有可能解。图 5.2 表示其中 1 个解。

程序采用试探法，即 A、B、C、D、E、F 的顺序试探找数。例如，已为 A、B 确定了数，就在尚未使用过的 4 个数中找一个数给 C。当为 F 找到剩下的 1 个数时，程序就测试它们是否满足要求。满足要求的是解，将它们输出。当处理完一组数后，应回溯去找下一组可能的解。例如，处理完一组数值（1，2，4，6，5，3）后就回溯。

1, 2, 4←6←5←3（←表示回溯）

下面便处理 1 2 5 ……（例如 1 2 5 3 4 6 等）。上述试探法求解实际上是穷尽了 6 个数的所有排列。
[程序]

#define N 6

int A,B,C,D,E,F;

int *pt[ ] = {&A,&B,&C,&D,&E,&F};

main( )

{ int b[N+1], j, k, c=0; /* c为找到的解的计数器 */

for (j=1;j<=N,j++) b[j] = 0; /* 预置6个数均未被选用标志 */

k = 0; j = 1;

while (1)

{ if (!b[j] )

{ b[ ___(1)___ ] = 1; /* 登录选定的数，并置该数已被选用标志 */

if (k < N-1)

{ /* 准备为第 k+1 个数选择整数 */

k++; j = 1;

continue;

}

if (A+B+C == C+D+E && A+B+C == E+F+A)

{ /* 测试6个数是否满足要求，满足是解，就输出 */

printf (＂%d\n\t\t%6d\n\t\t%4d%4d\n\t\t%2d%4d%4d\n\n＂,

++c,A,B,F,C,D,E);

scanf (＂%*c＂); /* 输出一个解后,按回车输出下一个解 */

}

do { /* 回溯 */

b[*pt[___(2)___]] = 0;

if (k<0) ___(3)___;

for (j=*pt[k]+1; ___(4)___; j++); /* 寻找第k个数的可用数 */

if (____(5)____) break;

} while (1);

if ( k < 0 ) break /* 已穷尽所有可能的选择 */

b[*pt[ ____(6)____ ]] = 0 /* 清除原先所选用的数的标志 */

j = ____(7)____; /* 调整第k个数可选用的数 */

}

else

while (++j<=N&&b[j]); /* 调整 */

}

}

试题六

阅读以下程序说明和 FORTRAN 程序，将应填入程序中 （n） 处的字句，写在答卷的对应栏内。
[程序说明]

子程序 PRINT 对给定的N（2 < N < 50）和M（2 < M < 16），以 M 进制形式计算并输出 N！的全部有效数字。

因 N！的值通常超出整型数最大值，故程序采用一维数组存储计算结果。数组 A 的每一个元素存放N！的 M 进制表示形式的一位数值。例如：当 N=9，M=10 时

9！= 362880 （10）

其存储形式为

当N = 3，M = 4时

3！= 12 （4）

其存储形式为

数组下标 1 2 3 4 5 ……

值 2 1 0 0 0 ……

程序中，用加法代替乘法计算阶乘，（K-1）！作为加数暂存于数组B中，D是数组B中有效数字的长度。
[程序]

SUBROUTINE PRINT (M,N)

CHARACTER V*16

INTERGER A(200), B(200), C, D

DATA V/ ＇012345678ABCEDF ＇/

DO 10 I = 1,200

A ( I ) = 0

B ( I ) = 0

10   CONTINUE

A (1) = 1

D = _______(1)_______

DO 70 K=2,N

DO 20 J=1,D

____(2)____

20     CONTINUE

DO 50 NUM=1.____(3)____

I=1

40     C=A(O)+B(I)

A(I)=___(4)____

I=I+1

_____(5)____

IF ( I. LT. MIN(D+K-1,200)) ____(6)____

50     CONTINUE

60     IF ( A(I) . EQ. 0 ) THEN

I=I-1

GOTO 60

ENDIF

____(7)____

70   CONTINUE

WRITE ( *,100) N,M,(V(A(J)+1:A(J)+1),J=D,1,-1)

100  FORMAT (1X, I2, ＇! ( ＇, I2 , ＇) = ＇,50A1/3(9X,50A1))

RETURN

END

试题七

阅读以下程序说明和 C 程序，将应填入程序中 （n） 处的字句，写在答卷的对应栏内。
[程序说明]

某集团公司为发展生产向社会公开招聘 M 个工种的工作人员，每个工种各有不同的编号（1 至 M）和计划招聘人数。每位应聘者需申报两个工种，并参加公司组织的考试。公司将按应聘者的成绩从高分至低分的顺序进行排队录取。公司的录取原则是：从高分到低分依次对每位应聘者先按其第一志愿录取；当不能按其第一志愿录取时，便将他的成绩扣去 5 分后，重新排队，并按其第二志愿考虑录取。

程序为输出各工种实际招聘的应聘人员，每个工种都保留一个录取者的有序队列。录取处理循环直至招聘额满或已对全部应聘者都作了录取处理。

程序中，类型 STU 包含有应聘者的基本信息：编号、成绩、志愿、排队成绩和录取志愿号。数组 rz[]的每个元素对应一个工种，包含有计划招聘人数和已录取的人数。
[程序]

#include

#define M 20

#define EDMARK 5

typedef struct stu {

int no, total, z[2], sortm, zi;

struct stu *next;

} STU;

struct rzmode {

int lmt , count;

STU *next;

} rz[M];

STU *head = NULL, *over = NULL;

Int all

FILE *fp;

char dataf [ ] = ＂pp07.dat＂;

print (STU *p)

{ for (;p!=NULL; p = p->next)

printf (＂%d(%d)\t＂, p->no, p->total);

}

insert(STU **p, STU *u)

{ STU *v, *q;

for (q = *p;q != NULL; v == q , ____(1)____)

if ( q-> sortm < u->sortm) break;

if ( q == *p) ___(2)____;

else ____(3)____;

u->next = q ;

}

main ( )

{ int zn, i, no, total, z1, z2 ;

STU *p, *v, *q;

fp = fopen(dataf,＂r＂);

if (fp == NULL)

{ printf (＂Can't open file %s.\n＂,dataf);

exit (0);

}

fscanf (fp,＂%d＂,&zn);

for (all = 0, i = 1; i <= zn; i++)

{ fscanf (fp, "%d", &rz [ i ].lmt );

rz[i].count = 0; rz[i].next = NULL;

all += ___(4)___;

}

for (;;)

{ if (( fscanf(fp,＂%d%d%d%d＂,&no,&total,&z1,&z2)) != 4 )

break;

p = ( STU *) malloc (sizeof (STU));

p->no = no;

p->total = p->sortm = total;

p->zi = 0; p->z[0] = z1; p->z[1] = z2;

____(5)____;

}

fclose (fp);

for (;all && head != NULL;)

{ p = head; head = head->next;

if (rz[p->z[p->zi]].count < ___(6)___)

{ rz[p->z[p->zi]].count ++;

insert( &rz[p->z[p->zi]].next,p);

all--;

continue;

}

if (p->zi >= 1 )

{ p->next = over; over = p;

continue;

}

p->sortm -= DEMARK; _____(7)_____;

insert( &head,p);

}

for ( i = 1; i <= zn; i++ )

{ printf(＂%d:\n＂,i);

print( rz[i ].next);

printf(＂\n＂);

}

printf(＂over:\n＂); print (head);

print(over); printf(＂\n＂);

}

试题八

阅读以下程序说明和 FORTRAN 程序，将应填入程序中 （n） 处的字句，写在答卷的对应栏内。
[程序说明]

某肉猪养殖场为了保证生猪质量,对每次配种种猪的祖先进行族谱代系分析,以选择无血缘关系或尽可能远的远亲种猪进行配种。

为了分析某个给定种猪的族谱代系，我们为该种猪及其每个祖先计算一个代系号，代系号的计算方法是：给定种猪自身的代系号为 1，父母的代系号为其子女代系号加 1。本题假定任一种猪的最大祖先代系号小于 20。

假定每只种猪有一能唯一标识的编号I( 1 < I < 100 ),数组元素PARENT(1，I)、PARENT(2，I)分别存放种猪I的双亲编号，当不知其某个双亲来源时，其相应的双亲编号为零。

函数 FINDLV 对给定的二只编号为 MA、MB 的种猪，查找它们是否至少存在一只相同的祖先。若存在，则返回相同祖先中最小的代系号；否则返回值为 100。程序中用数组 NOA、LEVA 存放 MA 的所有祖先编号及其相应的代系号，TOPA 为 MA 的祖先个数（含MA），数组NOB、LEVB存放MB的所有祖先编号及其相应的代系号，TOPB 为 MB 的祖先个数（含 MB）。

子程序 GF 将种猪编号 MAB 的所有祖先编号存放于数组 NO 中，将其相应的代系号存放于数组 LEV中。实现时，先将种猪编号 MAB 及代系号 1 分别存入 NO(1) 和 LEV(1) 中，然后按代系号由小到大的次序依次将其祖先（如有的话）的编号和代系号加入数组NO和LEV中，直到找遍所有的祖先。
[程序]

FUNCTION FINDLV(MA,MB)

INTEGER PARENT (2,100), FINDLV

INTEGER NOA(100), LEVA (100), TOPA

INTEGER NOB(100), LEVA (100),TOPB

COMMON PARENT

CALL GF (MA,NOA,LEVA,TOPA)

CALL GF (MB,NOB,LEVB,TOPB)

L = 100

DO 10 I =1,TOPA

DO 10 J =1, TOPB

IF (NOA(I).EQ.NOB(J))THEN

L = MIN (L,LEVA(I))

____(1)____

ENDIF

10  CONTINUE

____(2)____

RETURN

END

SUBROUTINE GF (MAB,NO,LEV,TOP)

INTEGER NO(100),LEV(100),PARENT(2,100),TOP,TOP1

___(3)___

TOP1=1

TOP=1

NO(TOP)=MAB

LEV(TOP)=1

10  IF(TOP1.LE.TOP) THEN

NOP=NO(TOP1)

L=LEV(TOP1)

TOP1=TOP1+1

DO 20 I=1,2

IF (____(4)____) THEN

TOP = TOP+!

NO(TOP)=___(5)___

LEV(TOP)=___(6)___

ENDIF

20     CONTINUE

_____(7)_____

ENDIF

RETURN

END

回目录                     老顽童校对整理 2002年8月