明星大学 情報学科　2012年度 後期 　 情報技術Ⅱ 　 第８回 　中間試験の解説 @　DENGINEER

本日 の メニュー １．中間試験の結果報告 ２．問題についての解説

１．木構造の応用（１） 四則演算式の解析 （４＋２）×（３－１） ４ ２ ＋ ３ １ － × ４ ２ ＋ ３ １ － ４ ２ ＋

２．解説（問題１ 1-1）（１） 問題１ C言語 １-1 unsigned char moji_1; ・・・文字型 １-1　 unsigned char moji_1; struct Kouzou { unsigned char code; unsigned char str[10]; }; struct Kouzou mk[3]; ・・・文字型 ・・・文字型 ・・文字型配列 構造体 ・・・構造体配列

２．解説（問題１ 1-1）（２） 問題１ C言語 １-1 unsigned char moji_1; struct Kouzou { １-1　 unsigned char moji_1; struct Kouzou { unsigned char code; unsigned char str[10]; }; struct Kouzou mk[3]; 1 11 1 1 2 3 4 5 6 7 8 9 10 11 11 11

sizeof( struct Kouzou ) ２．解説（問題１ 1-2） 問題１　C言語 １-2　 int main( void ) { struct Kouzou ; //構造体 Kouzouのポインタ pkを宣言 pk = malloc( ); //動的にメモリを確保し、pkに割り当てる = 168; //pkのcodeに168を入れる printf( “pkのcodeその１ = %02x\n” , (3)と同じもの ); // pkのcodeを表示する printf( “pkのcodeその２ = %02X\n” , (3)と同じもの ); // pkのcodeを表示する free( ); //pkを解放する return ( 0 ); } (1) (2) (3) (4) *pk sizeof( struct Kouzou ) pk -> code pk

２．解説（問題１ 1-3） 問題１ C言語 １-3 pk の code には 、10進表記の 168 が入っている １-3　 printf( “pkのcode その１ = %02x\n” , (3)と同じもの ); // pkのcodeを表示する printf( “pkのcode その２ = %02X\n” , (3)と同じもの ); pk の code には 、10進表記の 168 が入っている 16進に変換すると A8 となる

２．解説（問題２ 2-1） 問題２ 逆ポーランド記法 2-1 （1） ２＋３－５×８ （２） ２＋（３－５）×８ （３） （２＋３－５）×８ 問題２　逆ポーランド記法 2-1　 （1） 　２＋３－５×８ （２） 　２＋（３－５）×８ （３） 　（２＋３－５）×８ － ＋ × ２ ＋ × × － 8 ２ ３ 5 8 － 8 ＋ 5 3 5 ２ 3 　２ ３ ＋ ５ ８ × － 　２ ３ ５ － ８ × ＋ 　２ ３ ＋ ５ － ８ ×

２．解説（問題２ 2-2） 問題２ 逆ポーランド記法 2-２ ＋ － （1） ２0_12_×_11_－_29_＋ （2） 問題２　逆ポーランド記法 2-２　 （1） 　２0_12_×_11_－_29_＋ （2） 　1_2_3_4_＋_×_－ （3） 　10_2_3_＋_÷_73_× 4 7 ＋ 14 3 5 3 × ＋ 11 240 12 229 29 258 -13 2 2 2 146 73 － × ÷ × ＋ － 20 1 10

２．解説（問題２ 2-3） 問題２ 逆ポーランド記法 2-3 ４ ８ ２ ６ ＋ ＋ × （1） （2） 6 8 ＋ 2 16 ＋ 64 8 問題２　逆ポーランド記法 2-3　 ４ ８ ２ ６ ＋ ＋ × （1） （2） 4 8 2 6 ＋ × × 6 8 ＋ ＋ 2 16 ＋ ＋ 64 8 × 4 8 2 6 4

２．解説（問題３ 3-1） 問題３ スタックとキュー 3-1 （1）stack （2）queue LINK リングバッファ LIFO 問題３　スタックとキュー 3-1　 LINK リングバッファ LIFO PUSH FILA 先入れ後出し FIFA PULL 待ち行列 FILE FIFO LOLI ドーナツバッファ FILO 先入れ先出し （1）stack LIFO , PUSH , 先入れ後出し , FILO （2）queue リングバッファ , 待ち行列 , FIFO , 先入れ先出し

２．解説（問題３ 3-2）（１） 問題３ スタックとキュー 3-2 ・・・入れた順番どおりに取り出す必要がある （1）速度差を吸収する 問題３　スタックとキュー 3-2　 ・・・入れた順番どおりに取り出す必要がある （1）速度差を吸収する 先入れ先出し（FIFO） キュー（queue） （2）読み出し不能の間は、バッファから取り出して再生するだけ バッファが空になるまでは、連続して再生できる （音飛びしない） バッファサイズが、何秒分の再生データか 計算すればよい 256,000（byte） 176,400（byte／sec） ≒ 1.4512（sec）

２．解説（問題３ 3-2）（２） （3）3通りの考え方で解説 その１ 256kbyte 読み出しにかかる時間は 256,000（byte） ・ 再生 読み出し （3）3通りの考え方で解説 その１ 256kbyte 読み出しにかかる時間は 256,000（byte） ４×176,400（byte／sec） ≒ 0.3628（sec） この間に再生されている分は 176,400（byte／sec）×0.3628（sec） ≒ 64,000（byte） 0.3628秒 読み出した時点で、さらに64,000byte 使えることになる 64kbyte 読み出しにかかる時間は 64,000（byte） ４×176,400（byte／sec） ≒ 0.0907（sec） よって、 0.3628 ＋ 0.0907 ≒ 0.4535（sec）

２．解説（問題３ 3-2）（３） （3） その２ 読み出し時間をｔ(sec)と置くと、 読み出せるデータ量は ・ 再生 読み出し （3） その２ 読み出し時間をｔ(sec)と置くと、 読み出せるデータ量は （４×176,400） ×ｔ（byte） この間に再生されるデータ量は、 　176,400 ×ｔ（byte） 読み出し部がバッファを１周してから、再生部に追いつくのは、 （４×176,400） ×ｔ＝ 176,400 ×ｔ＋256,000 と、なるので、ｔについて解くと ｔ ≒ 0.4837（sec）

２．解説（問題３ 3-2）（４） 再生された部分は、再利用可能 （3） その３ 再生しながらなので、4倍速で読み出す間に １倍速で再生される ・ 再生 読み出し （3） その３ 再生しながらなので、4倍速で読み出す間に １倍速で再生される 再生された部分は、再利用可能 ｔ秒で バッファに溜まる分は、 （４×176,400）×ｔ － 176,400 ×ｔ ＝（３×176,400）×ｔ（byte） バッファサイズは、256kbyte なので、 （３×176,400）×ｔ＝ 256,000 ｔ ≒ 0.4837（sec）

２．解説（問題４ 4-1）（１） 問題４ 木構造 4-1 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・○ （３）完全2分木 問題４　木構造 4-1　 ア 4 2 9 15 12 17 8 10 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・○ （３）完全2分木 ・・・・× （４）木構造 ・・・・・・○ （５）ヒープ木 ・・・・ × （６）ハフマン木 ・・・ ×

２．解説（問題４ 4-1）（２） 問題４ 木構造 4-1 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・ × （３）完全2分木 問題４　木構造 4-1　 イ 5 1 8 9 13 12 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・ × （３）完全2分木 ・・・・ ○ （４）木構造 ・・・・・・○ （５）ヒープ木 ・・・・ × （６）ハフマン木 ・・・ ×

２．解説（問題４ 4-1）（３） 問題４ 木構造 4-1 （１）2分木 ・・・・・・ × （２）2分探索木 ・・・・ × （３）完全2分木 問題４　木構造 4-1　 ウ 3 1 2 5 6 7 4 8 （１）2分木 ・・・・・・ × （２）2分探索木 ・・・・ × （３）完全2分木 ・・・・× （４）木構造 ・・・・・・○ （５）ヒープ木 ・・・・ × （６）ハフマン木 ・・・ ×

２．解説（問題４ 4-1）（４） 問題４ 木構造 4-1 （１）2分木 ・・・・・・ × （２）2分探索木 ・・・・ × （３）完全2分木 問題４　木構造 4-1　 エ 7 6 4 8 10 9 2 1 3 5 （１）2分木 ・・・・・・ × （２）2分探索木 ・・・・ × （３）完全2分木 ・・・・× （４）木構造 ・・・・・・ × （５）ヒープ木 ・・・・ × （６）ハフマン木 ・・・ ×

２．解説（問題４ 4-1）（５） 問題４ 木構造 4-1 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・○ （３）完全2分木 問題４　木構造 4-1　 オ 10 13 6 15 12 8 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・○ （３）完全2分木 ・・・・ ○ （４）木構造 ・・・・・・○ （５）ヒープ木 ・・・・ × （６）ハフマン木 ・・・ ×

２．解説（問題４ 4-1）（６） 問題４ 木構造 4-1 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・ × （３）完全2分木 問題４　木構造 4-1　 カ 5 2 4 11 12 10 8 7 6 3 1 9 （１）2分木 ・・・・・・○ （２）2分探索木 ・・・・ × （３）完全2分木 ・・・・ ○ （４）木構造 ・・・・・・○ （５）ヒープ木 ・・・・ ○ （６）ハフマン木 ・・・ ×

２．解説（問題４ 4-2） 問題４　木構造 4-2　 1 , 2 , 5 , 8 , 13 , 18 , 21 1 5 2 13 21 18 8

２．解説（問題５ 5-1） 問題５　線形リスト 5-1　 ● 1 ● 2 ● 2 ● 8 ● 13 ● 18 ② ① ● 5

２．解説（問題５ 5-2） 問題５ 線形リスト 5-2 ● ● ● ● ● ● ● 1 2 8 13 18 5 0x01 0x00 1 問題５　線形リスト 5-2　 0x9000 0x9004 0x9008 0x900C 0x9010 ● 1 ● 2 ● 8 ● 13 ● 18 0x0001 0x0002 0x0008 0x000D 0x0012 ● 5 0x9014 0x0005 struct singly_list { short value; struct singly_list *next; }; value *next 0x01 0x00 ● 1 0x04 0x90

@