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)