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

[stevenwin (袋哥)]

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
推 tom21tom21:1.a 2.b 我猜得啊
推 dendrobium:1. a 2. c
推 lightergogo:1a. 2.bc  政大有出多選 = =
→ EntHeEnd:請問2是為什麼 ?
→ stevenwin:2是多選題喔QQ
→ EntHeEnd:2我"覺得"只有b也... postorder比較像stack
推 crazyjoe:2只有B吧XD
推 lightergogo:preorder inorder postorder DFS 都是stack的應用
→ lightergogo:這是洪兔講義寫的說= =
推 zkdzvy22:lightergogo正解  只是做輸出的位置不同而已
→ EntHeEnd:stack的應用 不代表有stack property吧...(LIFO)
推 tracy8901:如果多選的話會說Algorithms XD
→ lightergogo:他也沒說是單選XD
→ EntHeEnd:他是問性質 不是問應用吧... ?
推 bernachom:他說which of 沒加is@@?
→ EntHeEnd:真的要說的話 他用has 不是用have
推 lightergogo:有人知道雜湊搜尋的 worst case是多少嗎?
→ zkdzvy22:如果單純就輸出來看的話preorder確實沒有對啦XD
※ 編輯: stevenwin       來自: 219.85.159.52        (03/06 16:46)
→ EntHeEnd:有沒有人可以說明一下 因為還是覺得怪怪的...
推 dendrobium:雜湊搜尋的 worst case是 O(n)
→ assassin88:第一題竟然是n喔..為何不是nlogn??
→ EntHeEnd:簡單說 要traverse過n個element 就是O(n)
推 ie925155:最多就是經過全部的點阿當然會被 big-O bound 住
※ 編輯: stevenwin       來自: 219.85.159.52        (03/06 18:12)
推 sa074463:第二題完全要看教授要給什麼答案了...今天寫的時候也考慮
→ sa074463:很久
推 chencccc:答案是d.none of the above
推 chencccc:前年碩班考題 同位老師出的 題目一模一樣 是D
推 assassin88:莫非關鍵在於algorithm..@@
推 sa074463:為什麼是d呢? 可以解釋一下嗎@@?