11183 words

56 minutes

Osaka University IST Graduate Entrance Exam: Bilingual Revision Cards (2009-2024)

2026-07-10

ノート / Notes

院試 / Grad Prep

大阪大学院入試：情報科学研究科 2009〜2011年記述式問題（簡答題）英日バイリンガル暗記カード#

本ドキュメントは、大阪大学大学院情報科学研究科の過去問（2009年〜2011年）におけるすべての記述式問題（簡答題）を、日本語と英語の双方で記述した暗記用ガイドです。

目次#

2009年記述式問題
2010年記述式問題
2011年記述式問題
2024年記述式問題
2023年記述式問題
2022年記述式問題
2021年記述式問題

2009年記述式問題#

Q1-5: クイックソートの最悪時間計算量が $O(n^2)$ になる証明#

日本語 (Japanese): 最悪の場合、各分割（Partition）において、ピボットが常に現在の区間の最大値または最小値となる。これにより、サイズ $n$ の問題がサイズ $n-1$ と $0$ の二つの部分問題に分割される。再帰の深さが $O(n)$ に退化し、各階層の比較回数の総和は $\sum_{i=1}^{n} (i-1) = \frac{n(n-1)}{2} = O(n^2)$ となる。
英語 (English): In the worst case, each partition yields an extremely unbalanced split where the pivot is always the maximum or minimum element of the current subarray. This divides the problem of size $n$ into subproblems of size $n-1$ and $0$ . The recursion tree depth degenerates to $O(n)$ , and the total number of comparisons across all levels becomes $\sum_{i=1}^{n} (i-1) = \frac{n(n-1)}{2} = O(n^2)$ .
中文解析 (Chinese Analysis): 最坏情况下，快速排序退化为每次划分子数组时，基准元素（Pivot）总是子数组中的最大值或最小值。这导致递归树深退化为 $O(n)$ ，每一层需要与剩余的所有元素进行比较，总比较次数为 $O(n^2)$ 。通常在数组已经完全有序（正序或逆序）时且总是选择端点作为基准时触发。

Q2-1-2: プロセスのメモリ空間の独立性とコピーオンライト (COW)#

日本語 (Japanese): 親プロセスと子プロセスは完全に独立した仮想メモリ空間を持つ。物理メモリを節約するため、fork() 直後は同一の物理ページフレームを指し、「読み取り専用」に設定される。いずれかのプロセスが書き込みを試みると、ページフォルトが発生し、OSが物理ページを複製してページテーブルを更新する（書き込み時コピー / Copy-on-Write）。
英語 (English): The parent and child processes have completely independent virtual memory spaces. To save physical memory, immediately after fork(), their page tables map to the same physical page frames marked as read-only. When either process attempts to write to a page, a page fault is triggered, and the OS allocates a new page frame, copies the content, and updates the page table (Copy-on-Write).
中文解析 (Chinese Analysis): 写时复制（Copy-on-Write, COW）是一种内存管理优化技术。通过 fork() 创建子进程时，并不立刻复制父进程的整个物理内存空间，而是将页表指向相同的物理内存页，并将这些页设为只读。只有当其中一个进程尝试对这些内存页进行写操作时，CPU 才会触发缺页异常（Page Fault），操作系统此时复制该物理页并更新页表映射，从而在减少不必要内存复制的同时保证了父子进程内存空间的独立性。

Q2-1-3: 孤児（Orphan）プロセスとゾンビ（Zombie）プロセスの違い#

日本語 (Japanese):
- 孤児プロセス: 子プロセスの実行中に親プロセスが先に終了した状態。子プロセスは init プロセス（PID 1）に里親（Adopt）され、その終了時に資源が回収される。
- ゾンビプロセス: 子プロセスがすでに終了しているが、親プロセスが wait() 等のシステムコールを実行しておらず、プロセス制御ブロック（PCB）内の終了ステータス情報が未回収のまま残っている状態。
英語 (English):
- Orphan Process: A child process whose parent process has terminated first while the child is still running. The child is adopted by the init process (PID 1), which reaps it upon termination.
- Zombie Process: A terminated child process whose exit status has not yet been read by its parent process via the wait() system call, leaving its process control block (PCB) in the process table.
中文解析 (Chinese Analysis): 孤儿进程（Orphan）指父进程已先终止，而子进程还在运行，会被 init 进程（PID 1）领养并自动回收；僵尸进程（Zombie）则是子进程已终止，但父进程尚未调用 wait() 进行状态收集，导致子进程的进程控制块（PCB）依然滞留在系统中占用资源。

Q2-2: ページフォルト（欠ページ例外）の発生とカーネルによる処理フロー#

日本語 (Japanese):
1. プロセスが仮想アドレスにアクセスし、MMUがページテーブルを参照して有効ビット（Valid Bit）が0であることを検出する。
2. ハードウェアがページフォルト例外を発生させ、CPUがカーネルモードに移行して状態を保存する。
3. OSの例外ハンドラが起動し、空き物理フレームを探し、必要に応じてページ置換を行う。
4. スワップ領域から該当ページをメモリにロードする（ディスクI/O）。
5. ページテーブルの物理フレーム番号と有効ビットを更新する。
6. 中断された命令を再実行し、プロセスは透過的に実行を継続する。
英語 (English):
1. The CPU accesses a virtual address, and the MMU finds that the corresponding page table entry has a valid bit of 0.
2. A page fault exception is triggered, causing a hardware trap to kernel mode and saving the CPU registers.
3. The OS page fault handler is invoked to locate a free page frame, performing page replacement if necessary.
4. The required page is read from the disk swap space into the physical memory frame (disk I/O).
5. The OS updates the page table entry with the physical frame number and sets the valid bit to 1.
6. The interrupted instruction is restarted, allowing the process to resume execution seamlessly.
中文解析 (Chinese Analysis): 缺页异常处理流程：CPU访问无效虚拟页面时触发中断，挂起进程并切到内核态。OS处理程序寻找空闲物理页框（满则置换页换出到磁盘），通过磁盘I/O将目标页读入物理页框，随后更新页表映射关系并将有效位置1，最后让CPU恢复并重新执行先前被中断的访问指令。

