1. 下列排序法中，何者有最佳時間複雜度 (Time Complexity)？
(A) Quick Sort 快速排序法
(B) Heap Sort 堆積排序法
(C) Bubble Sort 氣泡排序法
(D) Insertion Sort 插入排序法
<93 身障五等>
ans:B
我記得 Quick Sort 所花的時間是最少的 (nlog n)，
2
2. 在一個有 1023 筆資料的二元搜尋樹 (Binary Search Tree) 上找資料，
最倒楣時大約要幾步？
(A) 10 (B) 32 (C) 500 (D) 1000
<92 高考三級>
ans:D
我記得 log 1023 ~~ 10 ，為什麼會到 1000 ？
2
3. 令 A[100] 是一個專門用來儲存 4 位元實數之一維陣列，若 A[1] 的位址為 256 ，
則 A[90] 的位址為何？
(A) 612 (B) 616 (C) 345 (D) 346
<92 身障五等>
ans:A 請問要怎麼算？
4. 一顆二元搜尋樹 (Binary Search Tree) ，左節點值較小，右節點值較大，
以何種方式追蹤 (Traversal) 可得到由小到大排序結果？
(A) Preorder (B) Inorder (C) Postorder (D) Levelorder
<92 地方四等>
ans:B
我認為應該是 C，如果是 Inorder，
7
╱ ╲
2 5
∕ ﹨ ∕ ﹨
1 3 4 6 不是 1237456 ？沒有由小到大排阿？
5.一顆二元樹之中序法 (Inorder) 為 ECFBDAHG，而後序法 (Postorder) 為 EFBCHGAD，
則此二元數之前序法 (Preorder) 為何？
(A) ABDGCEHF (B) ABCDEFGH (C) DECFBAHG (D) DCEBFAGH
<92 地方四等>
ans:D 我認為D有誤，此題沒有答案
6. 算式 A + B * C - A 的 Postfix 式為：
(A) ACB*-A+ (B) BC*A-A+ (C) ABC*-A+ (D) AABC*-A
ans:A 我認為此題沒有答案
7. 假設 A = 3，B = 4，C = 5，則 prefix 算式 + A - / B - CA * BA 的值為：
(A) 7 (B) 9 (C) 11 (D) 13
ans:A 要怎麼把 prefix 換成 Inorder ？ 我卡在 -/ 要怎麼還原?
8. 有一堆疊 (Stack)，一開始狀態為空，假設 Push(X) 指令會將資料 X 放入堆疊，
Pop 指令會將堆疊頂端的資料輸出。現在有 ABCDE 五個資料，依序以 Push 指令放入
堆疊中，在放入過程中與結束後，我們陸續執行了一些 Pop 指令，下列何者為
不可能的輸出？
(A) ABCDE (B) EDCBA (C) EABCD (D) ABDEC
ans:C
我在想，先依序 push A, 再 pop A, push B, pop B, push C, pop C,
push D, push C, push B, push A, push E, 是可以的.
(從 stack pop 出來的 element 先放到一邊)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.116.193.79
※ 編輯: forris 來自: 59.116.193.79 (12/11 01:29)