卷別

資料結構與演算法

選擇

國立臺灣大學 2026 · 考試 · 第 21 題

(4 points) Let $T$ be a B-tree of minimum degree $t \ge 2$ . During the deletion of a key $k$ from an internal node $x$ , suppose $k$ is stored in $x$ at index $i$ . Which of the following actions correctly preserves all B-tree invariants before the recursive deletion proceeds?

(A)
Always replace $k$ with its inorder predecessor from the left subtree, regardless of the number of keys in the subtree.
(B)
Replace $k$ with either the predecessor or successor arbitrarily, since both choices always produce valid B-trees.
(C)
Merge the two children of $k$ immediately, even if both have at least $t$ keys.
(D)
Delete $k$ directly from node $x$ and rebalance only if an underflow occurs afterward.
(E)
Replace $k$ with the key preceding $k$ in the left child if the left child has at least $t$ keys; otherwise replace it with the key following $k$ if the right child has at least $t$ keys.

標準解析

AI 已複查