基数変換 負数表現 浮動小数点 論理演算 集合と確率 オートマトン 符号理論 データ構造 ソート・探索 講義資料のみ

📖 講義スライド

データ構造 開く ↗

年度を選択

2013年度 2014年度 2015年度 2016年度 2017年度
ℹ️

注意: この年度では 「データ構造・符号理論 / FSM・確率・データ構造」 として統合試験になっています。

小テスト一覧

小テスト5 データ構造・符号理論 (2017) 小テスト6 FSM・確率・データ構造 (2017) 小テスト8 データ構造 (2017)

📝 データ構造・符号理論 (2017)

PDF ↗
1

次の順にデータを挿入した二分探索木を、S式（括弧表記）で表せ。 27, 7, 51, 20, 6, 19

Binary tree diagram 27 7 6 20 19 51
▶ 解答を表示
A. (27 (7 6 (20 19)) 51)
解説: 二分探索木のS式表現: 27をルートとし、各ノードを (値 左部分木 右部分木) の形式で表記する。左右の部分木がない場合は省略。 構築順序: 27(ルート) → 7(左) → 51(右) → 20(7の右) → 6(7の左) → 19(20の左)
2

次のリスト(N, E, W, S)から、要素 E を削除するために書き換えるアドレス、データ、ポインタを示せ。 アドレス データ ポインタ 100 E 200 200 W 300 300 S 0 400 N 100

▶ 解答を表示
A. アドレス400のポインタを100から200に書き換える
解説: リスト構造: N(400)→E(100)→W(200)→S(300)。Eを削除するには、Eを指しているN(アドレス400)のポインタを、Eの次の要素W(アドレス200)に変更する。
3

空のキューとスタックに、次の操作を行った後、x, y を求めよ。 enq(み), push(か), push(ん), enq(pop()), push(deq()), x = pop(), y = deq()

▶ 解答を表示
A. x=み，y=ん
解説: 操作の流れ: 1. enq(み) → キュー[み] 2. push(か) → スタック[か] 3. push(ん) → スタック[か,ん] 4. enq(pop()) → pop()で「ん」、キュー[み,ん] 5. push(deq()) → deq()で「み」、スタック[か,み] 6. x = pop() → 「み」 7. y = deq() → 「ん」
4

16進数で表されるデータ 122, 235, 43B, 58E, 7A1, 8AF, ABA, C2D をハッシュ表に入れる。ハッシュ関数を H(x) = x mod 8 とするとき、最初に衝突が起きるのはどのデータか?

▶ 解答を表示
A. ABA
解説: 各データのハッシュ値（x mod 8）: 122(16) = 290(10) → 290 mod 8 = 2 235(16) = 565(10) → 565 mod 8 = 5 43B(16) = 1083(10) → 1083 mod 8 = 3 58E(16) = 1422(10) → 1422 mod 8 = 6 7A1(16) = 1953(10) → 1953 mod 8 = 1 8AF(16) = 2223(10) → 2223 mod 8 = 7 ABA(16) = 2746(10) → 2746 mod 8 = 2 ← 122と衝突！ 最初に衝突するのはABA（122と同じハッシュ値2）。
5

LIFO を表すデータ構造は、リスト、配列、スタック、キュー、二分探索木、ハッシングのどれか?

▶ 解答を表示
A. スタック
解説: LIFO (Last In First Out: 後入れ先出し) を実現するデータ構造はスタック。最後に入れたデータが最初に取り出される。キューはFIFO (First In First Out: 先入れ先出し) である。

📝 FSM・確率・データ構造 (2017)

PDF ↗
1

事象 A「1回目に赤玉が出る」，事象 B「2回目に赤玉が出る」とするとき，事象 A が生起した時の B の条件付確率を表す記号はどれか？

ア P(A∩B)
イ P(A∪B)
ウ P(A|B)
エ P(B|A)
オ P(B)
▶ 解答を表示
A. エ
解説: P(B|A) は「Aが起きたときのBの条件付確率」を表す
2

