卷別

資料結構與演算法

選擇

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

(4 points) Which of the following $\square$ generates a uniformly random permutation of an array $A$ of size $n$ in place, assuming that $\textsc{Random}(\ell, r)$ returns an integer chosen uniformly at random from $\{\ell, \ell+1, \dots, r-1, r\}$ ?

RANDOM-PERMUTE(A):
1   for i = 1 to n
2       □
3       if a ≤ b
4           swap A[i] with A[RANDOM(a, b)]

(A)
$a = \textsc{Random}(1, n),\ b = \textsc{Random}(a, n)$
(B)
$a = 1,\ b = i - 1$
(C)
$a = i,\ b = n$
(D)
$a = i + 1,\ b = n$
(E)
$a = 1,\ b = n$

標準解析

AI 已複查