電子情報４年情報構造論96年度前期中間試験

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

すべての大きな設問の中から、５題以上について回答せよ。
採点は、各設問毎に行ない点数の高いものから５題について評価する。

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

1.文法(ド・基礎)

	#include <stdio.h>

	int  d ;

	void rot_swap( int* px , int* py , int* pz )
	{
	    int tmp = *px ;
	    *px = *py ; *py = *pz ; *px = tmp ;
	}

	int  foo()
	{
	    int  a = d ;
	    d = d + 3 ;
	    return a ;
	}

	void main()
	{
	    int  a = 1 , b = 23 , c = 456 ;
	    d = 123 ;
	    b = foo() ;
	    printf( "%d %d %d %d\n" , a , b , c , d ) ;
	    rot_swap( &a , &b , &c ) ;
	    printf( "%d %d %d %d\n" , a , b , c , d ) ;
	}

2.ポインタ(基礎)

次のプログラムの実行結果を回答せよ。 
	#include <stdio.h>

	#define SIZE  10
	char  my_atox_tmp[ SIZE ] ;

	char* my_atox( unsigned x )
	{
	    char* hex = "0123456789ABCDEF" ;
	    char* pc ;
	    pc = my_atox_tmp + SIZE - 1 ;
	    *pc = '\0' ;
	    for( /* nothing */ ; x != 0 ; x /= 16 ) {
	        unsigned  d = x % 16 ;
	        pc-- ;
	        *pc = hex[ d ] ;
	    }
	    return  pc ;
	}

	void main()
	{
	    printf( "%s" , my_atox( 123 ) ) ;  /* Answer ________ */
	}

3.構造体(応用)

回転角度 θ と、10個の座標列 (x,y) と入力し、 次式の回転移動を加えた結果の座標列 (X,Y) を出力したい。 関数 rotate() を作成せよ。

ただし、関数 sin(),cos() を使用すること。 

	#include <stdio.h>
	#include <math.h>

	struct  Point {
	    float  x ;
	    float  y ;
	} ;

	void  rotate( _______________ )
	{
	    /* この部分を作成せよ */
	}

	int   main( int argc , char** argv )
	{
	    int           i ;
	    float         theta ;
	    struct Point  points[ 30 ] ;

	    scanf( "%f" , &theta ) ;
	    for( i = 0 ; i < 10 ; i++ )
	        scanf( "%f %f" , &points[ i ].x , &points[ i ].y ) ;
	    rotate( theta , points ) ;
	    for( i = 0 ; i < 10 ; i++ )
	        printf( "%f %f" , points[ i ].x , points[ i ].y ) ;
	}

4.再帰(応用)

次の関数 gcd(x,y) は、ユークリッドの互除法を再帰によって 記述したものである。この関数と、同じ結果が得られる関数を、 再帰を用いずループ(while,for等)によって記述せよ。 

	#include <stdio.h>

	int gcd( int x , int y )
	{
	    if ( x == 0 )
	        return y ;
	    else if ( x > y )
	        return gcd( x % y , y ) ;
	    else
	        return gcd( y % x , x ) ;
	}

	void main()
	{
	    printf( "%d\n" , gcd( 24 , 100 ) ) ; /* 4 が表示される */
	}

5.文字列処理(ポインタ)

ポインタで渡される文字列の中に、同じ文字が含まれるかどうかを 判別する関数 isUniq() を作成せよ。

同じ文字が一切含まれない時、TRUE(非0)、含まれる場合 FALSE(0)を返すこと。 

	#include <stdio.h>

	int  isUniq( char* str )
	{
	    /* この部分を作成せよ */
	}

	void main()
	{
	    /* 0を表示(i,s,a,空白が複数回含まれる) */
	    printf( "%d\n" , isUniq( "this is Japan." ) ) ;
	    /* 1を表示 */
	    printf( "\n" , isUniq( "aceghIjLnbdf" ) ) ;
	}

6.再帰方程式(応用)

次の関数 foo() は、引数 n の値によって処理速度が 変化する。そこで、処理速度のオーダ O(n) を求めたい。

ヒント： 

	int foo( int n )
	{
	    if ( n == 1 ) {
	        return 1 ;
	    } else {
	        int  i , j , sum ;
	        sum = foo( n - 1 ) ;
	        for( i = 0 ; i < n ; i++ )
	            for( j = 0 ; j < n ; j++ )
	                sum++ ;
	        return sum ;
	    }
	}

7.再帰(応用)

	#include <stdio.h>

	int   stack[ 30 ] ;
	int   sp = 0 ;

	void  foo()
	{
	   if ( stack[ sp - 1 ] <= 2 ) {
	      stack[ sp - 1 ] = 1 ;
	   } else {
	      stack[ sp ] = stack[ sp - 1 ] - 1 ;
	      sp++ ;
	      foo() ;
	      stack[ sp ] = stack[ sp - 2 ] - 2 ;
	      sp++ ;
	      foo() ;
	      sp -= 2 ;
	      stack[ sp - 1 ] = stack[ sp ] + stack[ sp + 1 ] ;
	   }
	}

	int   main( int argc , char** argv )
	{
	   stack[ sp++ ] = 4 ;
	   foo() ;
	   printf( "%d\n" , stack[ --sp ] ) ;
	}
上記プログラムで