白玉5個，赤玉4個が入っている壺から球を2個取り出す．赤玉の数の期待値を求めよ．

▶ 解答を表示
A. 8/9
解説: 期待値 E[X] = 0×P(X=0) + 1×P(X=1) + 2×P(X=2) を計算する
3

平均60点のテストで55点と採点された時の偏差値が40点だった．この時の標準偏差を求めよ．

▶ 解答を表示
A. 5
解説: 偏差値 = 50 + 10×(得点-平均)/標準偏差。40 = 50 + 10×(55-60)/σ より σ = 5
4

次のBNFで定義されるビット列を全て挙げよ． <S>::=0|1|<S>0

ア 00
イ 01
ウ 10
エ 010
オ 100
▶ 解答を表示
A. ア，ウ，オ
解説: BNFにより生成できるのは、0で終わるビット列（0, 10, 00, 100, 110, 1000, ...）と1のみ
5

A=1, B=3, C=5, D=4 の時，逆ポーランド表記された式 AB+CD-* の演算結果を求めよ．

▶ 解答を表示
A. 4
解説: AB+ = 1+3 = 4, CD- = 5-4 = 1, 4*1 = 4

📝 データ構造 (2017)

PDF ↗
1

次の順にデータを挿入した二分探索木を、S式（括弧表記）で表せ。 27, 7, 51, 20, 6, 19

Binary tree diagram 27 7 6 20 19 51
▶ 解答を表示
A. (27 (7 6 (20 19)) 51)
解説: 二分探索木のS式表現: 27をルートとし、各ノードを (値 左部分木 右部分木) の形式で表記する。左右の部分木がない場合は省略。 構築順序: 27(ルート) → 7(左) → 51(右) → 20(7の右) → 6(7の左) → 19(20の左)
2

次のリスト(N, E, W, S)から、要素 E を削除するために書き換えるアドレス、データ、ポインタを示せ。 アドレス データ ポインタ 100 E 200 200 W 300 300 S 0 400 N 100

▶ 解答を表示
A. アドレス400のポインタを100から200に書き換える
解説: リスト構造: N(400)→E(100)→W(200)→S(300)。Eを削除するには、Eを指しているN(アドレス400)のポインタを、Eの次の要素W(アドレス200)に変更する。
3

空のキューとスタックに、次の操作を行った後、x, y を求めよ。 enq(み), push(か), push(ん), enq(pop()), push(deq()), x = pop(), y = deq()

▶ 解答を表示
A. x=み，y=ん
解説: 操作の流れ: 1. enq(み) → キュー[み] 2. push(か) → スタック[か] 3. push(ん) → スタック[か,ん] 4. enq(pop()) → pop()で「ん」、キュー[み,ん] 5. push(deq()) → deq()で「み」、スタック[か,み] 6. x = pop() → 「み」 7. y = deq() → 「ん」
4

16進数で表されるデータ 122, 235, 43B, 58E, 7A1, 8AF, ABA, C2D をハッシュ表に入れる。ハッシュ関数を H(x) = x mod 8 とするとき、最初に衝突が起きるのはどのデータか?

▶ 解答を表示
A. ABA
解説: 各データのハッシュ値（x mod 8）: 122(16) = 290(10) → 290 mod 8 = 2 235(16) = 565(10) → 565 mod 8 = 5 43B(16) = 1083(10) → 1083 mod 8 = 3 58E(16) = 1422(10) → 1422 mod 8 = 6 7A1(16) = 1953(10) → 1953 mod 8 = 1 8AF(16) = 2223(10) → 2223 mod 8 = 7 ABA(16) = 2746(10) → 2746 mod 8 = 2 ← 122と衝突！ 最初に衝突するのはABA（122と同じハッシュ値2）。
5

LIFO を表すデータ構造は、リスト、配列、スタック、キュー、二分探索木、ハッシングのどれか?

▶ 解答を表示
A. スタック
解説: LIFO (Last In First Out: 後入れ先出し) を実現するデータ構造はスタック。最後に入れたデータが最初に取り出される。キューはFIFO (First In First Out: 先入れ先出し) である。