[理工] 102台大電機丙數題

[qwer123073 (NullSpace)]

1.The memory usage for a doubly linked list is theta(n^2),where n is the number
of elements in the list.

這是錯的
我想問的是
這句是在問doubly linked list的空間複雜度嗎？

2.Given a balanced binary tree where,for any arbitrary internal node,the numbers
of nodes in its left and right sun-trees diff for at most one node.The time
complexity to find an element in this tree is O(log n),where n is the number of
elements.

這句是錯的
想問錯在哪

3.A B-tree of order 2 is a fully binary tree.
這是對的
但覺得怪怪的

4.Given an arbitrary directed graph,it takes O(2^n) time to determine whether
there exists a path between two nodes,where n is the number of nodes.
這句是錯的
是要改成O(2^(n^2))嗎
還是更快？


謝謝大家

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.233.82.115
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485877881.A.DE1.html
推 aa06697: 1.yes 2.BST才是true 3.你覺得怪在哪呢 4.個人覺得是O((n
→ aa06697: -1)!)
推 joeboy: 4是O(1)
→ qwer123073: 關於第3題，我的考量是可能不一定是滿的@@
→ qwer123073: j大，第4題是用相鄰矩陣直接看對不對？是1就有path
→ w181496: B tree外部節點都同level 所以是滿的
推 joeboy: 應該是n^3，Sorry給錯答案
推 aa06697: 忽然想到4可以用其他很多方法= = 最笨就是我上面講的每種
→ aa06697: path都跑過 其他我想最快就是跑DFS或BFS吧 樓上是怎麼在O
→ aa06697: (1) 找到的呢
推 joeboy: 看成是否有Ham-path QQ
→ qwer123073: 阿...題目應該是問每個頂點對，那複雜度應該不只O(1)
→ aa06697: 喔喔樓上改了 DFS的話 O(n^2). 3的話B tree 外部節點都同
→ aa06697: 一層 => 葉子都同一層 所以就是full BT了
→ aa06697: 沒看到要每一對lol 那就是樓上的答案了
→ qwer123073: 我明白了~謝謝大家!!該去惡補B-Tree了..讀什麼忘什麼
→ s89162504: 第四個要說對也可以吧 人家可是big O
推 yupog2003: 1應該是O(n)，每個node多花兩個空間存pointer
→ yupog2003: To S大：我寫101年的時候也遇到類似的問題，就看老師有
→ yupog2003: 沒有在玩這個心機了，這樣真不知道怎麼寫
→ ken52011219: DFS難找到吧 要也是BFS
→ yupog2003: 我覺得DFS跟BFS都可以，他們最後應該都會找到從source
→ yupog2003: 可以到達的點
→ ken52011219: 可是題目是指任兩對 DFS如何判定@@?
→ ken52011219: 哦哦哦 我懂意思了
→ ken52011219: DFS也可 我想成必須任兩點皆有邊
→ qwer123073: 對耶...BIG O= =
→ qwer123073: 不過這種題目應該寫越緊的bound越好
→ qwer123073: 只是 是非題真的很麻煩就是了