「情報技術Ⅱ」前半 中間試験
問題１．C 言語
次の宣言をしている時、以下の問いに答えよ
１-１．各値を求めよ。
（１）sizeof( unsigned char ) （２）sizeof( struct Kouzou ) （３）sizeof( mk )
（４）sizeof( mk[1].str ) （５）sizeof( moji_1 ) （６）sizeof( mk[0] )
（７）情報科学研究センター（２６号館）の unix 上の gcc における sizeof( int )
１-２．コメントに書かれた内容の動作をするように、空欄を埋めよ。
１-３．上記のプログラムを実行したときに、画面に表示される値を示せ。
pk の code その１=pk の code その２=
unsigned char moji_1; struct Kouzou {
unsigned char code; unsigned char str[10]; }; struct Kouzou mk[3]; （１） （２） （３） （４） （５） （６） （７）
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) (３) (4) (1) (2) （各 2 点） （各 5 点） （各 3 点）
１
11
33
10
1
11
4
*pksizeof( struct Kouzou )
pk->code
pk
a8
A8
問題２．逆ポーランド記法
２-１．次の式を、逆ポーランド記法で記せ。
（適切な位置に演算子を書き入れよ）
（１）２＋３－５×８ （２）２＋（３－５）×８ （３）（２＋３－５）×８ （１）２
３
＋
５
８
×
－
（２）２
３
５
－
８
×
＋
（３）２
３
＋
５
－
８
×
２-２．逆ポーランド記法で記された、次の式を解け。
（区切り記号は _ で示してある）
（１）20_12_×_11_－_29_＋
＝
258
（２）１_２_３_４_＋_×_－
＝
-13
（３）10_2_3_＋_÷_73_×
＝
146
２-３．次式の元となった解析木を 2 分木で構成し、計算手順をスタックの変化で示せ。
４８２６＋＋×
（２）計算手順 （１）解析木 ４4
８8
4
２2
8
4
６6
2
8
4
＋8
8
4
＋16
4
×64
（各 3 点） （各 3 点） （12 点） （10 点）×
＋
＋
２
６
８
４
問題３．スタックとキュー
３-１．次の語句の中から、それぞれに関係の深いものをすべて選べ。
（１）stack （２）queue３-２．次の問いに答えよ。
音楽用の CD のプレーヤーは、音とびを防止するために、標準より速い速度で CD から情報を 読み出し、再生する段階で標準の速度にしている。 （１）読み出し速度と再生速度の違いを吸収するのに適した仕組みは、次のどれか？ CD の音楽情報は、サンプリング 44.1kHz 量子化 16 ビット ステレオ、すなわち、 1 秒間の音声データは、44,100×16×2 (bit) ＝ 176,400 byte である。 4 倍速で読み出し可能な CD プレーヤーで、バッファサイズが 256kbyte のとき、 （２）外部からの衝撃などで一時的に読み出せなくなった場合、それまでに読み出されていた データがバッファに満たされていたとして、読み出し不能から回復するまで何秒以内 だったら、音飛びが発生しないですむか？ 該当するものをすべて選べ。 （３）順調に読み出しができるとして、バッファが空の状態から、音楽を再生しながら バッファがいっぱいになるまで、およそ何秒かかるか？ もっとも近いものを選べ。LINK リングバッファ LIFO PUSH FILA
先入れ後出し FIFA PULL 待ち行列 FILE
FIFO LOLI ドーナツバッファ FILO 先入れ先出し
LIFO、PUSH、先入れ後出し、FILO
リングバッファ、待ち行列、FIFO、先入れ先出し
ア）stack イ）queue ウ）struct
ア）0.5 秒 イ）1 秒 ウ）1.5 秒 エ）2 秒 ア）0.25 秒 イ）0.36 秒 ウ）0.48 秒 エ）0.72 秒 オ）1 秒 （8 点） （8 点） （4 点） （10 点） （10 点）
問題４．木構造
４-１．次の中から、条件に合うものをすべて選べ。
（該当するものがなければ「なし」
）
（１）2 分木 （２）2 分探索木 （３）完全 2 分木 （４）木構造 （５）ヒープ木 （６）ハフマン木４-２．次の数値を格納する、完全 2 分探索木を作成せよ。
ウ 3 1 2 5 6 7 4 8 ア 4 2 9 15 12 17 8 10 イ 5 1 8 9 13 12 エ 7 6 4 8 10 9 2 1 3 5 オ 6 8 13 10 15 12 カ 5 2 4 11 12 10 8 7 6 3 1 9 完全 2 分探索木 81 , 2 , 5 , 8 , 13 , 18 , 21
（各 3 点） （22 点） ア、イ、オ、カ ア、オ ア、イ、ウ、オ、カ カ イ、オ、カ なし 2 18 １ ５ 13 21問題５．線形リスト
値の小さい順につないでいる、次のようなリスト構造のデータがある。
このリストに「５」のデータを挿入するとき、次の各問いに答えよ。
５-１．挿入後のリスト構造を示すように、矢印を書き込め。
また、挿入の際につなぎ替えた部分の矢印には、つなぎ替えた順番を矢印のそばに番号で示せ。５-２．メモリの変化の様子について、空欄を埋めて、下図を完成させよ。
このときのノードの構造は、右図の通りであり、 リトルエンディアン、ポインタサイズは 16 ビット、 メモリへの格納は、0x9000 番地から隙間なく 使われるものとする。 ● １ ２ ● ８ ● 13 ● 18 ● ● １ ２ ● ８ ● 13 ● 18 ● ● ５ 挿入前の状態 アドレス メモリ アドレス メモリ 0x9000 0x01 0x9010 0x12 0x9001 0x00 0x9011 0x00 0x9002 0x04 0x9012 0x20 0x9003 0x90 0x9013 0x90 0x9004 0x02 0x9014 （空き） 0x9005 0x00 0x9015 （空き） 0x9006 0x08 0x9016 （空き） 0x9007 0x90 0x9017 （空き） 0x9008 0x08 0x9018 （空き） 0x9009 0x00 0x9019 （空き） 0x900A 0x0C 0x901A （空き） 0x900B 0x90 0x901B （空き） 0x900C 0x0D 0x901C （空き） 0x900D 0x00 0x901D （空き） 0x900E 0x10 0x901E （空き） 0x900F 0x90 0x901F （空き） 挿入後の状態 アドレス メモリ アドレス メモリ 0x9000 0x01 0x9010 0x12 0x9001 0x00 0x9011 0x00 0x9002 0x04 0x9012 0x20 0x9003 0x90 0x9013 0x90 0x9004 0x02 0x9014 0x05 0x9005 0x00 0x9015 0x00 0x9006 0x14 0x9016 0x08 0x9007 0x90 0x9017 0x90 0x9008 0x08 0x9018 （空き） 0x9009 0x00 0x9019 （空き） 0x900A 0x0C 0x901A （空き） 0x900B 0x90 0x901B （空き） 0x900C 0x0D 0x901C （空き） 0x900D 0x00 0x901D （空き） 0x900E 0x10 0x901E （空き） 0x900F 0x90 0x901F （空き） struct singly_list { short value;struct singly_list *next; };
（15 点）
（25 点）
① ②