Q2-3: ページ置換アルゴリズム FIFO と LRU の比較#

日本語 (Japanese):
- FIFO (First-In First-Out): 最も早くメモリに入ったページを置換対象とする。キューで簡単に実装できるが、頻繁にアクセスされるページを置換する恐れがあり、物理フレームを増やしても欠ページ率が上昇する「Beladyの例外」が発生しうる。
- LRU (Least Recently Used): 最も長い間アクセスされていないページを置換対象とする。局所性の原理に基づいておりヒット率が高いが、アクセス履歴（時間情報）を記録するためのハードウェアサポートが必要で、実装コストが高い。
英語 (English):
- FIFO (First-In, First-Out): Replaces the oldest page in memory. It is simple to implement using a queue, but may evict heavily used pages and is susceptible to Belady’s anomaly, where increasing the number of physical frames increases the page fault rate.
- LRU (Least Recently Used): Replaces the page that has not been accessed for the longest time based on temporal locality. It offers high hit rates but requires hardware timestamps or stacks to track access history, incurring high implementation overhead.
中文解析 (Chinese Analysis): FIFO算法最先入页最先出，结构简单但易产生Belady异常并换出高频页；LRU基于时间局部性置换最久未访问页，效果好，但必须借助硬件（如计数器/栈）维护访问时间记录，硬件与运行开销大。

Q11-1: ARQ方式（Stop-and-Wait, Go-back-N, Selective Repeat）における送受信側のバッファ・ウィンドウ管理機能#

日本語 (Japanese):
- Go-back-N方式において必要だが、Stop-and-Wait方式で不要な機能:
  1. 送信側における送信済未確認データフレーム数の管理: Stop-and-Waitでは未確認フレーム数が最大1であるのに対し、Go-back-Nでは最大 $N$ 個のフレームが送信可能なため、ウィンドウ制限のために送信数を管理する必要がある。
  2. 送信側における最大 $N$ 個のデータフレームバッファの管理: 再送発生時に備えて、送信済で未確認のフレームを最大 $N$ 個バッファに保持して管理する必要がある。
- Selective Repeat方式において必要だが、Go-back-N方式で不要な機能:
  1. 受信側における受信済データフレーム番号の管理: Go-back-Nは順序通りに受信するため「期待する次のシーケンス番号」のみを保持すればよいが、Selective Repeatは順不同の到着を許容するため、どのフレームを受信したかを個別にビットマップ等で管理する必要がある。
  2. 受信側における最大 $N$ 個のデータフレームバッファの管理: 欠損フレームが再送されて順序が揃うまで、順不同で到着したフレームを一時的に保持するための受信バッファを管理する必要がある。
英語 (English):
- Functions needed in Go-back-N but NOT in Stop-and-Wait:
  1. Management of the number of sent but unacknowledged data frames at the sender: Stop-and-Wait only has at most 1 in-flight frame, whereas Go-back-N allows up to $N$ frames, requiring the sender to track this count to enforce the window limit.
  2. Management of a buffer of at most $N$ data frames at the sender: The sender must buffer up to $N$ sent but unacknowledged frames to enable retransmission in case of loss or corruption.
- Functions needed in Selective Repeat but NOT in Go-back-N:
  1. Management of received data frame sequence numbers at the receiver: Go-back-N only accepts in-order frames and needs to store only the next expected sequence number. Selective Repeat allows out-of-order arrival, requiring the receiver to track which specific sequence numbers have been received.
  2. Management of a buffer of at most $N$ data frames at the receiver: Go-back-N discards out-of-order frames immediately, whereas Selective Repeat must buffer up to $N$ out-of-order frames until the missing frame is retransmitted and the sequence can be delivered in order.
中文解析 (Chinese Analysis): GBN相比Stop-and-Wait需在发送端维护大小为N的已发送未确认缓冲队列及滑动窗口，以便超时能全部重传。SR相比GBN需在接收端维护大小为N的乱序接收缓冲并跟踪各帧独立确认标志，以支持非顺序的选择性接收和暂存，待接收窗口内帧按序到齐后再交付上层。

Q11-5: ARQ方式の誤り率に対する平均スループットの変化特性と理由#

日本語 (Japanese):
- 横軸の指標: フレーム誤り率 ( $P_e$ )
- 方式と曲線の対応: 上から順に Selective Repeat ARQ (直線)、Go-back-N ARQ (下凸の曲線)、Stop-and-Wait ARQ (直線)。
- 理由:
  1. Selective Repeat ARQ: エラーが発生したフレームのみを個別に再送するため、伝送効率は誤り率に対し線形に低下し（ $\eta = 1 - P_e$ ）、最も高い直線となる。
  2. Go-back-N ARQ: エラーが発生するとそれ以降の未確認フレームも含めて全フレームを再送するため、誤り率の増加に伴い再送オーバーヘッドが非線形に急増し（ $\eta = \frac{1-P_e}{1+(M-1)P_e}$ 、ここで $M$ はラウンドトリップ内のフレーム数）、中間の曲線となる。
  3. Stop-and-Wait ARQ: 1フレームごとに確認応答（ACK）を待つため、無エラー時でも最大利用率が $50\%$ に制限され、スループットは $500(1-P_e)$ bps の最も低い直線となる。
