卷別

資料結構與演算法

選擇

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

(4 points) Consider a dynamic table that: (1) starts empty with capacity 1; (2) doubles its capacity when full; (3) shrinks its capacity by a factor of $1/2$ when the capacity $\ge 4$ and the number of stored elements falls below one quarter of the capacity. Assume that inserting or deleting an element costs 1, and resizing a table of size $k$ costs $\Theta(k)$ . Which statement is true when considering $n$ insertion and removal operations?

(A)
The worst-case cost of any single operation is $O(1)$ , so amortized analysis is unnecessary.
(B)
Using aggregate analysis, the amortized cost per operation is $\Theta(\log n)$ .
(C)
If shrinking were performed when the table becomes half full instead of one quarter full, the amortized cost would still remain $O(1)$ .
(D)
With the one-quarter shrinking rule, the amortized cost per operation is $O(1)$ , but shrinking more aggressively to half capacity when the table is half-full can destroy this bound.
(E)
The amortized cost depends on the order of operations and cannot be bounded independently of the operation sequence.

標準解析

AI 已複查