2001年度程序員級下午試題
試題一
閱讀下列程序或函數說明和 C 代碼,將應填入__(n)__處的字句寫在答題紙的對應欄內。
[函數1.1說明]
函數strcmp()是比較兩個字符串 s 和 t 的大小。若 s < t 函數返回負數;若 s = t 函數返回0;若 s > t,函數返回正數。
[函數1.1]
int strcmp(char *s,char *t)
{ while ( *s && *t && __(1)__){
    s++;t++ ;
    }
    return __(2)__;
}
[程序1.2說明]
在 n 行 n 列的矩陣中,每行都有最大的數,本程序求這 n 個最大數中的最小一個
[程序1.2]
#include〈stdio.h〉
#define N 100int a[N][N];
void main()
{ int row ,col ,max ,min ,n;
    /*輸入合法 n (〈100 ),和輸入 m n 個整數到數組 a 的代碼略*/
    for ( row = 0;row < n;row++) {
        for ( max = a[row][0],col = l ;col < n;col++)
            if (__(3)__) max = a[row][col];
        if (__(4)__) min = max;
        else if(__(5)__) min = max;
    }
    printf ("The min of max numbers is %d\n",min);
}
　
試題二
閱讀下列程序說明和C代碼,將應填入__(n)__處的字句寫在答題紙的對應欄內。
[程序2說明]
本程序中的函數 first_insert() 的功能是在已知鏈表的首表元之前插入一個指定值的表元;函數 reverse_copy() 的功能是按已知鏈表復制出一個新鏈表,但新鏈表的表元鏈接順序與已知鏈表的表元鏈接順序相反;函數 print_link() 用來輸出鏈表中各表元的值;函數 free_link()用來釋放鏈表全部表元空間。
[程序2〕
#include〈stdip.h〉
#include〈malloc.h〉
typedef 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 ("%d\t" , 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 stmct{char fnme[256];/*原始文件名*/
    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]
#include〈stdio.h〉
#include〈string.h〉
typedef struct{char fname[256];long length;long offset;}
        }FileInfo;
void copyfile( FILE *fin, FILE *fout, int fsiz)
{ char buf[1024]; 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 ( "創建文件錯誤: %s\n" , 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 fname[256] ; FILE *fcmbn;
    if (argc < 2) { printf( "輸入合并文件名:" ) ; scanf( "%s" , fname ) ; }
    else strcpy( fname,argv[1]) ;
    if ( ( fcmbn = fopen( fname , "rb" ) ) == NULL) {
        printf( "文件打開錯誤:%s\n" , 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 , argv[2] ) ) continue ;
        if ( dofile( fcmbn , &finfo ) != 0 ) break ;
    }
    fclose( fcmbn ) ; return 0 ;
}
　
試題四
閱讀下列程序說明和C代碼,將應填入__(n)__處的字句寫在答題紙的對應欄內。
[程序4說明]
設一個環上有編號為 0～n-1 的 n 粒不同顏色的珠子(每粒珠子顏色用字母表示, n 粒珠子顏色由輸入的字符串表示)。以環上某兩粒珠子間為斷點,從斷點一方按順時針方向取走連續同色的珠子,又從斷點另一方按逆時針方向對剩下珠子取走連續同色的珠子,兩者之和為該斷點可取走珠子的粒數。移動斷點,能取走的珠子數不盡相同。本程序找出可以取走最多的珠子數及斷點的位置。程序中用雙向鏈表存儲字符串。例如,編號為0-9的10粒珠子顏色的字符串為“aaabbbadcc",對應鏈表為:
    
若在2號與3號珠子間為斷點,共可取走6粒珠子,且為取走的珠子數最多。
[程序4]
#include〈stdio.h〉
#include〈string.h〉
#include〈malloc.h〉
typedef 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)__ ;
        }
    }
    return
}
int 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++
    }
    return
}
　
int 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 s[120] ;
    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} ,則有:
n	m	 程序運行后的輸出	
100	2	 100 = 100	
13	2	 13 = 9 + 4	
14	2	 No answer                   (9+4+1超過2個)	
71	5	 71 = 49 + 9 + 9 + 4         (表示可重復取數)	
　
函數 End()的形參 c 表示 d 中可取的整數個數;形參 pd 指向能成為和數的整數的存放位置。
[程序5]
#include〈stdio.h〉
#define N 20
int find( int n ,int m ,int *d ,int c ,int *pd )
{ int r ;
    if ( n == 0 ) return 0 ;  /* 已分解完成 */
    if ( n == 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 ) __(4)__ ;
        return find( n ,m , __(5)__ ,pd ) ;
     }
}
void main()
{ int n ,m ,k ,i ,p[N] ,*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 , p[0] ) ;
    for ( i = l ; i < k ; i++ )
        printf(" +%d" , p[i] ) ;
    printf("\n");
}