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

1.基礎の確認

以下のプログラムにて、下線部(A)〜(I)の命令の実行順序を、 最初から記号にて示し、変数の値が変化するものについては、 記号の下に変数の値を示せ。

	#include <stdio.h>

	void foo( int *p ) {
	    for( *p = 0 ; *p < 2 ; (*p)++ )
	         ~~~~~(A) ~~~~~(B) ~~~~~(C)
	        printf( " %d" , *p ) ;
	        ~~~~~~~~~~~~~~~~~~~(D)
	    printf( "\n" ) ;
	    ~~~~~~~~~~~~~(E)
	}
	void main() {

	    int i , j ;

	    for( i = 0 ; i < 2 ; i++ )
	         ~~~~(F) ~~~~(G) ~~(H)
	        foo( &j ) ;
	             ~~(I)
	}

2.説明問題

2分木のデータ構造について、具体的なデータ構造の宣言と、 その具体的な説明を例をあげて説明せよ。

3.ハッシュ法プログラム

名前20文字と電話番号16桁のデータを扱う。 電話番号から名前を調べるプログラムを チェイン法のハッシュにて扱う。

	#include <stdio.h>
	#include <string.h>

	#define HashSize 100
	#define MALLOC(T) (T*)malloc( sizeof(T) )

	struct NameTelList {
	    char  name[ 20 ] ;                 /* 名前 */
	    char  tel[ 16 ] ;                  /* 電話番号 */
	    _____________________ next ;       /* 次のデータ */
	} ;

	struct NameTelList* hash[ HashSize ] ; /* ハッシュ表 */
	/* hash[] は NULL で初期化するものとする */

	int hash_func( char tl[] ) {         /* ハッシュ関数 */
	    int sum = 0 , i ;
	    for( i = 0 ; _______________ ; i++ )
	        sum = sum * 10 + tl[ i ] ;
	    return  sum % HashSize ;
	}

	/* ハッシュ表に 名前:nm , 電話:tl を追加する */
	void add( char nm[] , char tl[] ) {
	    int  idx = hash_func( tl ) ;
	    struct NameTelList* n ;
	    if ( (n = MALLOC( struct NameTelList )) _________ ) {
	        /* リストの先頭に新規データを入れる */
	        strcpy( n->name , nm ) ;
	        ______________________ ;
	        ______________________ ;
	        ______________________ ;
	    }
	}

1. 上記プログラムの下線部を埋めよ。

4.ハッシュ法の速度

前述のプログラムで以下のデータ件数にて処理速度を計測した。

1. データ件数が 50 件の場合の処理速度を、 おおまかに予測せよ。 ただし、その算出理由を具体的に説明すること。
2. 同じく、データ件数が 3000件の場合の処理速度を予測せよ。

5.応用プログラム

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

	#include <stdio.h>
	#define  SIZE  15

	int  bin_heap[ SIZE ] = {    /*          ヒント         */
	             54 ,            /*            01           */
	      25 ,          84 ,     /*      02          03     */
	   10 ,  44 ,   70 ,   90 ,  /*   04    05    06    07  */
	  3,11, 32,50, 62,77, 89,95  /* 08 09 10 11 12 13 14 15 */
	} ;

	int search( int key )
	{
	    int p = 1 ;             /* 先頭の場所 */

	    while( p-1 < SIZE ) {
	        if ( bin_heap[ p-1 ] == key )
	            return  p-1 ;   /* 見つかった */
	        else if ( bin_heap[ p-1 ] > key )
	            p = p * 2 ;     /* 左の枝 */
	        else
	            p = p * 2 + 1 ; /* 右の枝 */
	    }
	    return -1 ;             /* 見つからなかった */
	}

	void main()
	{
	    int  a ;
	    printf( "%d\n" , search( 44 ) ) ;
	    printf( "%d\n" , search( 83 ) ) ;
	}