英語 (English):
- Horizontal Axis Metric: Frame error rate ( $P_e$ )
- Mapping: From top to bottom: Selective Repeat ARQ (straight line), Go-back-N ARQ (downward-curving line), Stop-and-Wait ARQ (straight line).
- Reasons:
  1. Selective Repeat ARQ: Since only the corrupted or lost frames are retransmitted, the efficiency decreases linearly with the frame error rate $P_e$ ( $\eta = 1 - P_e$ ), yielding the highest straight line.
  2. Go-back-N ARQ: A single frame corruption triggers the retransmission of all subsequent unacknowledged frames in that round-trip, scaling the overhead non-linearly with $P_e$ ( $\eta = \frac{1-P_e}{1+(M-1)P_e}$ ), forming the middle curving line.
  3. Stop-and-Wait ARQ: The sender must wait for an ACK after every frame, limiting the maximum channel utilization to $50\%$ even when $P_e = 0$ . Its throughput is $500(1-P_e)$ bps, resulting in the lowest straight line.
中文解析 (Chinese Analysis): 横坐标为帧错误率。三条线由上至下依次为SR、GBN和Stop-and-Wait。SR仅重传出错帧，吞吐效率随错误率线性下降；GBN单帧出错导致后续帧连带重传，开销非线性剧增；Stop-and-Wait因必须等单帧确认而极大限制度量，即使无错时吞吐率依然是最低的直线。

2010年記述式問題#

Q2-3: 1の補数における循環桁上げ（End-around Carry）の数学的導出#

日本語 (Japanese): 1の補数における負数 $X$ の無符号値は $(X)_2 = X_{1c} + 2^n - 1$ である。加算器で $(A)_2 + (B)_2 = 2^n + [2^n - 1 + (A)_{1c} + (B)_{1c}] - 1$ を計算すると、最上位桁あふれの $2^n$ が発生し、加算器の $n$ ビット出力は目的値より 1 小さくなる。このため、最上位桁の桁上げ（Carry-out）出力を最下位桁の桁上げ（Carry-in）入力にフィードバック（加算）する「循環桁上げ」が必要となる。
英語 (English): In 1’s complement, the unsigned value of a negative number $X$ is $(X)_2 = X_{1c} + 2^n - 1$ . Adding two numbers yielding $(A)_2 + (B)_2 = 2^n + [2^n - 1 + (A)_{1c} + (B)_{1c}] - 1$ produces a carry-out of $2^n$ , leaving the remaining $n$ -bit output 1 less than the desired value. Hence, “end-around carry” is required to feed back the carry-out from the MSB into the carry-in of the LSB to add the missing 1.
中文解析 (Chinese Analysis): 1的补数中负数用 $2^n - 1 - |X|$ 表示。加法运算若向最高位产生权值为 $2^n$ 的进位时，实际在模 $2^n - 1$ 的空间下应折算为加1，因此必须将最上位的进位输出（Carry-out）加回到最下位（Carry-in）做补偿。

Q2-4: デッカー（Dekker）のアルゴリズムにおける相互排除条件#

日本語 (Japanese): 相互排除を実現するためには、(1) 相互排除条件、(2) デッドロック回避条件、(3) 有限待ち条件の3つを満たす必要がある。デッカーのアルゴリズムは、意図フラグ（c1, c2）と優先権変数（turn）を組み合わせることで、両プロセスが同時にアクセスを希望した際のデッドロックを回避し、これらの条件をすべて満たす。
英語 (English): To achieve mutual exclusion, three conditions must be satisfied: (1) Mutual Exclusion, (2) Progress (avoidance of deadlock), and (3) Bounded Waiting. The Dekker algorithm combines intent flags (c1, c2) and a turn variable to resolve conflicts when both processes attempt to enter the critical section simultaneously, successfully satisfying all three requirements without deadlock.
中文解析 (Chinese Analysis): 满足互斥三大原则：互斥进入、前进（空闲不阻塞进入）、有限等待（不饥饿）。Dekker通过意图标志配合turn变量轮流表态并在冲突时退让特权，彻底消除死锁和饥饿，保证了全部互斥条件。

Q11-2-2: ルーティングメトリック（ホップ数と帯域幅/遅延）の定義と欠点#

日本語 (Japanese):
- ホップ数: 経由するルータの数。欠点は、リンクの帯域幅（通信速度）や遅延を無視するため、高速な遠回り経路ではなく低速な直通経路を選択してしまうこと。
- 帯域幅/遅延: リンクの物理的な伝送速度。欠点は、トラフィックの動的な混雑度（キューイング遅延）を考慮しないため、輻輳している経路にパケットを送り続けてしまうこと。
英語 (English):
- Hop Count: The number of routers a packet passes through. The drawback is that it ignores link bandwidth and propagation delay, potentially choosing a slow direct path over a fast path with more hops.
- Bandwidth/Delay: The physical transmission speed of a link. The drawback is that it often reflects static capacities and fails to account for dynamic network congestion (queueing delay), leading to packet forwarding along heavily congested links.
中文解析 (Chinese Analysis): 跳数是以路由器数为开销度量，缺点是忽略带宽，易选低速短程；带宽/延迟度量反映物理链路容量，缺点通常是静态的，忽视了队列积压带来的动态拥塞开销。

Q11-2-3: フラッディング制御とループ防止メカニズム#

