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.kjueaiud.com