卷別

資料結構與演算法

選擇

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

(4 points) Consider the linked-list representation of disjoint sets, where: (1) each set is represented by a linked list; (2) each element stores a pointer to the set's representative; (3) $\textsc{Union}(x, y)$ appends the shorter list to the longer list (union by weight/size); (4) $\textsc{Find-Set}(x)$ runs in $O(1)$ since the representative pointer. Which of the following statements is correct?

(A)
The total time for all $\textsc{Union}$ operations is $\Theta(n^2)$ , regardless of how unions are ordered.
(B)
The total running time of all operations is $O(m \log n)$ , because $\textsc{Find-Set}$ dominates.
(C)
Using union by size makes $\textsc{Union}$ amortized $O(1)$ , yielding total time $O(m)$ .
(D)
The total time of all $m$ operations is $O(m + n \log n)$ , because each operation touches at most a constant number of elements.
(E)
Each element's representative pointer can be updated at most $\log n$ times, so all $\textsc{Union}$ operations take $O(n \log n)$ time.

標準解析

AI 已複查