日本語 (Japanese):
1. TTL（生存時間）メカニズム: パケットヘッダ内のTTLフィールドをルータが経由するたびに1減らし、0になった時点でパケットを破棄することで、ネットワーク内での無限ループを防ぐ。
2. 重複パケット検出（履歴テーブル法）: 各ルータがすでに転送したパケットのID（履歴）を記録し、同一IDのパケットを再度受信した場合は転送せず破棄する。
英語 (English):
1. TTL (Time-to-Live) Mechanism: The TTL field in the packet header is decremented by 1 at each router, and the packet is discarded when TTL reaches 0, preventing infinite looping in networks with cycles.
2. Duplicate Packet Detection (History Table): Each router records the IDs of recently forwarded packets. If a packet with a duplicate ID is received, the router drops it instead of forwarding it again.
中文解析 (Chinese Analysis): TTL每经一跳减1，归0时丢弃包，防止循环数据包在网络拓扑中无限循环；重复报文检测（历史表法）通过记录近来转发过的包标识，收到重包直接丢弃不再扩散。

Q11-2-4: RIP と OSPF の比較（トポロジサイズと収束速度）#

日本語 (Japanese):
- トポロジデータのサイズ: RIPは隣接ルータとの間でルーティングテーブル全体（データサイズ $O(N)$ ）を交換する。OSPFはリンク状態（LSA）をフラッディングし、全ルータが同じトポロジマップ（LSDB）を持つため、データサイズは大きくなる。
- 収束速度: RIPは30秒ごとの周期的な情報交換を行うため収束が遅く、無限大カウント問題（Count-to-Infinity）がある。OSPFはイベント駆動型で変化時に即座にフラッディングし、ダイクストラで高速に再計算するため、収束速度が極めて速い。
英語 (English):
- Topology Data Size: RIP exchanges entire routing tables ( $O(N)$ size) with neighbors. OSPF floods link states (LSAs) so that all routers build a complete topology map (LSDB), which requires larger memory and message sizes.
- Convergence Speed: RIP updates periodically every 30 seconds, leading to slow convergence and vulnerability to the count-to-infinity problem. OSPF is event-driven, immediately flooding changes and recalculating paths using Dijkstra, resulting in extremely fast convergence.
中文解析 (Chinese Analysis): 信息交换：OSPFルータ广播自己接口邻接LSA，网络各点通过洪泛实现LSDB拓扑全同步；Dijkstra执行：ルータ以自身为源根节点，从LSDB完整路径树上运算求单源最短树，进而写表更新。

2011年記述式問題#

Q3-1-2-1: 同期型パイプラインにおけるクロックサイクル $\tau$ の制約#

日本語 (Japanese): クロックサイクル時間 $\tau$ は、各ステージの独立した機能ブロックにおける最大遅延時間以上でなければならない。
英語 (English): The clock cycle time $\tau$ must be greater than or equal to the maximum delay time of any individual stage’s independent functional block.
中文解析 (Chinese Analysis): 同步流水线的时钟周期必须大于或等于最慢的流水阶段延迟加上寄存器锁存开销（ $\tau \ge \max(T_{stage}) + d_{reg}$ ），以确保慢速阶段也能在一个周期内算完，时钟周期不能小于最长阶段的执行时间。

Q3-2-2-3: ファイルシステムのブロックサイズが空間効率と転送時間に及ぼす影響#

日本語 (Japanese):
- 空間効率: ブロックサイズが小さいほど、小ファイル保存時の内部フラグメンテーション（内部断片化）が抑えられ、ディスク容量の利用効率が高くなる。
- 転送速度: ブロックサイズが大きいほど、同一ファイルに対するシーク（Seek）回数が減少し、ボトルネックである機械的遅延が低減されるため、非連続ファイル配置時の平均転送時間が劇的に短縮される。
英語 (English):
- Space Efficiency: Smaller block sizes reduce internal fragmentation when storing small files, leading to higher disk capacity utilization.
- Transfer Performance: Larger block sizes reduce the number of seeks required for a given file size, mitigating the mechanical delay bottleneck and drastically shortening the average transfer time for non-contiguous files.
中文解析 (Chinese Analysis): 空间效率：块越小，尾部空隙（内部断片）浪费越少，存小文件利用率高；传输时间：块越大，读取大文件所需的机械寻道开销次数越少，非连续文件传输性能越佳。

Q11-2-4: OSPF ルーティングプロトコルにおける情報交換とダイクストラの実行#

日本語 (Japanese):
- ノードの動作と情報交換: 各ルータは、自身の隣接リンクの状態をLSAとしてネットワーク全体にフラッディングする。これにより、すべてのルータが同じリンク状態データベース（LSDB）を共有し、ネットワークの同一トポロジマップを構築する。
- ダイクストラの実行方法: 各ルータは、自身を始点ノード（根）とするダイクストラアルゴリズムを独立して実行し、最短経路木（SPT）を計算して、ルーティングテーブルを構築する。
英語 (English):
- Node Operations and Information Exchange: Each router floods its adjacent link states as LSAs to the entire network. Consequently, all routers share the identical LSDB, building a unified map of the network topology.
- Dijkstra Execution: Each router independently executes Dijkstra’s algorithm with itself as the source node (root) to calculate a Shortest Path Tree (SPT), constructing its routing table.
中文解析 (Chinese Analysis): 信息交换：OSPFルータ广播自己接口邻接LSA，网络各点通过洪泛实现LSDB拓扑全同步；Dijkstra执行：ルータ以自身为源根节点，从LSDB完整路径树上运算求单源最短树，进而写表更新。

Q11-2-5: 静的ルーティングと動的ルーティングの主な違い、利点・欠点#

