資料結構與演算法

(5 points) A Dynamic Array (abbreviated as DArray) is a type of array that permits the insertion and deletion of elements at the end to dynamically adjust its size. DArray $D$ maintains three crucial attributes, including the underlying array $D.\text{data}$, the logical data size $D.\text{size}$, and the actual array capacity $D.\text{capacity}$. The invariant $D.\text{size} \le D.\text{capacity}$ holds at any given moment. The $\text{Insert}(D, x)$ operation appends the element $x$ to the end of $D.\text{data}$. In case $D.\text{size} = D.\text{capacity}$, it triggers a call to $\text{Resize}(D)$ before appending $x$, where $\text{Resize}(D)$ allocates a new and larger array, moves all the data to it, increases the value of $D.\text{capacity}$, sets up $D.\text{data}$, and finally frees the old array. Two implementations of $\text{Resize}(D)$ are provided: $\text{ResizeA}(D)$ increases $D.\text{capacity}$ by a constant (e.g., 10) while $\text{ResizeB}(D)$ doubles $D.\text{capacity}$ each time.

To initialize DArray $D$, we set $D.\text{size}$ to 0, $D.\text{capacity}$ to 1, and allocate a size 1 array to $D.\text{data}$. Assuming that both allocating and freeing arrays of length $n$ take $O(n)$ time, and moving a single element takes $O(1)$ time, please select the correct description(s) below.