一九九七年度程序员级下午试题(佚名)

回目录
 回首页

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

试题一

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

[程序说明]

本程序中的函数factor(m,fac,cp)用来计算正整m(m>2)的除自身以外的所有不同因子的和。该函数返回因子和，并把各因子从小到大依次存放在数组fac中，其因子个数存入在cp所指的变量中。

例如 m=16,求得的因子为

（1，2，4，8）

因子和为15，因子个数为4。

程序假定正整数m的不同因子个数不会超过100个。

[程序]

# include <stdio.h>

# define N 100

long factor(int m,int fac[],int * cp)

{

int c1, c2 , i, k;

long s;

fac[0]=1;

for(c1=s=1,c2=N-1,____(1)____;;)

{

k=m/i;

if(____(2)____)

if(____(3)____

{ fac[c1++]=i

fac[c2--]=k;

s +=i;

}

i++

if(i>k)brdak;

}

for9c2++;c2<=N-1;c2++)

____(4)____;

*cp=c1;

return____(5)____;

}

试题二

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

[程序说明]

函数FACTOR（M，FAC，L）用来计算正整数M（M>2）的除自身以外的所有不同因子之各，该函数值返回因子和，并把M的各因子从小到大依次存放在数组FAC中，其因子个数存放在L中。

例如：M=16 ，其因子之和为15（1+2+4+8），因子个数为4。本程序假定正整数M的因子个数不会超过100个。

[程序]

FUNCTION FACTOR(M,FAC,L)

INTEGER FAC(100),FACTOR,S,R

FAC(1)=1

L=1

R=100

S=1

____(1)____

K=M/I

IF(____(2)____)THEN

IF(____(3)____)THEN

L=L+1

FAC(L)=I

FAC(R)=K

R=R-1

S=S+1

FAC(L)=I

ENDIF

ENDIF

I=I+1

IF(I.LT.K)GOTO 10

DO 20 I=R+1,100

____(4)____

L=L+100-R

____(5)____

END

　

试题三

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

[程序说明]

本程序列举从整数0至n-1中任取r个整数的所有组合。设求得组合中的各数分别存储于数据组C的C₀,C₁……C_r-1中，并假定C₀<C₁<…<C_r-1,则C_i有性质C_i<n-r+i(o<i<r)。

如设n=5,r=3,则i<2+i(0<i<3)。由初始组合0，1，2开始，可心依次产生以下组合序列：

012，013，014，023，024，034，123，124，134，234

产生组合的方法是：

对上一组合C₀，C₁，…C_r-1，自右端开始递增的C_i;

递增C_i后仍满足_Ci的性质，表示可以开成下一个组合，则递增C_i，并顺序生成C_i+1至C_r-1;

递增C_i后不满足C_i的性质，则回溯；

直至i减至小于0为止。

[程序]

# include <stdio.h>

#define N 100

void enumall(int n,int r)

