WAITルーチンの計算手順

明星大学情報学科 2012年度後期
情報技術Ⅱ
第８回
中間試験の解説
@ DENGINEER
本日のメニュー
１．中間試験の結果報告
２．問題についての解説
１．木構造の応用（１）
四則演算式の解析
（４＋２）×（３－１）
×
＋
４
－
２
３
１
２．解説（問題１ 1-1）（１）
問題１ C言語
１-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 {
unsigned char code;
unsigned char str[10];
};
struct Kouzou mk[3];
11
11
1
11
1
1
2
11
3
4
5
6
7
8
9 10
２．解説（問題１ 1-2）
問題１ C言語
１-2
int main( void )
{
struct Kouzou (1)
*pk
pk = malloc( (2)
(3)
;
//構造体 Kouzouのポインタ pkを宣言
);
//動的にメモリを確保し、pkに割り当てる
//pkのcodeに168を入れる
sizeof( struct Kouzou )
= 168;
pk -> code
printf( “pkのcodeその１ = %02x\n” , (3)と同じもの );
printf( “pkのcodeその２ = %02X\n” , (3)と同じもの );
free( (4)
return ( 0 );
}
pk
);
//pkを解放する
// pkのcodeを表示する
// pkのcodeを表示する
２．解説（問題１ 1-3）
問題１ C言語
１-3
printf( “pkのcode その１ = %02x\n” , (3)と同じもの );
// pkのcodeを表示する
printf( “pkのcode その２ = %02X\n” , (3)と同じもの );
// pkのcodeを表示する
pk の code には、10進表記の 168 が入っている
16進に変換すると A8 となる
２．解説（問題２ 2-1）
問題２逆ポーランド記法
2-1
（1）
２＋３－５×８
（２）
２＋（３－５）×８
－
＋
＋
２
5
×
8
－
3
２３＋５８×－
×
２
×
３
（３）
（２＋３－５）×８
－
8
5
２３５－８×＋
＋
２
8
5
3
２３＋５－８×
２．解説（問題２ 2-2）
問題２逆ポーランド記法
2-２
（1）
２0_12_×_11_－_29_＋
（2）
1_2_3_4_＋_×_－
4
73
12
11
29
240
229
258
20
14
2
×
－
＋
-13
1
（3）
10_2_3_＋_÷_73_×
＋
×
－
3
73
2
5
146
10
2
＋
÷
×
２．解説（問題２ 2-3）
問題２逆ポーランド記法
2-3
４８２６＋＋×
（1）
（2）
×
4
6
＋
8
82
＋
16
8
4
8
2
6
64
4
＋
＋
×
２．解説（問題３ 3-1）
問題３スタックとキュー
3-1
LINK
リングバッファ
LIFO
PUSH
FILA
先入れ後出し
FIFA
PULL
待ち行列
FILE
FIFO
LOLI
ドーナツバッファ
FILO
先入れ先出し
（1）stack
LIFO
,
PUSH
,
先入れ後出し
,
FILO
リングバッファ
,
待ち行列
,
FIFO
,
先入れ先出し
（2）queue
２．解説（問題３ 3-2）（１）
問題３スタックとキュー
3-2
（1）速度差を吸収する
・・・入れた順番どおりに取り出す必要がある
先入れ先出し（FIFO）
キュー（queue）
（2）読み出し不能の間は、バッファから取り出して再生するだけ
バッファが空になるまでは、連続して再生できる
（音飛びしない）
バッファサイズが、何秒分の再生データか
計算すればよい
256,000（byte）
176,400（byte／sec）
≒ 1.4512（sec）
２．解説（問題３ 3-2）（２）
（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)と置くと、
読み出せるデータ量は
（４×176,400） ×ｔ（byte）
・
・
・
読み出し
再生
この間に再生されるデータ量は、
176,400 ×ｔ（byte）
読み出し部がバッファを１周してから、再生部に追いつくのは、
（４×176,400） ×ｔ＝ 176,400 ×ｔ＋256,000
と、なるので、ｔについて解くと
ｔ ≒ 0.4837（sec）
・
・
・
２．解説（問題３ 3-2）（４）
（3）
その３
再生しながらなので、4倍速で読み出す間に
１倍速で再生される
再生された部分は、再利用可能
ｔ秒でバッファに溜まる分は、
（４×176,400）×ｔ－ 176,400 ×ｔ
＝（３×176,400）×ｔ（byte）
バッファサイズは、256kbyte なので、
（３×176,400）×ｔ＝ 256,000
ｔ ≒ 0.4837（sec）
・
・
・
読み出し
再生
・
・
・
２．解説（問題４ 4-1）（１）
問題４木構造
4-1
ア
（１）2分木
12
4
2
15
9
17
（２）2分探索木
・・・・○
（３）完全2分木
・・・・×
（４）木構造
（５）ヒープ木
8
・・・・・・○
・・・・・・○
・・・・ ×
10
（６）ハフマン木
・・・ ×
２．解説（問題４ 4-1）（２）
問題４木構造
4-1
イ
（１）2分木
13
5
1
9
8
12
・・・・・・○
（２）2分探索木
・・・・ ×
（３）完全2分木
・・・・ ○
（４）木構造
（５）ヒープ木
（６）ハフマン木
・・・・・・○
・・・・ ×
・・・ ×
２．解説（問題４ 4-1）（３）
問題４木構造
4-1
（１）2分木
ウ
8
3
1
4
2
5
6
7
・・・・・・ ×
（２）2分探索木
・・・・ ×
（３）完全2分木
・・・・×
（４）木構造
（５）ヒープ木
（６）ハフマン木
・・・・・・○
・・・・ ×
・・・ ×
２．解説（問題４ 4-1）（４）
問題４木構造
4-1
エ
（１）2分木
10
7
6
8
4
2
9
（２）2分探索木
・・・・ ×
（３）完全2分木
・・・・×
（４）木構造
（５）ヒープ木
5
3
・・・・・・ ×
・・・・・・ ×
・・・・ ×
1
（６）ハフマン木
・・・ ×
２．解説（問題４ 4-1）（５）
問題４木構造
4-1
（１）2分木
オ
・・・・・・○
15
13
12
10
8
6
（２）2分探索木
・・・・○
（３）完全2分木
・・・・ ○
（４）木構造
（５）ヒープ木
（６）ハフマン木
・・・・・・○
・・・・ ×
・・・ ×
２．解説（問題４ 4-1）（６）
問題４木構造
4-1
カ
（１）2分木
12
5
2
11
4
8
（２）2分探索木
・・・・ ×
（３）完全2分木
・・・・ ○
（４）木構造
10
（５）ヒープ木
1
3
6
7
・・・・・・○
・・・・・・○
・・・・ ○
9
（６）ハフマン木
・・・ ×
２．解説（問題４ 4-2）
問題４木構造
4-2
1 , 2 , 5 , 8 , 13 , 18 , 21
8
2
1
18
5
13
21
２．解説（問題５ 5-1）
問題５線形リスト
5-1
1
●
●
2
8
②
①
5
●
●
13
●
18
●
２．解説（問題５ 5-2）
問題５線形リスト
5-2
0x9000
1
0x0001
0x9004
●
0x9008
●
2
0x900C
●
8
0x0002
13
0x0008
0x9014
5
0x000D
0x9010
●
18
0x0012
●
0x0005
struct singly_list {
short value;
struct singly_list
};
value
*next;
1
*next
●
0x01
0x00
0x04
0x90
●
@

Download Report