1997年度程序员级下午试题

试题一

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

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

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

（1，2，4，8）

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

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

# include <stdio>

# 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+k;

        }

    else {

      fac[c1++] = i;  

            s + = i;

        }

        i++;

        if(i>=k) brdak;

     }

    for (c2++;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)____

10  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

20    ____(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 (0 ≤i < r)。 

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

0 1 2，0 1 3，0 1 4，0 2 3，0 2 4，

0 3 4，1 2 3，1 2 4，1 3 4，2 3 4

产生组合的方法是：

* 对上一组合C₀，C₁，…C_r-1，自右端开始寻找可递增的Ci ;

* 递增C_i后仍满足C_i的性质，表示可以开成下一个组合，则递增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] = 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 = ____(3)____;j < r; j++)  /*完成一个组合*/

        ____(4)____

            for(j = 0;j < r; j++)  prihtf(“\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]上的一个正根。弦截法求方程F（x）=0的迭代公式如下：

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

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

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

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

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

则用xi+1代替xi-1；否则用xi+1代替xi。当

    |(x_i-x_i-1)* F（x_i ）/ ( F（x_i ）- F（x_i))| < ε

时，终止迭代，且此时的xi+1即为方程F（x）=0的近似解。在程序中取 为10-6，x0=0,x1=1。
[程序]

    ____(1)____

    x0=0.0

    x1=1.0

    RT=____(2)____

    WRITE(*,20) RT

20  FORMAT(1X,F10.6)

    END

    FUNCTIION ROOT(G,X,Y,EPS)

5   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和j，它们或直接组连，或间接相连（部件 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 parts.”);

  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，例如

[程序]

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)____

10          CONTINUE

   IF (S.GT.MAX) THEN

        MAX = S

        TOP=T

   ELSE

   IF (____(7)____) TOP=T

   ENDIF

20     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;c++)

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

        fprint(fp,”\n”);

      }

}

试题八

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

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

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

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

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

例如，原始数据如下：

    -14，-14，-14，2，3，5， -2，8，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 = .TRUE.

        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

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