※ 引述《forris (喬巴)》之銘言： : 1. 下列排序法中，何者有最佳時間複雜度 (Time Complexity)？ : (A) Quick Sort 快速排序法 : (B) Heap Sort 堆積排序法 : (C) Bubble Sort 氣泡排序法 : (D) Insertion Sort 插入排序法 : <93 身障五等> : ans:B : 我記得 Quick Sort 所花的時間是最少的 (nlog n)， : 2 這題出的不好 quick sort跟heap sort的average case都是O(nlogn) 但quick sort的worst case為O(n^2) 是高等排序法的特例 : 2. 在一個有 1023 筆資料的二元搜尋樹 (Binary Search Tree) 上找資料， : 最倒楣時大約要幾步？ : (A) 10 (B) 32 (C) 500 (D) 1000 : <92 高考三級> : ans:D : 我記得 log 1023 ~~ 10 ，為什麼會到 1000 ？ : 2 這題答案是(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 ？沒有由小到大排阿？ 請先查清楚二元搜尋樹的定義..."左小右大"...7不可能是root 答案是B沒錯 這題考的是tree sort的觀念 : 7. 假設 A = 3，B = 4，C = 5，則 prefix 算式 + A - / B - CA * BA 的值為： : (A) 7 (B) 9 (C) 11 (D) 13 : ans:A 要怎麼把 prefix 換成 Inorder ？ 我卡在 -/ 要怎麼還原? 你題目有打錯嗎~怪怪的 我算出來是 A+B/(C-A)-(B*A) : 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 先放到一邊) 你的想法怪怪的...答案是C沒錯 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.134.224.41