基礎資料結構 - 練習題¶
Q1. Stack 操作序列 - Catalan Number (108)¶
Let \(b_n\) be the number of different permutations obtainable by passing the numbers 1, 2, 3, ..., n through a stack and deleting in all possible ways.
(a) Give the recursive formula for \(b_n\). (b) Give the analytic formula for \(b_n\).
答案與解析
答案:
(a) 遞迴公式: $\(b_n = \sum_{i=0}^{n-1} b_i \cdot b_{n-1-i}\)$
其中 \(b_0 = 1\)
解釋: 假設 1 是第 (i+1) 個被 pop 出來的元素： - 在 1 之前 pop 出來的有 i 個元素（都是 2 到 n 中的某些） - 在 1 之後 pop 出來的有 n-1-i 個元素 - 兩部分各自是獨立的子問題
(b) 解析公式 (Catalan Number): $\(b_n = C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)$
前幾項：\(b_0=1, b_1=1, b_2=2, b_3=5, b_4=14\)
Q2. Infix to Postfix (108)¶
Convert the expression "(a/(c*(b+d)))/(e-a)*c" into a postfix form.
答案與解析
答案: a c b d + * / e a - / c *
解析:
使用 Shunting-yard 演算法：
原式: (a/(c*(b+d)))/(e-a)*c
逐步轉換：
1. a → 輸出 a
2. / → push
3. ( → push
4. c → 輸出 c
5. * → push
6. ( → push
7. b → 輸出 b
8. + → push
9. d → 輸出 d
10. ) → pop 直到 (，輸出 +
11. ) → pop 直到 (，輸出 *
12. / → pop /，push 新的 /
13. ... 繼續
最終結果：a c b d + * / e a - / c *
驗證：
- b d + = b+d
- c (b+d) * = c*(b+d)
- a c*(b+d) / = a/(c*(b+d))
- e a - = e-a
- (a/(c*(b+d))) (e-a) / = (a/(c*(b+d)))/(e-a)
- ... c * = ...×c ✓
Q3. Dynamic Array Resize (113)¶
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: - D.data: the underlying array - D.size: the logical data size - D.capacity: the actual array capacity
The invariant D.size ≤ D.capacity holds at any given moment. The Insert(D, x) operation appends the element x to the end of D.data. In case D.size = D.capacity, it triggers a call to Resize(D) before appending x. Two implementations of Resize(D) are provided: - ResizeA(D): increases D.capacity by a constant (e.g., 10) - ResizeB(D): doubles D.capacity
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.
- (A) DArray is not suitable for random access because its memory may be relocated.
- (B) DArray can only be allocated in the heap memory due to its dynamic memory nature.
- (C) If ResizeA(D) is considered, the amortized time complexity of Insert(D, x) is O(1).
- (D) If ResizeB(D) is considered, the amortized time complexity of Insert(D, x) is O(1).
- (E) In the Delete(D) operation, if D.size > 0, D.size is decreased by one. If, at this stage, D.size < [D.capacity/2], we create a new array d' with a size of [D.capacity/2], transfer the data to d', set up d' as the new data array for D.data, and subsequently free the old array. Then, the amortized time complexity of mixed Insert and Delete operations can be O(1), where Resize(D) can be either ResizeA(D) or ResizeB(D).
答案與解析
答案: (D)
解析:
-
(A) 錯誤: 雖然記憶體可能重新分配，但 DArray 仍支援 O(1) 隨機存取（通過 index）
-
(B) 錯誤: 不一定只能在 heap，取決於實作
-
(C) 錯誤: ResizeA 增加固定常數
- 若每次增加 10，則每 10 次 insert 就要 resize
- Resize 成本：O(n)
- n 次 insert 需要 n/10 次 resize，每次 O(n)
-
總成本：O(n²)，攤銷 O(n)，不是 O(1)
-
(D) 正確: ResizeB 倍增
- 攤銷分析：每次 insert 預付 3 個 credit
- Resize 時使用累積的 credit
-
攤銷成本：O(1)
-
(E) 錯誤: 若使用 ResizeA 且同時有 Insert 和 Delete，可能會在邊界反覆 resize，導致每次操作都是 O(n)
Q4. Queue with Stacks (107)¶
Stacks can be used to implement queues and deques. Different from queues, a deque allows elements to be added to and removed from both ends.
(1) Describe how to implement a queue using only two stacks. And then describe how to extend the way to implement a deque using the same two stacks.
(2) Use the accounting method to prove that the amortized time complexity of a sequence of n queue operations (implemented with stacks) is O(n).
答案與解析
答案:
(1) Queue 實作:
使用兩個 stack：S1 (input stack) 和 S2 (output stack)
Enqueue(x):
push x to S1
Dequeue():
if S2 is empty:
while S1 is not empty:
pop from S1 and push to S2
return pop from S2
Deque 擴展: - 前端加入/移除用 S2 - 後端加入/移除用 S1 - 需要時在兩個 stack 間轉移
(2) 攤銷分析:
使用 Accounting Method： - 每個 Enqueue 操作預付 2 個 credit - 1 個用於 push 到 S1 - 1 個存起來，供之後轉移到 S2 使用 - 每個 Dequeue 操作使用存儲的 credit - 從 S2 pop 是 O(1) - 若需要從 S1 轉移，使用之前存的 credit
證明: - 每個元素最多被 push 2 次（進 S1，轉移到 S2） - 每個元素最多被 pop 2 次 - 每次操作攤銷成本 = O(1) - n 次操作總成本 = O(n)
Q5. Linked List 操作 (110)¶
There is a linked-list with n elements, which are \(x_1, x_2, ..., x_n\). Let \(f(n)\) be the time complexity of inserting a new element \(x_{n+1}\) to the tail of the list, and \(g(n)\) be that of deleting the last element \(x_n\). If there is only one pointer pointed to the head of the list, we know to access the list is time-consuming, and functions \(f(n)\) and \(g(n)\) are denoted as \(f_1(n)\) and \(g_1(n)\) in this case. To improve it, we may also add another pointer pointed to the tail of it, so the functions \(f(n)\) and \(g(n)\) become \(f_2(n)\) and \(g_2(n)\). Which of the following option is false if n becomes large.
| (A) \(\frac{f_1(n)}{g_1(n)} = 1\) | (B) \(\frac{f_2(n)}{g_2(n)} = n\) | (C) \(\frac{f_1(n)}{f_2(n)} = n\) | (D) \(\frac{g_1(n)}{g_2(n)} = 1\) |
答案與解析
答案: (D) 是錯誤的
解析:
只有 head pointer (Singly Linked List): - \(f_1(n) = O(n)\)：需要遍歷到尾部才能插入 - \(g_1(n) = O(n)\)：需要遍歷到倒數第二個節點
有 head 和 tail pointer: - \(f_2(n) = O(1)\)：直接在 tail 後插入 - \(g_2(n) = O(n)\)：刪除最後一個需要找到倒數第二個節點（singly linked list 沒有 prev pointer）
驗證選項： - (A) \(f_1/g_1 = O(n)/O(n) = 1\) ✓ - (B) \(f_2/g_2 = O(1)/O(n) = 1/n\)，不是 n → 選項說 = n 是**錯誤的** - (C) \(f_1/f_2 = O(n)/O(1) = n\) ✓ - (D) \(g_1/g_2 = O(n)/O(n) = 1\) ✓
答案是 (B)，但如果原題選項是問 false，則 (B) 是 false。
Q6. Postfix Advantages (112)¶
Postfix advantages: What is/are the advantage(s) of using postfix notation for math expressions?
- (A) No need to use parentheses
- (B) No need to consider precedence of operators
- (C) Easier for human to read
- (D) Easier for computers to evaluate
- (E) More concise when compared with prefix notation
答案與解析
答案: (A)(B)(D)
解析:
- (A) 正確: Postfix 不需要括號，運算順序由位置決定
- (B) 正確: 不需要考慮運算子優先級，直接按順序計算
- (C) 錯誤: Postfix 對人類較難閱讀（如
3 4 + 5 *vs(3+4)*5） - (D) 正確: 用 stack 可以 O(n) 直接求值，不需要建樹或處理優先級
- (E) 錯誤: Postfix 和 Prefix 長度相同
延伸練習¶
更多基礎資料結構相關題目： - 107 Data Structure.Pdf V(a) - Deque 詳細實作 - 109 Data Structure.Pdf Q7 - Linked List Stack 實作