日本語 (Japanese):
- 主な違い: 静的ルーティングでは、管理者が手動でルーティングテーブルを設定し、トポロジ変化時に自動更新されない。動的ルーティングでは、ルータがプロトコルを実行して制御情報を自動で交換し、トポロジ変化に応じてテーブルを更新する。
- 動的ルーティングの利点: 障害発生時に代替経路へ自動的に迂回する（耐障害性）、新規ノード追加時に自動で経路を学習するため管理コストが低い（スケーラビリティ）。
- 動的ルーティングの欠点: 制御情報の交換と経路計算により、帯域幅とCPU・メモリ資源を消費する（システムオーバーヘッド）、不正更新や設定ミスによるルーティングループや脆弱性が発生しやすい。
英語 (English):
- Key Difference: In static routing, routing tables are manually configured by administrators and do not update automatically when the topology changes. In dynamic routing, routers run routing protocols to exchange control information and automatically update routing tables in response to topology changes.
- Advantages: Automatic rerouting to backup paths upon link failures (Fault Tolerance), and automatic path discovery when new nodes are added, reducing administrative overhead (Scalability).
- Disadvantages: Consumes network bandwidth and CPU/memory resources (System Overhead), and is susceptible to routing loops or security vulnerabilities from misconfigurations or malicious updates.
中文解析 (Chinese Analysis): 区别：静态路由手动设、无自主感知；动态路由靠协议自动协商交互并实时改变。动态优点在于能自动改道应对链路失效，少人工干预；缺点在于产生协议报文带宽CPU资源开销，可能发生路由环路与安全毒化。

2024年記述式問題#

Q1-2-3: 二分挿入ソートで比較回数が最小となる初期配列の条件と理由#

日本語 (Japanese):
- 条件: 初期配列が降順に整列されていること。
- 理由: 各イテレーションにおいて、新要素がソート済み部分配列の先頭（インデックス 0）に挿入される場合、二分探索の判定は常に左側へ分岐し、比較回数は最小の $\lfloor \log_2(i+1) \rfloor$ となる。これを満たすには、新要素が常に既存の全要素より小さくなければならないため。
英語 (English):
- Condition: The initial array is sorted in descending order.
- Reason: In each iteration, if the new key is inserted at index 0, the binary search always branches to the left, minimizing the number of comparisons to $\lfloor \log_2(i+1) \rfloor$ . This requires each new key to be smaller than all elements in the sorted subarray, which is satisfied by descending order.
中文解析 (Chinese Analysis): 条件：初始数组为降序排列。原因：折半插入法中，如新插入数小于排序序列的所有数，折半查找分歧一律向左，每次刚好达到查找下限 $\lfloor \log_2(i+1) \rfloor$ （无多余判等比较）。降序排列时，新读入的元素总是当前所有已处理元素中的最小值，恰好能触发此最少比较回数。

Q2-2-1: 最適なページ置換アルゴリズム（OPT）における置換対象の選択基準#

日本語 (Japanese): メモリ内にあるページのうち、今後最も長い時間参照されない（または二度と参照されない）ページを優先的に置き換え対象とする。
英語 (English): The page in memory that will not be referenced for the longest duration (or will never be referenced again) in the future is prioritized for eviction.
中文解析 (Chinese Analysis): 页面调度时，优先选择那些未来最长周期不会被读取（或再也不用读）的页换出。这是非前瞻性实际操作的下限（作为对比参考），无法在运行时预测实现。

Q5-1: CSMA/CDにおける衝突検出時の動作（空欄X）#

日本語 (Japanese): 衝突を検出した場合には直ちに送信を中止し，ランダムな時間待機した後に再送を行う。
英語 (English): aborts transmission immediately if a collision is detected, and performs retransmission after waiting for a random time.
中文解析 (Chinese Analysis): 一旦侦测出信道碰撞冲突，节点需即刻停发，并抛出拥塞阻塞噪声以通知全网，然后基于退避算法得出一个随机等候间隔后方可发起重试。

Q5-2: CSMAにおいて伝送媒体の伝搬遅延時間が長くなると、単位時間あたりに衝突なしに受信されるフレーム数が減少する理由#

日本語 (Japanese): 伝搬遅延時間が増大すると、他の端末に信号が届くまでの時間（衝突窓）が長くなり、載波検出で「空き」と誤認して送信を開始し、フレームの衝突が起きる確率が増大するため。
英語 (English): An increase in propagation delay expands the vulnerable period (collision window), during which other nodes may falsely sense the channel as idle and start transmitting, increasing the collision probability.
中文解析 (Chinese Analysis): 延迟大代表发出的电波尚未抵达远端，该段时间（碰撞窗口）变宽。监听误判为空白便发信，从而极易在中途撞车，减少了顺畅投送率。

Q5-3-1: キャリアセンスとフレーム衝突の語句を用いて隠れ端末問題を説明せよ#

日本語 (Japanese): 無線端末1と2は互いに電波が届かずキャリアセンスで検出できないため、双方が送信すると、双方の電波が届く范围にある無線端末3でフレーム衝突が発生する。
英語 (English): Since Terminals 1 and 2 are out of range of each other, they cannot detect each other’s signals via carrier sense. When both transmit, their signals overlap at Terminal 3, causing a frame collision.
中文解析 (Chinese Analysis): 无线端点A和B相距太远彼此听不见对方，不能由载波监听觉察对方发送。一旦同时向共用中继C写数据，在C接收天线处重叠，造成严重的帧冲突损坏。

Q5-3-2: CSMA/CAにおけるRTS/CTSを用いた隠れ端末問題の対処手順#

