教科書・ノート持ち込み不可。
解答に使用するプログラム言語は、問題の趣旨に沿っていれば何を用いても良い。
解答を裏に書く場合、どの設問に対する答か解るようにすること。
すべての大きな６つの設問の中から、５題以上について回答せよ。
採点は、各設問毎に行ない点数の高いものから５題について評価する。
５題よりより多く回答されている場合は、点数の 1/2 で加算する。
名前と電話番号のデータベースを作り、 データ構造を書記化し(関数名init())、 名前と電話番号を登録し(関数名add())、 名前から電話番号を検索する(関数名find())プログラムを、 さまざまなデータ構造で作るものとする。
呼び出し側のプログラムは、あらかじめファイル(data.txt)から入力し、
標準入力から、探すべき名前を入力し、その結果を表示する。
(次のプログラムを参考)
void main()
{
char name[ 128 ] , phone[ 32 ] , *ans ;
FILE* fp ;
init() ; /* データベースの初期化 */
if ( (fp = fopen( "data.txt" , "rt" )) != NULL ) {
while( fscanf( fp , "%s %s" , name , phone ) == 2 )
add( name , phone ) ; /* データベースへの登録 */
fclose( fp ) ;
}
scanf( "%s" , name ) ;
ans = find( name ) ; /* データベースから検索 */
if ( ans == NULL )
printf( "みつからない\n" ) ;
else
printf( "%s = %s\n" , name , ans ) ;
}
int size ; /* データ件数 */
char *name_table[ 100 ] ; /* 名前の配列 */
char *phone_table[ 100 ] ; /* 電話番号の配列 */
void init() { size = 0 ; }
void add( char* n , char* p )
{
name_table[ size ] = n ;
phone_table[ size ] = p ;
size++ ;
}
char* find( char* n )
{ int i ;
for( i = 0 ; i < size ; i++ )
if ( strcmp( name_table[ i ] , n ) == 0 )
return name_phone[ i ] ;
return NULL ;
}
このプログラムは、登録が正しく行われない。
前の設問 2 のプログラムの データ構造にハッシュ法を採用する。 以下の問に答えよ。
#define HashSize 128
struct NamePhoneList {
char name[ 64 ] ;
char phone[ 32 ] ;
struct NamePhoneList* next ;
} ;
struct NamePhoneList* table[ HashSize ];
void init()
{ int i ;
for( i = 0 ; i < HashSize ; i++ )
table[ i ] = NULL ;
}
int hash_func( char* n )
{ int sum ;
for( sum = 0 ; *n != '\0' ; n++ )
sum += *n ;
return sum % HashSize ;
}
struct NamePhoneList* np_cons( char* n , char* p ,
struct NamePhoneList* nxt )
{ struct NamePhoneList* np ;
np = (struct NamePhoneList*)
malloc( sizeof( struct NamePhoneList ) ) ;
strcpy( np->name , n ) ;
strcpy( np->phone , p ) ;
np->next = nxt ;
return np ;
}
void add( char* n , char* p )
{ int index = hash_func( n ) ;
/* リストの先頭に追加 */
table[ index ] = np_cons( n , p , table[ index ] ) ;
}
char* find( char* n )
{
/* この部分を作成せよ。*/
}
前の設問 3 でのハッシュ法のプログラムと、 2分探索法のプログラムの検索速度の比較を行った結果、 全データ件数 N が1024件の時、以下の通りであった。
| 検索方式 | 平均処理速度 |
| ハッシュ法 | 8[msec] |
| 2分探索法 | 10[msec] |
このとき、データが 16384 件( = 214 件)の場合、 ハッシュ法と2分探索法で、同程度の処理速度になるためには、 ハッシュ法のプログラムをどの様に改良すべきか、 具体的な数値を用いて説明せよ。
#include#include #include int eval( char* str ) { int sp , digit ; int st[ 100 ] ; int flag = 0 ; for( sp = 0 ; *str != '\0' ; str++ ) { if ( isdigit( *str ) ) { if ( !flag ) /* 直前が数字以外 */ digit = 0 ; digit = digit * 10 + (*str - '0') ; flag = 1 ; } else { if ( flag ) /* 直前が数字なら */ st[ sp++ ] = digit ; switch( *str ) { case '+' : st[sp-2] = st[sp-2] + st[sp-1] ; sp-- ; break ; case '-' : st[sp-2] = st[sp-2] - st[sp-1] ; sp-- ; break ; case '*' : st[sp-2] = st[sp-2] * st[sp-1] ; sp-- ; break ; case '/' : st[sp-2] = st[sp-2] / st[sp-1] ; sp-- ; break ; case 'N' : st[sp-1] = -st[sp-1] ; break ; } flag = 0 ; } } return st[ --sp ] ; } void main() { printf( "%d\n" , eval( "1 2+3+" ) ) ; printf( "%d\n" , eval( "12 2*10-" ) ) ; }
このプログラムの実行結果を示せ。
以下の合計点数を求めるプログラム sum.c をコンパイルし、 その実行プログラムの名前を sum とした。
/* sum.c : gcc -o sum sum.c */ #include#define SIZE 5 void main() { char name[ 100 ] ; int point , sum , i ; while( scanf( "%s" , name ) == 1 ) { for( i = 0 , sum = 0 ; i < SIZE ; i++ ) { scanf( "%d" , &point ) ; sum += point ; } printf( "%s %d\n" , name , sum ) ; } }
また、データファイルとして data1.txt,data2.txt がある。
| ファイル名=data1.txt | ファイル名=data2.txt |
t-saitoh 10 20 30 40 50 inteli 100 100 100 100 100 |
aoyama 22 45 84 123 62 okada 49 33 75 64 89 sakamoto 104 66 43 98 100 |
以下の2つの説明問題の中から、1つについて説明を加えよ。