※ 引述《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