日本語 (Japanese):
1. 送信側がデータ送信の前に RTS を送信する。
2. 受信側が送信所要時間情報を含む CTS をブロードキャストする。
3. 隠れ端末は CTS を受信し、その時間情報に基づいて NAV を設定し送信を控える。
4. 送信側はデータを安全に送信し、受信側から ACK を受信する。
英語 (English):
1. The sender transmits an RTS frame before data transmission.
2. The receiver broadcasts a CTS frame containing the transmission duration.
3. The hidden terminal hears the CTS and sets its NAV to defer transmission.
4. The sender transmits the data frame safely and receives an ACK from the receiver.
中文解析 (Chinese Analysis): 解决过程：发送方发送短小的RTS报文请求，接收方返回CTS覆盖全局；听到CTS的隐蔽终端通过NAV静默避让；发送方在无干扰下畅快发完整Data并收ACK确认。

2023年記述式問題#

Q1-1-2: 線形探索法ハッシュテーブルの挿入ループ終了条件（互いに素）#

日本語 (Japanese): 探索ステップ幅（\texttt{delta}）とハッシュ表のサイズ（ $N$ ）が互いに素であること（ $\gcd(\text{delta}, N) = 1$ ）。これにより、探査シーケンスがすべてのスロットを巡回し、空きがあれば必ず発見して挿入ループが終了する。
英語 (English): The step size (\texttt{delta}) and the hash table size ( $N$ ) must be coprime ( $\gcd(\text{delta}, N) = 1$ ). This ensures the probe sequence traverses all slots, guaranteeing that an empty slot is found and the insertion loop terminates.
中文解析 (Chinese Analysis): 条件：探测步长 \texttt{delta} 与哈希表大小 $N$ 互质，即 $\gcd(\text{delta}, N) = 1$ 。原因：只有当两数互质时，探测序列才会生成全体哈希槽位的一个满排列，从而保证在表未满时必能发现空闲插槽并终止插入循环。

Q1-3-2: コックーハッシュ（Cuckoo Hashing）の最悪時間计算量と理由#

日本語 (Japanese): 最悪時間計算量は $\mathcal{O}(1)$ （定数時間）。各キーは2つのハッシュ関数に対応する特定の2つのスロットにしか格納されないため、高負荷时でも最大2回のメモリ参照で有無を判定できるため。
英語 (English): The worst-case time complexity is $\mathcal{O}(1)$ (constant time). Since each key can only reside in one of the two specific slots mapped by the two hash functions, a search requires at most two memory references regardless of load.
中文解析 (Chinese Analysis): 最坏时间复杂度： $\mathcal{O}(1)$ （常数级别）。原因：布谷鸟哈希保证任何键值最多只会被哈希至两个特定的插槽中（由 $h_1(\text{key})$ 和 $h_2(\text{key})$ 决定）。因此不管当前装载因子多高，查找时最多只需执行 2 次内存访问。

Q2-2-3: ページングシステムにおける Dirty Bit (変更ビット) の貢献とメカニズム#

日本語 (Japanese): ライトバック方式において、置換対象ページの変更ビットが0（未変更）ならディスク書き戻しを省略し直接上書きし、1（変更あり）の時のみディスクへ書き戻す。これにより、不要なディスク書き込み（I/O）を回避してシステムを高速化する。
英語 (English): Under a write-back policy, if the dirty bit of the page to be evicted is 0 (unmodified), the writeback is skipped and the page is overwritten directly. Disk writeback is only performed if the bit is 1. This avoids unnecessary disk writes (I/O) to accelerate the system.
中文解析 (Chinese Analysis): 贡献与机制：在写回策略中，脏位（Dirty Bit）用于标识物理页面载入后是否被写过。当需要置换页面时：若脏位为0，说明其未被修改，与磁盘备份完全一致，可直接覆盖以省略磁盘写I/O；若脏位为1，则必须先将新数据写回磁盘再覆盖。此举大幅免去了对未修改（干净）页面的磁盘写延迟。

Q5-2: TCPがセグメントの紛失を検出する2つの代表的な仕組み#

日本語 (Japanese):
1. 送信後に一定时间ACKが届かないことによる「タイムアウト（重伝タイムアウト）」，2) 同一セグメントに対するACKを連続して3回受信すること（「3回の重複ACK」による高速再送）。
英語 (English):
1. Retransmission Timeout (RTO), where a sent segment’s timer expires before receiving an ACK. 2) Three duplicate ACKs (Fast Retransmit), where receiving three identical ACKs triggers retransmission without waiting for the timer.
中文解析 (Chinese Analysis): 机制：1) 超时重传机制（RTO），即发送段后如果在设定的定时器周期内没收到应答确认，则触发超时重发；2) 快速重传机制（3次冗余ACK），即连续接收到 3 个相同的确认序列号（表示某段之后的数据已到但该段未到），则不等定时器超时即刻重传。

2022年記述式問題#

Q1-1: クイックソートのアルゴリズム名称#

日本語 (Japanese): クイックソート（Quick Sort）。
英語 (English): Quick Sort.
中文解析 (Chinese Analysis): 快速排序（Quick Sort）。基于分治策略的高效排序算法。

Q1-3: クイックソートの非安定性を示すデータの条件#

日本語 (Japanese): 図2の data.txt の2行目の得点（id=1 の得点）を60から 100 に書き換える。これにより、id=1 と id=5 の得点が同じ100になり、整列後の出力では id=5 が id=1 より前に並ぶ（順序が逆転する）ため、アルゴリズムが非安定であることが示される。
英語 (English): Change the score on the second line of data.txt (the score for id=1) from 60 to 100. This makes the scores of id=1 and id=5 both equal to 100. After sorting, id=5 (the pivot) is placed before id=1, reversing their original relative order and proving that the algorithm is unstable.
中文解析 (Chinese Analysis): 将 data.txt 第二行（即 id=1 的数据）的得分从 60 修改为 100。修改后，id=1 与 id=5 的得分均为 100。在 Lomuto 划分排序过程中，id=5（初始作为 Pivot）被交换到了 id=1 的前面，导致相同键值元素的相对位置发生逆转，从而用实例证明了该快速排序算法是非稳定的。

