電子情報４年情報構造論99年度後期期末試験

教科書・ノート持ち込み不可。
解答に使用するプログラム言語は、問題の趣旨に沿っていれば何を用いても良い。 解答を裏に書く場合、どの設問に対する答か解るようにすること。
以下の８題の中から，５つを選んで解答せよ．

５題よりより多く回答されている場合は、点数の 1/3 で加算する。

1.文法・型・ポインタの理解確認

1.1以下の実行結果を示せ。

	#include <stdio.h>
	int z = 20 ;
	~~~~~~~~~~~~A
	void foo( int x )
	{         ~~~~~B
	    static int z = 0 ;
	    ~~~~~~~~~~~~~~~~~~C
	    z += x ;
	    printf( "%d\n" , z ) ;
	}
	void bar( int x )
	{
	    int z = 10 ;
	    ~~~~~~~~~~~~D
	    z += x ;
	    printf( "%d\n" , z ) ;
	}
	void swap( int* px , int* py )
	{
	    int  tmp = *px ;
	    *px = *py ;
	    *py = tmp ;
	}
	void main()
	{
	    int x = 4 ;
	    foo( 3 ) ;
	    bar( 4 ) ;
	    printf( "%d %d\n" , x , z ) ;
	    bar( 5 ) ;
	    foo( 6 ) ;
	    swap( &x , &z ) ;
	    printf( "%d %d\n" , x , z ) ;
	}
	

1.2文法の理解確認

1. もし文法が間違っていれば、『エラー』と示し理由を示せ。
2. 正しい文法であれば、printf() の行についてはその実行結果を示し、 下線部があれば『そのデータの型』について述べよ。

	int  a[ 4 ] = { 11 , 22 , 33 , 44 } ;
	char str[ 8 ] = "AbCdEfG" ;
	char *pc ;
	int  *px ;

	px = a ;
	px++ ;
	printf( "%d\n" , *px ) ;           /* A */

	pc = str + 3 ;                     /* B */
	     ~~~~~~~
	printf( "%c\n" , *pc + 1 ) ;       /* C */
	                 ~~~
	px = &( a[ 2 ] ) ;                 /* D */
	        ~~~~~~
	printf( "%d\n" , (px + 1)[ 1 ] ) ; /* E */
	                 ~~~~~~~~
	printf( "%d\n" , *( px[0] ) ) ;    /* F */
	                    ~~~~~
	

1.3説明問題

1. 設問1.1の中のA-Dまでの変数宣言について、 その寿命やスコープについての用語を使って具体的に説明せよ。
2. 閉じたサブルーチンについて説明し、利点・欠点を述べよ。

2.文字列処理

	#include <stdio.h>
	int count( char* s1 , char* s2 ) {
	    /* この部分を作成せよ */
	}
	void main() {
	    printf( "%d\n" ,  /* 4 が表示されて欲しい */
	            count( "this is a pen" , "is" ) ) ;
	                      ~~ ~~
	    printf( "%d\n" ,  /* 3 が表示されて欲しい */
	            count( "that is a pencil" , "an" ) ) ;
	}                     ~     ~   ~
	

3.構造体の利用(複素数)

	#include <stdio.h>
	struct Complex { /* 複素数(直交座標系) */
	    double  re ; /* 実数部 */
	    double  im ; /* 虚数部 */
	} ;
	void add( struct Complex *pz , struct Complex *px , struct Complex *py )
	{
	    pz->re = px->re + py->re ;
	    pz->im = px->im + py->im ;
	}
	void mul( ________ )
	{
	    /* 仮引数の宣言と処理の内容を作成せよ */
	}
	void print( struct Complex *pz )
	{
	    printf( "%f+j*%f\n" , pz->re , pz->im ) ;
	}
	void main()
	{
	    struct Complex  x = { 1 , 2 } , y = { 2 , 2 } , z ;
	    add( &z , &x , &y ) ;  print( &z ) ;
	    mul( &z , &x , &y ) ;  print( &z ) ;  /* 複素数の乗算をしたい */
	}
	

