電子情報４年情報構造論98年度前期期末試験

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

1.データの追加での配列とリストの比較(必須)

データを昇順(小さいものから大きな順)に並べてデータを管理したい。 このプログラムをそれぞれ、配列とリスト構造によってプログラムを記述した。
この処理の一部として、配列やリストにデータxを追加する 関数 insert(x)と関連する部分を以下に示す。
この時、以下の設問に答えよ。

1. 配列でのプログラム1 の関数 ins(p,x) において、for文を
   for( j = p ; j < size ; j++ )
   で記述したら正しく動作しなかった。 理由を説明せよ。(10)
2. リストでのプログラム2 のデータxを 指定された位置pに挿入する関数 ins(p,x) を完成させよ。(10)
3. 配列とリストそれぞれのプログラムの関数 ins(p,x) の 処理速度のオーダー O(n) について分かりやすく説明し、 それぞれの方法の利点・欠点について述べよ。(10) (処理速度以外の利点・欠点についても述べること)

	/***** プログラム1 : 配列の場合 *****/
	#define MAX 200
	int array[ 200 ] ;  /* データを記憶する配列       */
	int size = 0 ;      /* array に記憶したデータ件数 */
	void ins( int p , int x ) /* 設問3 */
	{   int j ;
	    for( j = size - 1 ; j >= p ; j-- ) /* 設問1 */
	        array[ j + 1 ] = array[ j ] ;
	    array[ p ] = x ;
	    size++ ;
	}
	void insert( int x )
	{   int i ;
	    for( i = 0 ; i < size ; i++ ) {
	        if ( array[ i ] > x ) {
	            ins( i , x ) ;
	            break ;
	        }
	    }
	}
	
	/***** プログラム2 : リスト処理の場合 *****/
	struct List {
	    struct List* next ;  /* 次のリストへのポインタ */
	    int          data ;  /* 整数のデータ */
	} ;
	struct List* cons( int x , struct List* p )
	{
	    struct List* n = (struct List*)malloc(sizeof(struct List)) ;
	    if ( n != NULL ) {
	        n->data = x ;
	        n->next = p ;
	    }
	    return n ;
	}
	struct List* top = NULL ; /* リストデータの先頭 */
	void ins( struct List* p , int x ) /* 設問3 */
	{
	    /* この部分を作成せよ(設問2) */

	    /* ただしリストには、x より大きなデータが */
	    /* 1件以上、あらかじめ存在するものとする  */
	}
	void insert( int x )
	{
	    struct List* p ;
	    for( p = top ; p->next != NULL ; p = p->next )
	        if ( p->next->data > x ) { /* 次のデータが大きいなら */
	            ins( p , x ) ;
	            break ;
	        }
	}
	

2.リスト処理基礎(必須)

	struct List {
	    struct List* next ;     /* 次のリストへのポインタ */
	    int          data ;     /* 整数のデータ */
	} ;
	struct List* stack = NULL ; /* リストは最初、空 */
	void push( int x )
	{   struct List* n = (struct List*)malloc(sizeof(struct List)) ;
	    if ( n != NULL ) {
	        n->data = x ;
	        n->next = stack ;  /* リスト stack の先頭に */
	        stack = n ;        /* 新しい要素を追加      */
	    }
	}
	int pop()
	{   int  ret = 0 ;
	    if ( stack != NULL ) {
	        struct List* del = stack ;
	        ret = stack->data ; /* リストの先頭のデータ */
	        stack = stack->next ;
	        free( del ) ;            /* 先頭のデータを消す   */
	    }
	    return ret ;
	}
	void add()
	{
	    int a = pop() + pop() ;
	    push( a ) ;
	}
	void main()
	{
	    push( 3 ) ; push( 4 ) ; push( 5 ) ;
	    add() ; add() ;
	    printf( "%d\n" , pop() ) ;
	}
	

1. push(5)が終った時点での、リスト stack の 内容を、分かりやすく図によって示せ。(15)
2. プログラムによって表示される内容を、示せ。(15)

3.構造体に慣れてね問題(選択)

入力された (x,y) 座標に、与えられた座標の回転処理を加えてから、 回転後の座標に点を表示したい。このためのプログラムを以下のように作った。
回転座標を求めるための関数 rotate() を作成せよ。(20)

	#include <stdio.h>
	#include <math.h>
	struct XY {  /* 座標の構造体 */
	    int  x , y ;
	} ;
	void rotate( struct XY* res , double r[2][2] , struct XY* point )
	{
	    /* 座標の回転を加える関数 */
	    /* res   : 回転後の座標 */
	    /* r     : 回転行列     */
	    /* point : 元の座標     */
	}
	void main()
	{
	    struct XY  xy , ans ;
	    double     th = 45.0 * (3.1416 / 180.0) ; /* 45度 */
	    double     rot[ 2 ][ 2 ] ;
	    rot[ 0 ][ 0 ] = sin( th ) ;  rot[ 0 ][ 1 ] = cos( th ) ;
	    rot[ 1 ][ 0 ] = -cos( th ) ; rot[ 1 ][ 1 ] = sin( th ) ;
	    while( scanf( "%d %d" , &(xy.x) , &(xy.y) ) == 2 ) {
	        rotate( &ans , rot , &xy ) ;
	        point_set( ans.x , ans.y ) ;
	    }
	}
	

4.簡単なリスト処理問題(選択)

誕生日と名前のデータを以下のリストによって記憶した。 この時、指定された誕生日の人の名前をすべて表示する関数 happyBirthDay() を作成せよ。 (同一誕生日の人がリストに含まれる場合もありうる)
このデータ構造での例を、下図に示す。 happyBirthDay( top , 3 , 13 ) を実行したら、 tomoko と表示されて欲しい。(20)

	struct BirthDayList {
	    struct BirthDayList* next ;      /* 次のデータへのポインタ */
	    int                  mon , day ; /* 誕生日 */
	    char*                name ;      /* 名前   */
	} ;
	void happyBirthDay( struct BirthDayList* p , int m , int d )
	{
	    /* この部分を作成せよ               */
	    /* p   : 探す対象のリスト           */
	    /*       ヒント p->mon=月,p->day=日 */
	    /* m,d : 探す誕生日の月,日          */
	}
	

5.リスト処理の応用問題(選択)

設問2 のリスト処理問題の 関数push() , pop() を流用し、 以下のプログラムを実行する。
このプログラムの実行結果を示せ。(20)

	int  fact()
	{
	    if ( stack->data == 0 ) {
	        pop() ; push( 1 ) ;
	    } else {
	        push( stack->data - 1 ) ;
	        fact() ;
	        push( pop() * pop() ) ;
	    }
	}
	void main()
	{
	    push( 4 ) ; fact() ;
	    printf( "%d\n" , pop() ) ;
	}