Q1-5: クイックソートの最悪時間計算量とその理由#

日本語 (Japanese): 最悪時間計算量は $\mathcal{O}(n^2)$ である。配列がすでに昇順または降順に整列されている（またはすべての要素が同じ）場合、選択されるピボットが常に部分配列の最大値または最小値となる。これにより、分割後の部分問題のサイズが常に $n-1$ と $0$ という極端に不均等な分割になり、再帰の深さが $\mathcal{O}(n)$ に退化し、比較回数の総和が $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \mathcal{O}(n^2)$ になるため。
英語 (English): The worst-case time complexity is $\mathcal{O}(n^2)$ . This occurs when the chosen pivot at each partition step is always the minimum or maximum element of the subarray (e.g., when the array is already sorted). This leads to extremely unbalanced partitions of sizes $n-1$ and $0$ . The recursion depth degenerates to $\mathcal{O}(n)$ , and the total number of comparisons becomes $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \mathcal{O}(n^2)$ .
中文解析 (Chinese Analysis): 最坏时间复杂度为 $\mathcal{O}(n^2)$ 。原因为：当输入数组已经完全有序（升序或降序）或者所有元素均相等时，每次划分选择的基准元素（Pivot）都恰好是子数组的最大值或最小值。这导致子问题划分极度不均匀（每次被拆分为大小为 $n-1$ 和 $0$ 的两个子数组），递归深度退化到 $\mathcal{O}(n)$ 层，总比较次数为等差数列求和 $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \mathcal{O}(n^2)$ 。

Q2-1: セマフォ値が負の時の絶対値の意味#

日本語 (Japanese): セマフォの値が負のとき、その絶対値 $|s|$ は、そのセマフォに関連付けられた待ちキューでブロックされ、待機状態（waiting state）になっているプロセスの数を表す。
英語 (English): When the semaphore value $s$ is negative, its absolute value $|s|$ represents the number of processes that are blocked and currently in the waiting state in the queue associated with that semaphore.
中文解析 (Chinese Analysis): 当信号量的值 $s$ 为负数时，其绝对值 $|s|$ 代表当前由于等待该信号量资源而被阻塞、正处于等待状态（Waiting State）的进程数量。

Q2-2-1: クリティカルセクション（排他制御の対象領域）の定義#

日本語 (Japanese): クリティカルセクション（Critical Section）。複数のプロセスがアクセスする共有資源（変数やファイルなど）への操作が行われ、競合状態を防ぐために排他的に実行されなければならないプログラムのコード領域のこと。
英語 (English): Critical Section. A segment of code that accesses shared resources (such as shared variables or files) and must be executed mutually exclusively to prevent race conditions.
中文解析 (Chinese Analysis): 临界区（Critical Section）。指程序中访问共享资源（如共享变量、物理设备等）的代码段，为了防止竞合条件（Race Condition），该代码段在同一时刻只能允许一个进程/线程排他性地访问和执行。

Q2-2-2: 同期制御の有無における共有変数更新の競合状態とロストアップデート#

日本語 (Japanese): 同期制御を行う f1 では、各プロセスの共有変数 n に対する更新処理（読み込み、計算、書き込み）が P/V 操作によってアトミックかつ直列に実行されるため、すべての更新が正しく適用され最大の値 $n_1$ になる。一方、同期制御を行わない f2 では、複数のプロセスが同時に n を読み込んで更新を試みることにより、競合状態（Race Condition）が発生し、一部のプロセスによる更新が他方の書き込みによって上書きされ失われる（ロストアップデート）。n の値は常に正であり更新によって増加するため、一部の更新が失われると最終的な値は減少し、 $n_1 \ge n_2$ が成り立つ。
英語 (English): In f1, which uses synchronization, the updates (read-modify-write) to the shared variable n are executed atomically and serialized by P/V operations, ensuring all 20 updates are correctly applied to produce the maximum value $n_1$ . In contrast, f2 does not use synchronization, allowing concurrent processes to read and write n simultaneously. This causes race conditions where some updates are overwritten and lost (lost updates). Since $n$ is positive and strictly increases with each update, any lost updates will result in a smaller or equal final value, satisfying $n_1 \ge n_2$ .
中文解析 (Chinese Analysis): 进行同步控制的 f1 中，各进程对共享变量 n 的更新（读-改-写）操作通过 P/V 信号量实现了原子化与串行化执行，保证所有 20 次累加更新全部生效并达到最大值 $n_1$ 。而在未进行同步的 f2 中，多个进程可并发对 n 进行读写，导致竞合条件（Race Condition）并产生丢失更新（Lost Updates）现象，即某进程写回的中间结果被另一并发进程用旧值计算的结果覆盖。由于 $n$ 始终为正且每次更新都是严格单调递增的，任何丢失更新都会使最终累加值变小或保持不变，因此最终结果满足 $n_1 \ge n_2$ 。

Q5-2-3: クラフトの不等式とシャノンの情報源符号化定理#

日本語 (Japanese):
- (a) の式: $\sum_{x \in X} 2^{-l(x)} \le 1$ （クラフトの不等式）
- (b) の説明: クラフトの不等式を満たすとき、かつそのときに限り、瞬時に復号可能である（接頭符号が存在する）。
- (c) の式: $L_C(X) \ge H(X)$ （一意に復号可能な符号の平均符号語長は情報源エントロピー以上である）
英語 (English):
- Formula (a): $\sum_{x \in X} 2^{-l(x)} \le 1$ (Kraft’s Inequality)
- Description (b): A prefix (instantaneously decodable) code exists if and only if the codeword lengths satisfy Kraft’s inequality.
- Formula (c): $L_C(X) \ge H(X)$ (The average codeword length of any uniquely decodable code cannot be less than the source entropy.)
中文解析 (Chinese Analysis):
- 公式 (a)： $\sum_{x \in X} 2^{-l(x)} \le 1$ （克拉夫特不等式，Kraft’s Inequality）。
- 说明 (b)：当且仅当码字长度满足克拉夫特不等式时，才存在对应的瞬时可译码（前缀码）。
- 公式 (c)： $L_C(X) \ge H(X)$ （香农第一定理/无失真信源编码定理，指任何唯一可译码的平均码长不小于信源熵）。

