📖 講義スライド
データ構造
開く ↗
ℹ️
注意: この年度では 「集合・確率・データ構造」 として統合試験になっています。
📝 集合・確率・データ構造 (2014)
PDF ↗ 1
男3人、女5人から4人を選ぶとき、女が2人以上含まれる場合の数を求めよ
▶ 解答を表示
A. 65
解説: 女2人: C(5,2)×C(3,2) = 10×3 = 30通り、女3人: C(5,3)×C(3,1) = 10×3 = 30通り、女4人: C(5,4) = 5通り。合計: 30+30+5 = 65通り
2
0と1をn個組合せて100種類の数を表すためのnを求めよ
▶ 解答を表示
A. 7
解説: 2^n ≥ 100となる最小のnを求める。2^6 = 64 < 100、2^7 = 128 ≥ 100。したがってn = 7
3
平均70点で正規分布している100人分のテスト結果において、80点以上は16人だった。標準正規分布表が下の様に与えられている時、標準偏差σを求めよ
| u | 確率 |
|---|---|
| 0 | 0.5 |
| 1 | 0.159 |
| 2 | 0.023 |
| 3 | 0.001 |
▶ 解答を表示
A. 10
解説: 80点以上が16人 = 16%。Pr(U > u) = 0.16 ≒ 0.159より u = 1.0。U = (80-70)/σ = 1.0より、σ = 10
4
A=3, B=4, C=5, D=6である時、逆ポーランド記法で示された式 AB+CD−∗ を評価せよ
▶ 解答を表示
A. -7
解説: AB+ = 3+4 = 7、CD− = 5-6 = -1、7 × (-1) = -7
5
次の状態遷移表を表す状態遷移図を書け
▶ 解答を表示
A. 略
解説: 状態遷移表から状態遷移図を描く。S0, S1, S2の3状態があり、入力0と1で遷移する
📝 データ構造 (2014)
PDF ↗ 1
A, B, C の順に到着するデータをスタックに登録して、B, C, A の順に出力するための、スタックの操作列(push, pop など)を示せ。
▶ 解答を表示
A. push A, push B, pop, push C, pop, pop
解説: A, B, C の順に到着し、B, C, A の順に出力するには:
1. push A → スタック[A]
2. push B → スタック[A, B]
3. pop → Bを出力、スタック[A]
4. push C → スタック[A, C]
5. pop → Cを出力、スタック[A]
6. pop → Aを出力、スタック[]
2
双方向リスト構造に、春、夏、秋、冬の順にデータが登録されている。空欄ア、イ、ウを埋めよ。
図: 双方向リスト: アドレス30(春)→アドレス10(夏)→アドレス20(秋)→アドレス40(冬)
▶ 解答を表示
A. ア = 20, イ = 0, ウ = 10
解説: 双方向リストの構造:
- アドレス30: 春(次:10, 前:0) ← 先頭要素
- アドレス10: 夏(次:ア, 前:30)
- アドレス20: 秋(次:40, 前:ウ)
- アドレス40: 冬(次:イ, 前:20) ← 末尾要素
春→夏→秋→冬の順なので:
- ア(夏の次) = 20(秋のアドレス)
- イ(冬の次) = 0(末尾)
- ウ(秋の前) = 10(夏のアドレス)
3
空の二分木に次の順でデータを追加した時、最も検索時間がかかるデータを求めよ。複数ある場合は全て挙げよ。 C, H, R, I, S, T, M, A
▶ 解答を表示
A. M, T
解説: 二分探索木の構築: C(ルート) → H(右) → R(Hの右) → I(Hの左) → S(Rの右) → T(Sの右) → M(Iの右) → A(Iの左)。
木の深さ:
- C: 深さ0
- H: 深さ1
- R: 深さ2
- I, S: 深さ3
- M, T: 深さ4
- A: 深さ5
※問題文の解答は「M, T」となっていますが、実際には A が最も深い位置（深さ5）にあります。ただし、解答に従い M, T を正解としています。
4
高さ 6 の完全二分木の接点数を求めよ。
▶ 解答を表示
A. 127
解説: 完全二分木の接点数の公式: 2^h - 1 (h: 高さ)
高さ6の完全二分木の接点数 = 2^7 - 1 = 128 - 1 = 127
各レベルのノード数:
- レベル0(ルート): 1
- レベル1: 2
- レベル2: 4
- レベル3: 8
- レベル4: 16
- レベル5: 32
- レベル6: 64
合計: 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127
5
キーのハッシュ関数を h(x) = x mod 13 とする。キー1 から 100 の中に、キー3 と衝突するものはいくつあるか？
▶ 解答を表示
A. 8
解説: h(3) = 3 mod 13 = 3
キー3と同じハッシュ値(3)になるキーは、x mod 13 = 3 を満たすキー。
これは x = 13k + 3 (k = 0, 1, 2, ...) の形式。
1から100の範囲で:
- k=0: 3 (キー3自身、衝突には含めない)
- k=1: 16
- k=2: 29
- k=3: 42
- k=4: 55
- k=5: 68
- k=6: 81
- k=7: 94
- k=8: 107 (100を超えるので範囲外)
キー3以外で衝突するもの: 16, 29, 42, 55, 68, 81, 94 の7個
※解答が「8」となっているため、キー3自身を含めた個数、または計算方法が異なる可能性があります。一般的には7個が正解ですが、解答に従い8としています。