京都大学 情報学研究科 社会情報学コース 2026年度 情報学基礎 問題2

标签：

• 京都大学
• 互联网协议 IPv4 与 IPv6
• 关系代数
• 死锁与饥饿
• 信号量
• 链地址法哈希
• 链表

Author

祭音Myyura (Based on ymogi's answer refined with GPT 6 Astra)

Description

(1) ドット数値記法を使用して、IPv4 アドレスを表している次のビットパターンを符号化せよ。

10000101000000111100100110010001

(2) 次は関係「Employee」と関係「Sales」と関係「Hours」を表している。各関係の「EID」属性の値が同じことを条件（Employee.EID = Sales.EID = Hours.EID）として結合（JOIN）を行い、結果となる関係の表を示せ。

関係「Employee」

EID	Age	Name	Branch
347	25	Alex	LA
199	27	Sam	NY
563	22	Charlie	AZ
431	29	Jordan	MN

関係「Sales」

EID	Amount
523	235000
199	251000
347	189000
983	288000

関係「Hours」

EID	Hours
619	57
199	67
503	56
347	62

(3) 次は二つのプロセスの疑似コードである。相互排除（"read" と "write" の二つのセマフォ）を用いて同時にクリティカル領域に入らないようにしているが、デッドロックが発生している。プロセス B のみを修正してクリティカル領域を最小限にしながらデッドロックを解除せよ。 list.count() と list.get_first()、あるいは list.add_last() と list.remove_first() を同時に呼ぶとデータが破損される恐れがあるので、セマフォを使うこと。

プロセス A：

1: value = NULL
2: lock "read" semaphore
3: if (list.count() > 0) {
4:     lock "write" semaphore
5:     value = list.get_first()
6:     list.remove_first()
7:     unlock "write" semaphore
8: }
9: unlock "read" semaphore

プロセス B：

1: lock "write" semaphore
2: list.add_last(new_value)
3: lock "read" semaphore
4: if (list.count() > 10000) {
5:     print("too many")
6: }
7: unlock "read" semaphore
8: unlock "write" semaphore

(4) 以下のハッシュシステムでは整数をキー・要素として使う。このハッシュシステムは七個のバケット（Bucket）を持っていて、各バケットは整列された連結リストである。キー・要素の該当するバケットの番号はキーを剰余演算して獲得する。例えばキー・要素が $51$ の場合、$51$ を $7$ で除算して、剰余である $2$ がバケットの番号になる。この図はハッシュテーブルの現在の状態を表している（$\varnothing=\mathrm{NIL}$）。

• (a) 現在のハッシュテーブルに $12,19,24,10$ を逐次に挿入して結果を図示せよ。
• (b) 受け取ったキー・要素を該当するバケットから削除する疑似コードを記述せよ。各バケットは整列された連結リストであることを忘れずに。

题目描述

(1) 将二进制位串 10000101000000111100100110010001 表示的 IPv4 地址写成点分十进制形式。

(2) 对上列 Employee、Sales、Hours 三张关系表，以 Employee.EID = Sales.EID = Hours.EID 为条件进行连接（JOIN），写出结果表。

(3) 上面的进程 A 与进程 B 使用 "read"、"write" 两个信号量实现互斥，但发生了死锁。只修改进程 B，在尽量缩小临界区的同时消除死锁。 list.count() 与 list.get_first()，以及 list.add_last() 与 list.remove_first() 分别不能同时调用，否则可能破坏数据，因此必须使用信号量。

(4) 一个哈希系统以整数为键和元素，共有七个桶，每个桶保存一条有序链表。桶编号为键除以 $7$ 的余数，例如 $51$ 对应桶 $2$。初始状态如上图所示，$\varnothing$ 表示空指针：桶 $0$ 为 $112$，桶 $1$ 为 $456$，桶 $2$ 为 $44$，桶 $3,4,5$ 为空，桶 $6$ 为 $13\to328$。

• (a) 依次插入 $12,19,24,10$，画出最终结果。
• (b) 写出从相应桶中删除给定键的伪代码，并利用各桶的链表已经有序这一性质。

Kai

(1)

左から $8$ ビットずつ区切ると、

$$10000101\quad00000011\quad11001001\quad10010001$$

であり、各部分を十進数に直すと $133,3,201,145$ となる。したがって、

$$\boxed{133.3.201.145}$$

である。

(2)

三つの関係に共通する EID は $347$ と $199$ である。等しい EID 列を一列にまとめて表示すると、結合結果は次のようになる。

EID	Age	Name	Branch	Amount	Hours
347	25	Alex	LA	189000	62
199	27	Sam	NY	251000	67

(3)

A が "read" を保持して "write" を待ち、B が "write" を保持して "read" を待つと、循環待ちが生じる。B では、追加処理が終わった時点で "write" を解放してから "read" を取得する。

lock "write" semaphore
list.add_last(new_value)
unlock "write" semaphore

lock "read" semaphore
n = list.count()
unlock "read" semaphore

if (n > 10000) {
    print("too many")
}

ここで n は B の局所変数である。B の list.add_last() と A の list.remove_first() は "write" により、B の list.count() と A の list.get_first() は "read" により相互排除される。B はセマフォを保持したまま別のセマフォを待たないので、循環待ちがなくなる。

追加してから要素数を調べる処理順序を保ち、共有リストに触れない判定と出力はセマフォを解放した後に行う。したがって、B の各クリティカル領域は保護すべき一回のリスト操作だけになる。

(4)

(a)

$$12\bmod7=5,\qquad19\bmod7=5,\qquad 24\bmod7=3,\qquad10\bmod7=3.$$

昇順を保って挿入すると、バケット $3$ は $10\to24$、バケット $5$ は $12\to19$ となる。

(b)

table[i] はバケット $i$ の先頭ノード、value はノードの値、next は次のノードへのポインタとする。key mod 7 は $0$ 以上 $6$ 以下の剰余を返す。

procedure delete_key(key):
    i = key mod 7
    prev = NIL
    curr = table[i]

    while curr != NIL:
        if curr.value >= key:
            break
        prev = curr
        curr = curr.next

    if curr == NIL:
        return false
    if curr.value != key:
        return false

    if prev == NIL:
        table[i] = curr.next
    else:
        prev.next = curr.next

    free(curr)
    return true

リストは昇順なので、key より大きい値に到達した時点で探索を打ち切れる。削除対象が先頭ならバケットの先頭ポインタを、それ以外なら直前のノードの next を更新する。空のバケットやキーが存在しない場合にはリストを変更しない。

Reference

• 京都大学公式問題：2025年8月2日実施、情報学基礎、PDF 6–8ページ
• ymogi：2025年8月実施（2026年入学）社会情報学コース・基礎科目解答、大問2