卷別

資料結構與演算法

選擇

國立臺灣大學 2024 · 考試 · 第 1 題

(5 points) Consider the following variation of the Selection Problem: Given a sequence $S = \langle a_1, a_2, \dots, a_n \rangle$ of $n$ distinct integers and two positive integers $x$ and $y$ , where each number in $S$ falls between 1 and $y$ , the goal is to report the smallest $x$ numbers in $S$ in ascending order. This scenario assumes the conventional single-processor, random access machine (RAM) model, with a machine word size of at least $\lceil \log y \rceil$ bits. To tackle this problem, five algorithms have been proposed. Please select the correct description(s) below.

(A)
Algorithm A: The algorithm initializes an empty max-heap and sequentially inserts numbers from $S$ . During insertion, if the size of the max-heap exceeds $x$ , it removes the maximum element from the heap. Finally, the remaining numbers in the heap are sorted by heapsort and reported. If $x \le n/\log n$ , Algorithm A runs in $O(n)$ time in the worst case.
(B)
Algorithm B: The algorithm initially constructs a min-heap and proceeds to extract the minimum element $x$ times. If $x \le n/\log n$ , Algorithm B runs in $O(n)$ time in the worst case.
(C)
Algorithm C: The algorithm begins by performing a base- $n$ radix sort, followed by reporting the smallest $x$ values. If $y \le n^2$ , Algorithm C runs in $O(n)$ time in the worst case.
(D)
Algorithm D: The algorithm performs a counting sort by allocating an array $C$ of length $y$ , traversing through $S$ and incrementing $C[a_i]$ for each $a_i$ . It finally reports the smallest $x$ values by scanning through the counter array. If $y \le n^2$ , Algorithm D runs in $O(n)$ time in the worst case.
(E)
Algorithm E: The algorithm first applies quickselect, i.e., Randomized-Select, to determine the $x$ -th smallest number in $S$ . Subsequently, it traverses $S$ for extracting all numbers smaller than or equal to the $x$ -th smallest number. Finally, these $x$ numbers are sorted by quicksort and reported. The time complexity of Algorithm E is $O(n + x \log x)$ in expectation.

標準解析

AI 已複查