Re: [ 問 ] 資料結構
※ 引述《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
推
12/12 01:00, , 1F
12/12 01:00, 1F
→
12/12 01:00, , 2F
12/12 01:00, 2F
討論串 (同標題文章)