4.ヒープを使ったプログラム

1. 配列は、データのポインタと、 記憶しているデータ件数と、 実際の配列の大きさにより管理する。
2. 最初は、適当な大きさの配列を malloc() で確保しておく。
3. 配列にデータを追加する場合、 データ件数が実際の配列の大きさを越えた場合、 次のような処理で新たなデータを記憶できるようにする。
   • ２倍の大きさの配列を新しく malloc() で確保する。
   • 新しく確保した配列に、前の配列の中身をすべてコピーする。
   • 不要になった前の配列は、free() で廃棄する。

	#include <stdio.h>
	#include <stdlib.h>
	int *array ;  /* 配列の記憶場所のポインタ */
	int volume ;  /* 配列に記憶しているデータ件数 */
	int size ;    /* 配列の本当の大きさ */
	void main() {
	    int  i , x ;

	    size = 6 ;  /* 適当な配列の初期サイズ */
	    array = (int*)malloc( sizeof(int) * size ) ;
	    volume = 0 ;
	
	    while( scanf( "%d" , &x ) == 1 ) {
	        array[ volume ] = x ; /* 末尾にデータを追加 */
	        volume++ ;            /* データ件数を増やす */
	        if ( volume >= size ) {
	            /* 配列の大きさが足りなくなった */
	            int  j , *n_array ;
	            n_array = ________________________________ ;
	            if ( n_array == ______ ) {
	                printf( "ヒープメモリが不足してます\n" ) ;
	                break ;
	            }
	            for( j = 0 ; __________ ; j++ )
	                ___________________________
	            free( array ) ;
	            array = _________ ;
	            size  = _________ ;
	        }
	    }
	    for( i = 0 ; i < volume ; i++ ) /* 配列を全部印刷 */
	        printf( "a[%d] = %d\n" , i , array[i] ) ;
	}
	

5.プログラムの実行

	#include <stdio.h>
	char opStack[ 100 ] ;   int opSp  = 0 ;
	int  valStack[ 100 ] ;  int valSp = 0 ;
	void pushOp( char c )
	{
	    opStack[ opSp ] = c ;
	    opSp++ ;              /*--------------------------------*/ 
	}                         /*  プログラムの実行結果を示せ!!  */
	int popOp()               /*--------------------------------*/ 
	{
	    if ( opSp > 0 ) {
	        opSp-- ;
	        return opStack[ opSp ] ;
	    } else
	        return -1 ; /* 演算子が空なら-1を返す */
	}
	void pushValue( int x )
	{
	    valStack[ valSp ] = x ;
	    valSp++ ;
	}
	int popValue()
	{
	    valSp-- ;
	    return valStack[ valSp ] ;
	}
	int eval()
	{
	    char c ;   int x ;
	    while( (c = popOp()) >= 0 ) {
	        switch( c ) {
	        case '+' : pushValue( popValue() + popValue() ) ;
	                   break ;
	        case '*' : pushValue( popValue() * popValue() ) ;
	                   break ;
	        }
	    }
	    return popValue() ;
	}
	void main()
	{
	    pushValue( 2 ) ; pushValue( 3 ) ; pushValue( 4 ) ;
	    pushOp( '+' ) ;  pushOp( '*' ) ;
	    printf( "%d\n" , eval() ) ; /* 何が表示される？ */
	}
	

6.さらなる応用

	    /* 前問題 eval() の swith 文の'*'の処理の次に追加 */
	    case '!' : x = popValue() ;
	               if ( x <= 1 ) {
	                   pushValue( 1 ) ;
	               } else {
	                   pushOp( '*' ) ;
	                   pushValue( x ) ;
	                   pushOp( '!' ) ;
	                   pushOp( '+' ) ;
	                   pushValue( x ) ;
	                   pushValue( -1 ) ;
	               }
	               break ;
	

	void main()
	{
	    pushValue( 3 ) ; pushOp( '!' ) ;
	    printf( "%d\n" , eval() ) ;
	}