資料結構›Ch2 陣列與字串
第 3 題/共 6 題
◀ DS 3/6
3. Dynamic Array、攤還分析
#DS-02-003中Dynamic Array攤還分析

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 DD maintains three crucial attributes, including the underlying array D.dataD.data, the logical data size D.sizeD.size, and the actual array capacity D.capacityD.capacity. The invariant D.size≤D.capacityD.size \le D.capacity holds at any given moment. The Insert(D,x)Insert(D,x) operation appends the element xx to the end of D.dataD.data. In case D.size=D.capacityD.size = D.capacity, it triggers a call to Resize(D)Resize(D) before appending xx, where Resize(D)Resize(D) allocates a new and larger array, moves all the data to it, increases the value of D.capacityD.capacity, sets up D.dataD.data, and finally frees the old array. Two implementations of Resize(D)Resize(D) are provided: ResizeA(D)ResizeA(D) increases D.capacityD.capacity by a constant (e.g., 10) while ResizeB(D)ResizeB(D) doubles D.capacityD.capacity each time.

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

📄 台大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch2 陣列與字串
本章題號 · 1–6 / 6