情報構造論 (斉藤)

前期期末試験

番号：4EI
2023/08/05
(1/3)
氏名：
以下の 5 つの設問の中から、4 つを選んで回答せよ。

1基本動作トレース (25)struct List {int data ;struct List* next ;} ;| void print_list( struct List* p ) {|for( ; p != NULL ; p = p->next )|printf( "%d " , p->data ) ;|printf( "\n" ) ;~~~~~~~(A)| }struct List* cons( int x , struct List* n ) {struct List* ans ;ans = (struct List*)malloc( sizeof( struct List ) ) ;if ( ans != NULL ) {~~~~~~~~~~~~~~~~~~~~~(B)ans->data = x ;| int main() {ans->next = n ;|struct List* a = prime_factorize( 2 ) ;}|~~~~~~~~~~~~~~~~~~~~(C)return ans ;|struct List* b = prime_factorize( 10 ) ;}|print_list( a ) ; /* (a) */|print_list( b ) ; /* (b) */| }| (設問 1)struct List* prime_factorize( int x ) {| main 関数の中の 2 つの print_list() でstruct List* ans = NULL ;| 表示される内容を答えよ。
struct List** tail = &ans ;|for( int i = 2 ; i <= x ; i++ ) {| (a) ___________________(7)~~~~~~(D)|for( ; x % i == 0 ; x /= i ) {| (b) ___________________(8)*tail = cons( i , NULL ) ;|tail = &( (*tail)->next ) ;| (設問 2) 下線 (A)〜(E) の型を答えよ}~~~~~~~~~~~~~~~~(E)|}| (A)_____________ (B)____________
return ans ;|}| (C)_____________ (D)____________|| (E)_____________ (2x5)2説明問題 (25)
以下の 3 つの説明問題から 2 つを選び答えよ。

1. C 言語の typedef 命令について例を交えて説明せよ。
2. C 言語のビットフィールドについて例を交えて説明せよ。
3. 配列を使った LIFO 型のデータ構造について、イメージ図もしくはプログラムコードを交えて説明せよ。

情報構造論 (斉藤)

4EI

3

前期期末試験

2023/08/05

番号：
氏名：

(2/3)

説明問題 (25)
下線部 (A)〜(H) を穴埋めせよ。回答欄 (B),(C),(D),(E) はオーダー記法で回答すること。

1. リスト構造と配列を比べた場合、配列の中から目的のデータを探すのにかかる時間は、あらかじめデータを昇順に並べておく (A)____________法を用いれば、検索に要する時間は、データ件数を N としたとき (B)____________となる。しかしリスト構造であれば、先頭から 1づつ探すことから処理時間は、(C)____________となる。(4+3+3)
2. 一方で、配列では昇順のデータ列の途中にデータを挿入する場合、データを挿入すべき場所を見つけた後に、データを挿入する場所を確保するためにデータを１つずらす処理が必要となる。この処理には (D)____________の時間がかかる。これに対して、リスト構造であれば、データの挿入場所を見つけた後の挿入には (E)____________の時間がかかる。(3+3)
3. 最大でもデータ件数が 300 件、平均約 100 件の整数型のデータを保存する場合、配列であれば、このデータを覚えるのにメモリは (F)__________byte 必要となる。リスト構造の場合
は sizeof( struct List ) は、1 件あたり (G)__________byte なので、このデータ全体を覚えるには (H)__________byte を必要とする。(3+3+3)
ただし、int 型は 32bit とし、sizeof(struct List*) は 4 とする。ヒープ領域の管理に必要なメモリについては考慮しなくていい。

4プログラム作成 (25)
西暦の年月日のデータを和暦に変換して出力するプログラムを作りたい。西暦年月日は、2023/8/3 は 20230803 の様に8 桁の 10 進数で扱うものとする。
右図に示すように明治以降の和暦の始まった西暦, 年, 月, 日をリスト構造で保存し、このリストを使って入力された西暦を和暦に表示して表示したい。(参考: 入力と出力の例)

1. 右図にしめす構造体 Nengo を定義し、

Nengo
top

name

ymd

Meiji

18681023

Taisho19120730

Showa

19261225

Heisei

19890108

Reiwa

20190501

next

2. 西暦を和暦に変換し表示する関数 print_wareki() を作成せよ。

struct NengoList {| int main() {|struct NengoList* top = リスト生成処理 ;|int ymd ;|while( scanf( "%d", &ymd ) == 1 )|print_wareki( ymd ) ;|return 0 ;| }|(注意) リスト生成処理は作らなくていい。(10+15)| 入力と出力の例| 19261224 => Taisho 15,12,24| 19261225 => Showa 1,12,25| 20230805 => Reiwa 5,8,5

情報構造論 (斉藤)

4EI5

前期期末試験

2023/08/05

(3/3)

番号：
氏名：

プログラム穴埋め問題 (25)

30 以下の自然数の集合を (a) 集合の要素をリストとしたもの、(b) 集合の要素を配列に格納し配列の最後には-1 を保存したもの、(c) 集合の要素に対応した 2 進数 (最下位 bit を 0 とする) で扱う場合、(a) 方式と (b) 方式の集合積を (a) 方式で求める関数 and_list_array()、(c) 方式と (a)方式の集合和を (c) 方式で求める関数 or_bits_list() を作成する。
以下のプログラムの下線部にふさわしい処理を記載せよ。
struct List* and_list_array(p , int array[] ) {~~~~~~~~~~~~~~~~~~(A)3

struct List* ans = NULL ;| void main() {|struct List* a =|cons( 1, cons( 3, cons( 5, NULL ) ) ) ;|int b[] = { 3 , 6 , 9 , -1 } ;|int c = (1<<1) | (1<<2) | (1<<3) ;if ( p->data ==)|print_list( and_list_array( a , b ) ;break ;~~~~~~~~~~~(C)3|print_bits( or_bits_list( c , a ) ;if ( array[i] >= 0 )| }(注意)
ans =;
List や print_list() は}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(D)3
設問 1 の内容を引き継ぐ
return ans ;(上記例の結果)}
print_list() - 3
int or_bits_list(bits ,p ) {print_bits() - 1,2,3,6,9~~~~~~~~~(E)3~~~~~~~~~~~~~~~(F)3
int ans = bits ;for( ;; p = p->next )| void print_bits( int bits ) {~~~~~~~~~~~~(G)3|
for( int i = 0 ; i <= 30 ; i++ )ans|
if ( (1 << i) & bits )~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(H)4 |printf( "%d " , i ) ;return ans ;|printf( "\n" ) ;}| }for( ; p != NULL ;) {int i ;~~~~~~~~~~~~~~~~(B)3for( i = 0 ; array[i] >= 0 ; i++ )