京都大学 情報学研究科 知能情報学専攻 2021年8月実施 情報学基礎 F2-1
Author
Isidore, 祭音Myyura
Description
設問1
整数の集合

(1) Algorithm.
(2)
設問2
(1) 表
(2)
(3) (2) で求めた対応付けを
表1
インデックス | リスト |
---|---|
0 | |
1 | 0100 |
2 | |
3 |
表2
キー | 生起確率 | ハッシュ値 |
---|---|---|
0100 | 0.10 | (a) |
0210 | 0.20 | (b) |
1010 | 0.15 | 0 |
1101 | 0.15 | 1 |
1111 | 0.25 | (c) |
2101 | 0.15 | (d) |
Kai
設問1
(1)
a.
b.
c.
d.
e.
(2)
Note that Algorithm 1 is so called "Quick Select" algorithm.
Let
Therefore,
設問2
(1)
index | list |
---|---|
0 | 2101 -> 1111 |
1 | 0100 -> 1211 -> 1222 |
2 | |
3 | 0010 |
(2)
- (a): 0
- (b): 2
- (
): 3 - (d): 1
Reason: to minimize the cost is to equalize the probability to insert each list
(3)
Construct a system of six linear equations in six variables from the table given in (2), and we have