[理工] [資結]-政大99-資科所

看板Grad-ProbAsk作者 (袋哥)時間14年前 (2010/03/06 16:10), 編輯推噓16(16推 0噓 13→)
留言29則, 13人參與, 最新討論串1/2 (看更多)
1. What is the complexity of inorder traversal of binary tree ? a. O(n) b. O(n^2) c. O(logn) d. O(nlogn) 2. Which of the algorithm has stack property(LIFO)? a. Breath first search b. depth first search c. preorder of tree traversal d. none of the above 題目可能有點出入，不過想問一下這兩題的答案? 感謝!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.85.159.52
推
03/06 16:12, , 1F
1.a 2.b 我猜得啊
03/06 16:12, 1F
推
03/06 16:13, , 2F
1. a 2. c
03/06 16:13, 2F
推
03/06 16:19, , 3F
1a. 2.bc 政大有出多選 = =
03/06 16:19, 3F
→
03/06 16:21, , 4F
請問2是為什麼 ?
03/06 16:21, 4F
→
03/06 16:23, , 5F
2是多選題喔QQ
03/06 16:23, 5F
→
03/06 16:25, , 6F
2我"覺得"只有b也... postorder比較像stack
03/06 16:25, 6F
推
03/06 16:27, , 7F
2只有B吧XD
03/06 16:27, 7F
推
03/06 16:28, , 8F
preorder inorder postorder DFS 都是stack的應用
03/06 16:28, 8F
→
03/06 16:29, , 9F
這是洪兔講義寫的說= =
03/06 16:29, 9F
推
03/06 16:29, , 10F
lightergogo正解 只是做輸出的位置不同而已
03/06 16:29, 10F
→
03/06 16:29, , 11F
stack的應用 不代表有stack property吧...(LIFO)
03/06 16:29, 11F
推
03/06 16:30, , 12F
如果多選的話會說Algorithms XD
03/06 16:30, 12F
→
03/06 16:31, , 13F
他也沒說是單選XD
03/06 16:31, 13F
→
03/06 16:31, , 14F
他是問性質 不是問應用吧... ?
03/06 16:31, 14F
推
03/06 16:32, , 15F
他說which of 沒加is@@?
03/06 16:32, 15F
→
03/06 16:33, , 16F
真的要說的話 他用has 不是用have
03/06 16:33, 16F
推
03/06 16:36, , 17F
有人知道雜湊搜尋的 worst case是多少嗎?
03/06 16:36, 17F
→
03/06 16:37, , 18F
如果單純就輸出來看的話preorder確實沒有對啦XD
03/06 16:37, 18F
※ 編輯: stevenwin 來自: 219.85.159.52 (03/06 16:46)
→
03/06 16:44, , 19F
有沒有人可以說明一下 因為還是覺得怪怪的...
03/06 16:44, 19F
推
03/06 16:48, , 20F
雜湊搜尋的 worst case是 O(n)
03/06 16:48, 20F
→
03/06 17:10, , 21F
第一題竟然是n喔..為何不是nlogn??
03/06 17:10, 21F
→
03/06 17:19, , 22F
簡單說 要traverse過n個element 就是O(n)
03/06 17:19, 22F
推
03/06 17:52, , 23F
最多就是經過全部的點阿當然會被 big-O bound 住
03/06 17:52, 23F
※ 編輯: stevenwin 來自: 219.85.159.52 (03/06 18:12)
推
03/06 18:35, , 24F
第二題完全要看教授要給什麼答案了...今天寫的時候也考慮
03/06 18:35, 24F
→
03/06 18:35, , 25F
很久
03/06 18:35, 25F
推
03/06 18:42, , 26F
答案是d.none of the above
03/06 18:42, 26F
推
03/06 19:00, , 27F
前年碩班考題 同位老師出的 題目一模一樣 是D
03/06 19:00, 27F
推
03/06 19:02, , 28F
莫非關鍵在於algorithm..@@
03/06 19:02, 28F
推
03/06 19:04, , 29F
為什麼是d呢? 可以解釋一下嗎@@?
03/06 19:04, 29F
‣ 更多 stevenwin 的文章
文章代碼(AID): #1BaWtnGS (Grad-ProbAsk)
‣ 更多 stevenwin 的文章
文章代碼(AID): #1BaWtnGS (Grad-ProbAsk)