1992年程序员级考试——下午试题

1.本程序采用筛选法求质数。程序用一个无符号整数数组代表筛，它的每一位对应一个整数。因除２以外，其

余所有的质数都是奇数，约定数组按位的顺序，依次对应整数３，５，７，９，１１。程序首先将数组所能容

纳的上述奇数放入筛中，即将数组的全部位置成１。从筛中找出最小的数，该数即为质数，然后将该质数的倍

数从筛中去掉，即将在数组中与它们对应的位置成０。因偶数不在筛中，去掉的数是找到的质数的1倍，3倍，

5倍……等整数。反复上述过程，直至筛为空。程序就能找到指定范围内的全部质数。

【程序】

　#include <stdio.h>

#define N 50

#define LN 16


main()

{

unsigned int sieve[N],primes[N];

unsigned int j,w,p,c;


for(j=0;j<N;j++)

{ sieve[j] =0xFFFFFFFF;

primes[j] =0x00;

}

w=0; j=0;

do { while (((0x01<< (j++)) & sieve[w]==0x00);

p=________;

c=________;

primes[w] |= (___________);

do

{ sieve[p/LN] &=(~(___________));

p+=c;

} while (p < N*LN-LN);

while ((sieve[w] == 0x00) && (w < N-1))

{ w++;

j=0;

}

} while (sieve[w]) ;


printf("%5d",2);

for(w=0;w<N;w++)

{ for(j=0;j<LN;j++)

if((0x01 << j) & primes[w])

printf("%5d",__________);

}

printf("\n");

}


　

　

2.　设有两整数向量 A, B 的比较矩阵M 可定义为:

┏ 1 a(j) > b(i),

m(i)(j) = ┃ -1 a(j) < b(i), (i,j=0,1,┄,n-1)

┗ 0 a(J) = b(I),

如图所示。

┌──┬───────────┐

│B＼A│ 8 9 4 6 2 4│

├──┼───────────┤

│ 3 │ 1 1 1 1 -1 1│

│ 7 │ 1 1 -1 -1 -1 -1│

│ 7 │ 1 1 -1 -1 -1 -1│

│ 5 │ 1 1 -1 1 -1 -1│

│ 3 │ 1 1 1 1 -1 1│

│ 8 │ 0 1 -1 -1 -1 -1│

└──┴───────────┘

(1) 本程序对给定的比较矩阵 M,确定满足 a(k)=x 条件的 A, B的一个整数解。

(2) 本程序的解法是: 读入 M,k,x后

1.填充A,B, 令b(i)=x-m(i)(k), a(i)=x (i=0,1,┄,n-1)

2.检查 a(j) 与b(i)是否满足 m(i)(j)

.若满足检查下一个;

.否则向上调整相应元素,并按以下约定回朔检查: 当B的第i个元*

素调整时,则回朔到A的第一个元素; 当A的第j个元素调整时,则*

回朔到A的当前元素和B的第一个元素.

本程序对比较矩阵M的合理性未作检查,并假定在指定的条件下一定能找到一个解。


【程序】

#include <stdio.h>

#define MN 20

typedef int Vector[MN];

Vector Matrix[MN];

int N;


main(argc,argv)

int argc; char **argv;

{ Vector a,b;

int i,j,x,k;

void PrintVector();

void FillVector();

FILE *fp,*fopen();


if ((fp=fopen(argv[argc-1],"r")) == NULL)

{ printf("Cannot open file %s\n",argv[argc-1]);

exit(1);

}

fscanf(fp,"%d",&N);

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

for(j=0;j<N;j++)

fscanf(fp,"%d",&Matrix[j]);

fscanf(fp,"%d%d",&k,&x);

fclose(fp);

FillVector(a,b,k,x);

printf("The Vector A is:\n");

PrintVector(a);

printf("The vector B is:\n");

PrintVector(b);

}

void PrintVector(v)

Vector v;

{ int i;

printf("[");

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

printf("%5d",v);

printf("]\n");

}

void FillVector(a,b,k,x)

Vector a,b;

int k,x;

{ int i,j,temp;


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

{ b=x-Matrix[k];

a=x;

}

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

{ for(j=0;j<N;j++)

{ Temp=b+Matrix[j];

if (Matrix[j]==1 && Temp > a[j])

{ _________; i=0;}

else if(Matrix[j]==-1 && Temp < a[j])

{ b=a[j]+1; _________ ; }

else if( a[j]>b )

{ b=a[j] ; ________ ; }

else if( a[j] < b )

{ __________ ; __________ ; }

}

}

}


　

　

3. 本子程序利用递归法判别用链表表示的两个非递归链表是否相等.

程序中的非递归列表定义为:

(1) 无元素的空列表;

(2) 由元素序列组成的一个列表,其中的元素可以是一个字符,或者是满足本定*

义的一个列表.

这种列表的一个例子是:

　　Ｓ

┌───┐ ┌─┬─┬─┐ ┌─┬─┬─┐

│ ├→┤０│ａ│ ├→┤１│││＾│

└───┘ └─┴─┴─┘ └─┴┼┴─┘

┌─────┘

│ ┌─┬─┬─┐ ┌─┬─┬─┐

└→┤０│ｂ│ ├→┤０│ｃ│＾│

└─┴─┴─┘ └─┴─┴─┘


列表S由两个元素组成,第一个元素是字符a (标志为0),第二个元素是另一个列*

表(标志为1),该元素又有两个元素组成(标志为0),分别为字符b和字符c.

在两个列表中,若它们的元素个数相等,且表中元素依次相同,则两个列表相等(*

子程序回答1),否则不相等(子程序回答0).


　【程序】

typedef struct lnode

{ int tag;

union

{ char data;

struct lnode *dlink;

} un;

struct lnode *link;

} listnode;

int equal(s,t)

listnode *s,*t;

{ int x,res;


if(s==t)

__________ ;

else if( _________ )

if( _________ )

{ if(!s->tag)

x= ___________ ;

else

x= ___________ ;

if(x) return (_________);

}

return(0);

}

原文转自：http://www.ltesting.net