2001上半年程序员考试真题及答案-下午卷.doc
2001上半年程序员考试真题及答案-下午卷试题一阅读下列程序或函数说明和 C 代码,将应填入_(n)_处的字句写在答题纸的对应栏内。函数1.1说明函数strcmp()是比较两个字符串 s 和 t 的大小。若 s < t 函数返回负数;若 s = t 函数返回0;若 s > t,函数返回正数。函数1.1int strcmp(char *s,char *t) while ( *s && *t && _(1)_) s+;t+ ; return _(2)_;程序1.2说明在 n 行 n 列的矩阵中,每行都有最大的数,本程序求这 n 个最大数中的最小一个程序1.2#includestdio.h#define N 100int aNN;void main() int row ,col ,max ,min ,n; /*输入合法 n (100 ),和输入 m ×n 个整数到数组 a 的代码略*/ for ( row = 0;row < n;row+) for ( max = arow0,col = l ;col < n;col+) if (_(3)_) max = arowcol; if (_(4)_) min = max; else if(_(5)_) min = max; printf ("The min of max numbers is %dn",min);试题二阅读下列程序说明和C代码,将应填入_(n)_处的字句写在答题纸的对应栏内。程序2说明本程序中的函数 first_insert() 的功能是在已知链表的首表元之前插入一个指定值的表元;函数 reverse_copy() 的功能是按已知链表复制出一个新链表,但新链表的表元链接顺序与已知链表的表元链接顺序相反;函数 print_link() 用来输出链表中各表元的值;函数 free_link()用来释放链表全部表元空间。程序2#includestdip.h#includemalloc.htypedef struct node int val; struct node *next; NODE;void first_insert( NODE *p,int v) NODE *q = (NODE *) malloc( sizeof(NODE); q -> va1 = v;_(1)_; *p = _(2)_;NODE *reverse_copy(NODE *p) NODE *u; for( u = NULL ; p ; p = p ->next ) first_insert(_(3)_); return u;void print_link( NODE *p ) for( ;_(4)_) printf ("%dt" , p -> val); printf("n");void free_link(NODE*p) NODE *u; while( p != NULL) u=p-next;free( p );_(5)_;void main() NODE *link1 , *link2;int i ;linkl = NULL ;for( i = 1;i <= 10 ; i+ ) first insert( &link1,i );link2 = revere_ copy(link1);print_link(link1);freeJink(linkl);print_link(link2);free_link(link2);试题三阅读下列程序说明和C代码,将应填入_(n)_处的字句写在答题纸的对应栏内。程序3说明本程序从若干个原始文件合并成的合并文件中恢复出其中一个或全部原始文件。所有文件均作为二进制文件进行处理。合并文件中先顺序存储各原始文件,然后顺序存储各原始文件的控制信息,即文件名、文件长度和在合并文件中的位置(偏移量)。其结构为:typedef stmctchar fnme256;/*原始文件名*/ long length;/*原始文件长度(字节数)*/ long offset;/*原始文件在合并文件中的位置(偏移量)*/ FileInfo;在合并文件最后存储如下一个特殊的标志信息作为合并文件的结束标记: F11ek1fo EndF1ag="Combined File".0,_offset;其中_offset是第一个原始文件的控制信息在合并文件中的位置(偏移量)。启动本程序的命令行的格式是: 程序名 合并文件名原始文件名如果不指定原始文件名,默认恢复合并文件中的所有原始文件。程序中涉及的部分文件操作的库函数简要说明如下:int fread(void *buffer,int size,int count,FILE *fbin):从二进制文件流 fbin 中读取count块长度为size字节的数据块到buffer指向的存储区。返回值为实际读取的数据块数。int fwrite(void *buffer,int size,int count,FILE *fbin):各参数和返回值的意义与fread相同,但对文件进行写操作。int fseek(FILE *fbin,long offset,int position): 将文件流 fbin 的读/写位置以 position为基准移动offset字节。position的值可以是SEEK_SET(文件头),SEEK_CUR(当前位置),SEEK_END(文件尾);offset为正表示向文件尾方向移动,为负表示向文件头方向移动,为零表示到基准位置。long ftell(FILE *fbin): 返回文件流 fbin 的当前读/写位置(相对于文件头的偏移量)。上述偏移量均以字节为单位,即偏移字节数。 程序3#includestdio.h#includestring.htypedef structchar fname256;long length;long offset; FileInfo;void copyfile( FILE *fin, FILE *fout, int fsiz) char buf1024; int siz = 1024 ; while(fsiz != 0) /*每次复制siz个字节,直至复制完fsiz个字节*/ if ( siz > fsiz) _(1)_ ; fread( buf , 1 , siz , fin ) ; fwrite( buf , 1 , siz , fout ); fsiz = _(2)_; int dofile( FILE *fin , FileInfo *inp ) long offset ; FILE *fout ; if ( ( fout = fopen( inp -fname , "wb" ) ) = NULL) printf ( "创建文件错误: %sn" , inp -fname ); return 1 ; offset = _(3)_ ; /*保留合并文件读/写位置*/ fseek( _(4)_) ; /*定位于被恢复文件首*/ copyfile( fin , fout , inp -length ) ; fclose( fout ) ; printf( "n-文件名: %n 文件长: %1d.n " , inp -fname , inp -length ); _(5)_; /*恢复合并文件读/写位置*/ return 0 ;int main( int argc ,char *argv ) FileInfo finfo ; char fname256 ; FILE *fcmbn; if (argc < 2) printf( "输入合并文件名:" ) ; scanf( "%s" , fname ) ; else strcpy( fname,argv1) ; if ( ( fcmbn = fopen( fname , "rb" ) ) = NULL) printf( "文件打开错误:%sn" , fname ) ; return 1; fseek( fcmbn ,-sizeof(FileInfo),SEEK END);/*定位于合并文件末尾的标志信息*/ fread(&finfo,1,sizeof(FileInfo),fcmbn) ; if ( finfo.length !=0 | strcmp( finfo.fmane , "CombinedFile" ) ) printf( "指定的文件不是合法的合并文件n" ) ; fclose( fcmbn ) ; return 2 ; fseek(fcmbn,finfo.offset,SEEK_SET );/*定位于首个原始文件的控制信息*/ for ( ; ; ) /*恢复一个(argc > 2) 或全部 ( argc = 2 )原始文件*/ fread( &finfo , 1 , sizeof( FileInfo ) , fCmbn ) ; if ( finfo.length = 0 ) break ; if ( argc > 2 && strcmp( finfo.fname , argv2 ) ) continue ; if ( dofile( fcmbn , &finfo ) != 0 ) break ; fclose( fcmbn ) ; return 0 ;试题四阅读下列程序说明和C代码,将应填入_(n)_处的字句写在答题纸的对应栏内。程序4说明设一个环上有编号为 0n-1 的 n 粒不同颜色的珠子(每粒珠子颜色用字母表示, n 粒珠子颜色由输入的字符串表示)。以环上某两粒珠子间为断点,从断点一方按顺时针方向取走连续同色的珠子,又从断点另一方按逆时针方向对剩下珠子取走连续同色的珠子,两者之和为该断点可取走珠子的粒数。移动断点,能取走的珠子数不尽相同。本程序找出可以取走最多的珠子数及断点的位置。程序中用双向链表存储字符串。例如,编号为0-9的10粒珠子颜色的字符串为“aaabbbadcc",对应链表为: 若在2号与3号珠子间为断点,共可取走6粒珠子,且为取走的珠子数最多。程序4#includestdio.h#includestring.h#includemalloc.htypedef struct node char d ; struct node *fpt ; /*后继指针*/ struct node*bpt ; /*前趋指针*/ NODE ;NODE *building( char *s ) /*生成双向循环链表*/ NODE *p = NULL , *q ; while ( *s ) q = ( NODE * ) malloc( sizeof( NODE ) ) ; q -> ch = *s+ ; if ( p = NULL ) p = q -> fpt = q -> b t = q ; else p -> bpt -> fpt = q ; q -> fpt = p ; q -bpt = _(1)_; _(2)_ ; returnint count( NODE *start , int maxn ,int step ) /*求可取走珠子粒数*/ int color ,c ; NODE *p ; color = -1 ; C = 0 ; for ( p = start ; c <maxn ; p = step > O ? p -> fpt ; p -> bpt ) if ( color = -1 ) color = p -> ch ; else if (_(3)_) break ; c+ returnint find ( char *s ,int *cutpos ) /*寻找取走珠子数最多的断点和粒数*/ int i , c , cut , maxc = 0 ,1en = strlen(s) ; NODE *p ; if ( ( p = building(s) ) = NULL ) *cu1tpos = -1 ; return -1 ; i = 0 ; do c = count( p , 1en ,1 ) ; c = c + _(4)_ ; if ( c > maxc ) maxc = c ; cut = i ; _(5)_ ; i+ ; while (i < len ) ; * cutpos = cut ; return maxc ;void main() int cut , max ; char s120 ; scanf( , %s', s ) ; max = find( s , &cut ) ; printf ( "Cut position = %d , Number = %d.n" , cut , max ) ;试题五阅读下列程序说明和C代码,将应填入_(n)_处的字句写在答题纸的对应栏内。程序5说明本程序采用递归算法将一个自然数 n 分解成不多于 m 个整数之和。设构成和数 n 的各个整数取于数组 d ,d 中的整数互不相等且由大到小存储。例如,数组 d 中存储以下整数: d = 100 ,81 ,64 ,49 ,36 ,25 ,16 ,9 ,4 ,1 ,则有:nm 程序运行后的输出1002 100 = 100132 13 = 9 + 4142 No answer (9+4+1超过2个)715 71 = 49 + 9 + 9 + 4 (表示可重复取数)函数 End()的形参 c 表示 d 中可取的整数个数;形参 pd 指向能成为和数的整数的存放位置。程序5#includestdio.h#define N 20int find( int n ,int m ,int *d ,int c ,int *pd ) int r ; if ( n = 0 ) return 0 ; /* 已分解完成 */ if ( m = 0 | c = 0 ) return -1 ; /* 不可以分解 */ if ( _(1)_ ) return find( n ,m , d+1 ,c-1 ,pd ) ; else *pd = *d ; r = find( _(2)_ ,d , c , _(3)_ ) ; /* 继续对剩余数作分解 */ if ( r >= 0 ) return _(4)_ ; return find( n ,m , _(5)_ ,pd ) ; void main() int n ,m ,k ,i ,pN ,*pptr = p ; int d = 100, 81, 64, 49, 36, 25, 16, 9, 4, 1 ; printf( "Enter n , m : " ; scanf( %d %d ,&n ,&m ); k = find( n , m , d , 10 , pptr ) ; if ( k <= O ) printf ( "No answer!n" ) ; else printf( "%d = %d" , n , p0 ) ; for ( i = l ; i < k ; i+ ) printf(" +%d" , pi ) ; printf("n"); 参考答案试题一试题二(1) *s = *t(1) q ->ncxt = *p(2) *s - *t(2) q(3) arowcol > max (3) &u ,p->val(4) row = 0(4) p != NULL; p = p->next(5) max < min(5) p = u试题三试题四(1) siz = fsiz(1) p->bpt(2) fsiz-siz(2) p->bpt = q(3) ftell(fin)(3) p->ch != color(4) fin,inp->offset, SEEK_SET(4) eount(p-bpt,len-c,-1)(5) feesk(fin ,offset, SEEK_SET)(5) p = p->fpt试题五(1) n<*d(2) n-*d ,m-1(4) r+l(3) pd+1(5) d+1 ,c-1
