情報構造論 (斉藤)

前期期末試験

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

1

基本動作トレース (20)struct List {int data ;struct List* next ;} ;このプログラムを動かした時に関数 main で生成されたリスト a,b のデータ構造のイメージ図を解答し、またプログラム中の (A)-(F) の型を答えよ。

struct List* cons( int x , struct List* n ) {struct List* ans ;ans = (struct List*)malloc( sizeof( struct List ) ) ;if ( ans != NULL ) {~~~~~~~~~~~~~~~~~~~~~(A)ans->data = x ;ans->next = n ;| struct List* even_filter( struct List* p ) {}|struct List* ans = NULL ;return ans ;|struct List** tail = &ans ;}~~~(B)|
for( ; p != NULL ; p = p->next ) {|~~~~~~~~~(C)~~~~~~~(D)void main() {|if ( p->data % 2 == 0 ) {struct List* a|~~~~~~~~~~~(E)= cons( 2 , cons( 3 ,|*tail = cons( p->data , NULL ) ;cons( 4 , NULL ) ) ) ;|tail = &( (*tail)->next ) ;struct List* b|}~~~~~~~~~~~~~~~~~~(F)= even_filter( a ) ;|}}|return ans ;| }[イメージ図][型の解答欄]a(A)(D)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(B)(E)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(C)(F)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~b2(4+4+2x6)

プログラム記述問題 (20)
topcityfukui

mon day max min next
8
4 27.6 22.3

fukui

8531.5 23.3

fukui

8

734.7 25.9

obama

8

634.2 23.9

左図のような市町村名, 月, 日, 最高気温, 最低気温の情報がリスト構造で与えられるものとする。

(1) この情報を保存するための、構造体の宣言、(2) この構造体の先頭アドレス top が引数で与えられた場合、真夏日 (最高気温が 30 度以上) でかつ熱帯夜(最低気温が 25 度以上) の日の市町村名と日付を表示する関数 print_heavy_hot_day() を作成せよ。

情報構造論 (斉藤)

4EI

3

前期期末試験

2022/08/09

番号：
氏名：

(2/3)

穴埋め問題 (20)void print( struct List* p ) {for( ; p != NULL ; p = p->next )printf( "%d " , p->data ) ;printf( "\n" ) ;}| int find(p ,key ) {|~~~~~~~~~~~~~~~~(A)2 ~~~~~~~~~(B)2|
for( ; p != NULL ;) {|~~~~~~~~~~~~~~~~(C)3|if ( p->data == key )|return 1 ;void main() {|}struct List* a|return 0 ;= cons( 2 , cons( 3 ,| }| リスト構造で集合のデータ
cons( 2 , NULL ) ) ) ;| を扱うプログラムを作成
print( uniq( a ) ) ; // output=3,2| する。
}|| A = {2,3,2} という集合でuniq(p ) {| は同じデータ 2 が含まれる~~~~~~~~~~~~~~~~(D)2~~~~~~~~~~~~~~~~~~~~(E)2| ので同じ値が１つしか含まstruct List* ans = NULL ;| れないリストを生成する
for( ;;) { | uniq() を完成させる。
~~~~~~~~~~~~~~~(F)3 ~~~~~~~~~~~~~~~~~~~(G)3 | 下線部 (A)〜(H) を埋めよ。
if ()~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(H)3ans = cons( p->data , ans ) ;}return ans ;※ List,cons()}4

は [設問 1] を継続

動作トレースと説明問題 (20)struct List* stack = NULL ;void push( int x ) {stack = cons( x , stack ) ;}int pop() {int ans = stack->data ;struct List* d = stack ;stack = stack->next ;free( d ) ;return ans ;}(5+5+10)| void add() {|int r = pop() , l = pop() ;|push( l + r ) ;| }|| void mul() {|int r = pop() , l = pop() ;|push( l * r ) ;| }|| void main() {|push( 1 ) ; push( 2 ) ; add() ;|push( 3 ) ; mul() ;|printf( "%d\n" , pop() ) ;| }1. 上記のプログラムの実行結果を答えよ。 ※ List,cons() は [設問 1] の継続とする。
2. このプログラムにおけるスタックのデータの出し入れの特徴を 4 単語で表せ。
3. 配列を用いた「待ち行列」の実装方法について、図などを交えながら説明せよ。

情報構造論 (斉藤)

4EI

前期期末試験

2022/08/09

(3/3)

番号：
氏名：

説明問題 (20)5

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

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

エラトステネスのふるい (20)6

エラトステネスのふるいのアルゴリズムで、64 未満の素数を表示するプログラムを以下の様に作成した。エラトステネスのアルゴリズムは、i の倍数に目印をつけていき、目印がついていないものを素数とする。
このプログラムでは、偶数は 2 以外は素数ではないので、奇数だけを bit 列に保存する。そこで、奇数 i は i−12 番目の bit に保存する。

void main() {// ...11,9,7,5,3,1 i 番目
int primes = 0 ; // ....0,1,0,0,0,0 ビット列
printf( "2\n" ) ; // 2 は偶数の素数
for( int i = 3 ;if ( (primes &; i += 2 ) {~~~~~~~~~(A)3// 奇数だけの繰り返し) == 0 ) {~~~~~~~~~~~~~~~~~~~~~(B)4
printf( "%d\n" , i ) ;for( int j = i + i ;;) {~~~~~~~~~(C)3 ~~~~~~~~~(D)3if () // j が奇数の時~~~~~~~~~~~~~~~(E)3
primes = primes;}~~~~~~~~~~~~~~~~~~~~~~~~~~~(F)4}}}