2021年記述式問題#

Q2-3: 空きブロック極少时におけるビットマップ管理の探索时间増大の理由#

日本語 (Japanese): 空きブロックが極めて少なくなった状態では、ビットマップの大部分のビットが0（割当済）になる。空きブロックを探す際、ビットマップを先頭から线形に走査して値が1であるビットを見つける必要があり、ほぼ全領域を走査しなければならなくなるため、探索時間が大幅に増大する。
英語 (English): When the number of free blocks is extremely small, almost all bits in the bitmap are set to 0 (allocated). To locate a free block, the allocator must perform a linear scan starting from the beginning of the bitmap to find a bit set to 1, which requires scanning almost the entire bitmap, causing the search time to increase significantly.
中文解析 (Chinese Analysis): 空闲块极少时，位图的绝大部分位都被置为0（已占用）。由于寻找空闲块的算法需要从头开始线性扫描位图，寻找第一个值为1的空闲位，因此当空闲块极少时，几乎需要扫描整个位图，导致搜索时间显著增加。

Q5-3: イーサネットで同軸ケーブル最大長 $L_{\max}$ が規定されている理由#

日本語 (Japanese): CSMA/CD方式では、送信端が衝突を検出する前にフレーム送信を完了してしまうと、衝突を検知できない（遅い冲突）。よって、最小フレーム長 $F_{\min}$ の送信時間が信号の双程伝搬遅延時間（ $2 L_{\max} / V$ ）以上である必要があり、これを満たすために同軸ケーブル的最大長が厳しく規定されている。
英語 (English): In CSMA/CD, if a sending station completes its frame transmission before a collision signal propagates back, it fails to detect the collision (late collision). Thus, the transmission time of the minimum frame length ( $F_{\min}$ ) must be at least the round-trip propagation delay ( $2 L_{\max} / V$ ). To satisfy this condition, the maximum length of the coaxial cable ( $L_{\max}$ ) is strictly regulated.
中文解析 (Chinese Analysis): 在CSMA/CD以太网中，如果发送方在冲突发生并传回之前就完成了整帧的发送，它将无法检测到冲突（晚冲突）。为了确保在发送结束前能听到冲突，最小帧长 $F_{\min}$ 的发送时间必须大于等于信号在最大网段长度 $L_{\max}$ 下的双程传播延迟（即 $2L_{\max}/V \le F_{\min}/C$ ）。因此必须对同轴电缆的最大长度 $L_{\max}$ 进行严格约束。

Q5-4: 同軸ケーブル最大長を超えてフレーム伝送するために網橋が果たす役割#

日本語 (Japanese): 網橋（Bridge）はデータリンク層で動作し、各ポートが独立した衝突ドメインを形成して衝突信号を遮断（隔離）する。さらに、フレームを一度メモリに完全に受信・蓄積（バッファリング）した上で、別のポートに再送信（フォワーディング）するため、物理的伝搬距離による時間的制約をリセットしてネットワークを延長できる。
英語 (English): A bridge operates at the data link layer (Layer 2) and isolates collision domains at each port, preventing collision signals from passing through. Furthermore, it completely receives and stores (buffers) a frame in memory before retransmitting (forwarding) it onto another port, resetting the propagation delay constraint and allowing network extension beyond physical limits.
中文解析 (Chinese Analysis): 网桥工作在数据链路层（L2），其每个端口形成独立的冲突域，可以隔离冲突信号。另外，网桥在接收帧时会将其完整存入内存中进行缓存（Store-and-Forward），确认无误后再从另一个端口发射出去，从而重新生成信号并复位传播延迟限制，实现网络的超长扩展。

Q5-5: 再送フレームの再衝突を軽減するための指数退避メカニズム#

日本語 (Japanese): 各送信端は衝突を検出すると、送信を即時中止し jam 信号を送信する。その後、衝突回数 $k$ 回（最大10）に対して退避用のランダム倍数 $r$ を区间 $[0, 2^k - 1]$ から選択し、時隙（Slot Time）の $r$ 倍の時間待機してから再送を試みる。衝突回数が増えるにつれて待機窓が指数関数的に拡大し、送信タイミングを時間的に分散させることで再衝突を効果的に防ぐ。
英語 (English): Upon detecting a collision, each station immediately aborts transmission and sends a jam signal. Then, for the $k$ -th collision (capped at 10), it randomly selects a backoff multiplier $r$ from the interval $[0, 2^k - 1]$ and waits for $r \times (\text{slot time})$ before reattempting. As the number of collisions increases, the wait window grows exponentially, dispersing transmission timings to effectively mitigate re-collisions.
中文解析 (Chinese Analysis): 采用截断二进制指数退避算法。当终端检测到冲突时，立即停止发送并广播jam干扰信号。之后，对应第 $k$ 次冲突，从区间 $[0, 2^k - 1]$ 中随机选择一个整数 $r$ ，等待 $r$ 倍的时隙时间（slot time）后再尝试发送。随着冲突次数增加，等待窗口呈指数级扩大，使各终端的重传时间错开，从而降低再次发生冲突的概率。