{ int i, j, c[N];

for(j=-0;j<r;j++) c[j]/*开成初始组合*/

for(j=0;j<r;j++) printf(“\t%d”,c[j]);

printf(“\n”);

i=____(1)____;

do{if(____(2)____)/*如调整c[i]是可接受的*/

{ c[i]++; /*递增c[i]*/

for(j=0;j<r;j++) printf(“\t%d”,c[j]);

prihtf(“\n”);

____(5)____

}

else____(6)____;/*回溯*/

}while(____(7)____;

}

main()

{int,n, r;

do{printf(“Enter n, r:\n”);

scanf(%d %d,%n,%r);

} while(n<r);

enumall(n,r);

}

试题四

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

[程序说明]

本程序用弦截法求方程

5^x-x²-2=0

在区间[0.0,1.0]上的一个正报。弦截法求方程（x）=0的迭代公式如下：

xi+1=xi- F（x_i） (i=1,2,3…)

迭代的初值为x₀和x₁,并且满足

F（x₀）*F(x_i)<0

然后用迭代公式，由x_i-1和x_i计算x_i=1。若

F（xi-1）*F(xi+1)>0

则用x_i+1代替x_i-1;否则用x_i+1代替x_i。当

时，终止迭代，且此时的x_i+1即为方程F（x）=0的近似解。在程序中取为10^-6，x₀=0,x₁=1。

[程序]

____(1)____

x0=0.0

x1=1.0

RT=____(2)____

WRITE(*,20) RT

FORMAT(1X,F10.6)

END

　

FUNCTIION ROOT(G,X,Y,EPS)

T=(Y-X)*G(Y)/(G(Y)-G(X))

IF(____(3)____)THEN

Z=Y-T

IF(G(X)*G(y)/(G(Y0-G(x))

____(4)____

ELSE

____(5)____

ENDIF

____(6)____

ENDIF

____(7)____

END

FUNCTION F(X)

F=5**X-X*X-2

END

　

　

试题五

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

[程序说明]

某系统由n个部件组成，这些部件被物理地分成若干个分离的部件组。同一组内的两件部件i和f，它们或直接组连，或间接相连（部件i和部j间接相连是指在这两件部件之间有一个部件相连序列，其中部件i和j分别与这相连序列中的某个部件直接相连）。系统的n个部件被统一编号为0，1，…，n-1。本程序输入所有直接相连的部件号对，分别求出系统各分离部件组中的部件号并输出。

程序根据输入的直接相连的两件部件号，建立n个链表，其中第i个链表的首指针为s[i]，其结点是与部件号i直接相连的所有部件号。

程序按下述方法顺序处理各链表。设处理第i个链表，将该链表移至由指针top所指的工作链表。对top链表的各结点作如下处理：从top链表上取出一个结点，根据该结点所指出的相连部件j，将第j个链表也移入top链表中，并将所取出的结点按部件号从小到大的顺序重新构造第i个链表（该链表中只保留不相同的结点），如此重复，直至top链表为空，第i个链表的重新构造也结束。所有链表处理完毕后，重新构造好的各非空链表即对应系统中的一个部件组。

[程序]

# include <stdio.h>

# define N 100

typedef 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 prarts.”);

scanf(“%d”,&n);

for(i=0;i<n;i++)s[i]=NULL;

printf(“Enter pairs.\n”);

while(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],s[i]=NULL;____(1)____;)

{/*将第i链表移入top工作链表，并顺序处理工作链表的各结点 */

q=top;____(2)____;

if(s[j=q->data]!=NULL)

{/*将j链表也移入工作链表*/

for(p=s[j];____(3)____;p=p->link);

p->link=top; top=s[j];____(4)____;

}

/*在重新生成的第i链表中寻找当前结点的插入点*/

for(y=s[i]____(5)____;x=y,y=y->link);

if (y!=NULL && y->data= = q->data)

free(q);/*因重新生成的第i链表已有当前结点，当前结点删除*/

else {/*当前结点插入新生成的第i链表*/

____(6)____;

if (____(7)____ s[i]=q;

else x->link=q;

}

for(i=0;i<0;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)__处的字句，写在答卷的对应栏内。

[程序说明]

子程序MS对N阶方阵A中的与次（副）对角线平行的各条斜线（共有2N-1条）上的元素进行累加和比较，求出累加和的最大值MAX，以及具有最在值的斜线上的最大元素TOP，例如

A=		MAX=10 TOP=6

[程序]

SUBROUTINE MS（A，N，MAX，TOP）

REAL MAX，A（N，N）

MAX=A（1，1）

TOP=A（1，1）

DO 20 K=____(1)____

IF(K.E.N)THEN

IBEG=K

IEND=1

JBEG=1

ELSE

IBEG=____(2)____

IEND=____(3)____

JBEG=____(4)____

ENDIF

J=JBEG

____(5)____

T=Az(IBEG,JBEG)

DO 10 I=IBEG,IEND,-1

S=S+A(I,J)

IF(A(I,J) .GT.T) T=A(I,J)

____(6)____

CONTINUE

IF(S.GT.MAX) THEN

MAX=S

TOP=T

ELSE

IF(____(7)____)TOP=T

ENDIF

CONTINUE

RETURN

END

　

试题七

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

[程序说明]

有些非负整数文件中存在许多边续相等的整数段。设计函数packed( )将这种整数原文件按以下规则压缩存储到另一个压缩文件中：

一个连续相等的整数段，如有C（>1）个边续相等整数，在压缩文件中存入C和这个整数。

一个不连续相等的整数段，如有C（C>1）个整数，其中每个整数都与其相邻的整数不等，在压缩文件中存入-C和这个C个整数。

例如，原文件为

2 2 2 4 4 4 8 3 8 1 1 1 1 2 2 1

则它的压缩文件为

3 2 3 4 –3 8 3 8 4 1 –2 2 1

函数packed（）把从原文件读入的整数暂存于数组buf中，对连续相等的整数段只保存一个整数。当发现一个连续相等整数段或一个不边续相等整数段结束时，就将该整数段按压缩规则存入压缩文件。函数为了防止不连续相等整数太长，当发现不连续相等整数段已有N（N=100）个整数时，先将其中前（N-2）个整数按压缩规则存入压缩文件。

[程序]

# include <stdio.h>

# define N

char rfname[]=”pp071.dat”,wf name[]=”pp072.dat”:

main()

{FILE* rfp,* wfp;

if ((rfp=fopen(rfname,”r”))= =NULL)

{ printf (“Can’t open file %s.\n”,rfname);

exit(1);

}

wfp=fopen(wfname,”w”);

packed(wfp,rfp);

fclose(wfp_; fclose(rfp);

printf(“The program has finished.\n”);

}

packed (FILE*wfp,FILE *rfp)

{int buf(N),pos,c,pstatus,cstatus;

c =0; /* c:当前整数段已读入的整数个数*/

pos =0: /* pos:下一个读入整数在buf中的存放位置*/

while(fscanf(rfp,”%d”,buf+pos)= = 1)

{ if (c= =0)

{c=pos=1:continue:/*buf中只有一个数*/

}

if (c= =1)

{ /*buf中已有两个数，建立已读入的两个数的相等与否状态*/

pstatus=buf[0]= =buf[1];

pos=____(1)____;/*设定下一个输入数在buf中的位置*/

c =2; /*设置当前整数段已读入的整个数*/

continue;

}

cstatus=____(2)____;/*建立最后两个数的相等与否状态*/

if (pstatus && ! cstatus)

{ /*连续相等整数段结束*/

pop(pstatus,buf,c,wfp);

____(3)____;c=pos=1;pstatus=cstatus;

}

else if (!pstatus && cstatus || pos= =cstatus;

{/*不连续相等整数段已结束或已满N个*/

pop(____(4)____);

____(5)____; c=2;

if(!cstatus)

{ /*不连续相等整数段尚未结束*/

____(6)____;pos=2;

}else

{/* 不连续相等速数段已结束*/

____(7)____;pstatus=cstatus;

}

}else{ /*一个整数段还未结束*/

c++; if (!pstatus)pos++;

}

if(c>0) pop (pstatus,buf,c,wfp); /*最后一个整数段的处理*？

}

pop(int s,int *b,int c,FILE* fp)

{/*一个整数段以压缩形式存入压缩文件*/

int i;

if(s)fprintf(fp,”%d %d\n”,c, *b);

else {fprintf(fp,”%d”,-c);

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

fprintf(fp,”%d”,-C);

rprint(fp,”\n”);

}

试题八

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

[程序说明]

为减少存贮空间或数据通信中的信息量，经常需要对原始数据进行压缩。下面给出一种数据压缩规则：

当原始数据中连续出现N（N>1）个相同的数X时，则在压缩数据中相继存放N和X两个数

当原始数据中连续出现M(M>0)个相邻不同的数（即每个数与其相邻的数均不相同）时，则在压缩数据中先存放-M，再存放这M个相邻不同的数。

在压缩数据中，数据次序与原始数据中数的出现次序相一对敌，并在压缩数据的最后加上0，作为结束标志。

例如，原始数据如下：

-14，-14，-14，2，3，5， -Z，8，8，8，8，-6，5，7，12，19，25

压缩后的数据为：

3，-14，-4，2，3，5，-2，5，8，-6，-6，5，7，12，19，25，0

子程序PACK用来压缩原始数据，并求出压缩后数据的数目。程序中数组X存放L个原始数据，数组Y存放压缩后的数据（假定Y中数据数目不超过1000）。子程序POP根据参数SAME之逻辑值将X中一组连续出现的数据或一组相邻不同的数据以压缩方式存入在数组Y中。

　

[程序]

　

SUBROUTINE PACK（X，Y，L，NUM）

INTEGER X（L），Y（1000）

LOGICAL SAME，F

COMMON BUF（50）

BUF（1）=X（1）

N=1

NUM=0

SAME=X（1） EQ .X(2)

I=2

IF(____(1)____THEN

F=X(I-1) EQ X(I)

IF(____(2)____.AND..NOT.F) THEN

CALL POP(SAME,N,Y,L,NUM)

N=0

IF(I,LT,L)THEN

SAME=X(I).EQ.X(I=1)

ENDIF

ELSE

IF(____(3)____.AND.F)THEN

CALL POP(SAME,N-1,Y,L,NUM)

BUF(1)=X(I)

N=1

SAME=.RUE.

ENDIF

ENDIF

N=N+1

BUF(N)=____(4)____

I=I+1

____(5)____

ENDIF

CALL POP(SAME,N,Y,L,NUM,)

NUM=NUM+1

____(6)____

END

　

SUBROUTINE POP)SAME,N,Y,L,NUM)

INTEGER Y(1000)

LOGICAL SAME

COMMON BUF(50)

IF(____(7)____)THEN

Y(NUM+1)=N

Y(NUM+2)=BUF(1)

NUM=NUM+2

ELSE

Y(NUM+1)=-N

DO 10 J=1,N

Y(NUM+1+J)=BUF(J)

NUM=NUM+N+1

ENDIF

END

回目录
 回首页