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)