電子情報4年情報構造論99年前期期末試験

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

1.再帰呼び出しの追跡

以下のプログラムの実行結果を示せ。

	#include <stdio.h>
	int  data[ 5 ] = { 2 , 8 , 5 , 9 , 3 } ;
	int  next[ 5 ] = { 4 , 3 , 1 ,-1 , 2 } ;
	void printAll( int p )
	{
	    if ( p != -1 ) {
	        printf( "%d\n" , data[ p ] ) ;
	        printAll( next[ p ] ) ;
	    }
	}
	void main()
	{
	    printAll( 0 ) ;
	}

2.リスト処理基本

座標 (x , y) のリスト構造を扱うプログラムを作成した。

	#include <stdio.h>
	struct XYList {
	    int            x , y ;
	    struct XYList* next ;
	} ;
	struct consXY( int xx , int yy , struct XYList* nx )
	{
	    struct XYList* n ;
	    n = (struct XYList*)malloc(                ) ;
	    if ( n != NULL ) {          ~~~~~~~~~~~~~~(A)
	        n->x = xx ;
	        n->y = yy ;
	        n->next = nx ;
	    }
	    return n ;
	}
	void printXY( struct XYList* p )
	{
	    for( /* */ ; p != NULL ; p = p->next )
	        printf( "(%d,%d)\n" , p-> , p->y ) ;
	}
	void main()
	{
	    struct XYList* list ;
	    list = consXY( 10 , 20 ,
	            consXY( -5 , 5 ,
	             consXY( 200 , 100 , NULL ) ) ) ; /* (B) */
	    printXY( list ) ;
	}

1. 下線部 (A) にふさわしい式を埋めよ。
2. 式 (B) の実行結果のイメージを図を用いて解りやすく示せ。
3. (x,y)座標のリスト構造の中から、 原点からの距離が n 未満の座標だけを選んで 表示したい。その処理を行う関数 void print_R_lt_N( struct XYList* p , int n ) を作成せよ。

3.再帰方程式

次のような再帰処理を含む関数がある。

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

1. foo( 4 ) を実行した場合の、関数の戻り値を答えよ。
2. この関数の処理速度 T_foo(n)を予測したい。 処理速度にふさわしい再帰方程式を示せ。
3. 再帰方程式を解いて、処理速度の一般式を示せ。 (厳密な証明でなくても可)
   ヒント：n = 2^m の場合から予測は可能となる。

4.リスト処理の応用例

	#include <stdio.h>
	struct List {
	    int          data ;
	    struct List* next ;
	} ;
	void printList( struct List* p )
	{
	    for( /* nothing */ ; p != NULL ; p = p->next )
	        printf( "%d " , p->data ) ;
	    printf( "\n" ) ;
	}
	struct List* cons( int x , struct List* n )
	{
	    struct List* new ;
	    new = (struct List*)malloc( sizeof( struct List ) ) ;
	    if ( new != NULL ) {
	        new->data = x ;
	        new->next = n ;
	    }
	    return new ;
	}
	struct List* bar( struct List* p )
	{
	    struct List* r = NULL ;
	    for( /* nothing */ ; p != NULL ; p = p->next )
	        r = cons( p->data , r ) ;
	    return r ;
	}
	void main()
	{
	    struct List* top = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
	    struct List* rev = bar( top ) ;
	    printList( rev ) ;
	}

1. このプログラムの bar( top )を実行した後の、rev の内容のイメージ図を示せ。
2. 最終的に出力されるデータを示せ。

5.処理速度の予測

アルゴリズム	オーダ	N=100
アルゴリズム1	O(2n)	T1(100) = 10 [msec]
アルゴリズム2	O(n2)	T2(100) = 20 [msec]
アルゴリズム3	O(n log n)	T3(100) = 30 [msec]

1. アルゴリズム1 のプログラムで、データ件数 110 件において、 処理時間は何秒かかるか？
2. アルゴリズム3 のプログラムで、データ件数 1000 件において、 処理時間は何秒かかるか？
3. アルゴリズム2,3 を比較して、データ件数が 何件以上であれば、 どちらのアルゴリズムを採用すべきか、式を使って説明せよ。

6.再帰方程式と再帰的帰納法による証明

N 枚の積み重ねられた disk を 3 本の塔を使って移動する、 ハノイの塔において、disk の移動回数を再帰的帰納法を用いて 証明せよ。