[理工] 102台大電機丙數題
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
推
01/31 23:57, , 1F
01/31 23:57, 1F
→
01/31 23:57, , 2F
01/31 23:57, 2F
推
01/31 23:58, , 3F
01/31 23:58, 3F
→
02/01 00:00, , 4F
02/01 00:00, 4F
→
02/01 00:01, , 5F
02/01 00:01, 5F
→
02/01 00:01, , 6F
02/01 00:01, 6F
推
02/01 00:02, , 7F
02/01 00:02, 7F
推
02/01 00:03, , 8F
02/01 00:03, 8F
→
02/01 00:03, , 9F
02/01 00:03, 9F
→
02/01 00:03, , 10F
02/01 00:03, 10F
推
02/01 00:04, , 11F
02/01 00:04, 11F
→
02/01 00:04, , 12F
02/01 00:04, 12F
→
02/01 00:05, , 13F
02/01 00:05, 13F
→
02/01 00:05, , 14F
02/01 00:05, 14F
→
02/01 00:06, , 15F
02/01 00:06, 15F
→
02/01 00:08, , 16F
02/01 00:08, 16F
→
02/01 01:40, , 17F
02/01 01:40, 17F
推
02/01 07:40, , 18F
02/01 07:40, 18F
→
02/01 07:43, , 19F
02/01 07:43, 19F
→
02/01 07:43, , 20F
02/01 07:43, 20F
→
02/01 07:52, , 21F
02/01 07:52, 21F
→
02/01 07:56, , 22F
02/01 07:56, 22F
→
02/01 07:56, , 23F
02/01 07:56, 23F
→
02/01 08:05, , 24F
02/01 08:05, 24F
→
02/01 08:06, , 25F
02/01 08:06, 25F
→
02/01 08:07, , 26F
02/01 08:07, 26F
→
02/01 10:18, , 27F
02/01 10:18, 27F
→
02/01 10:19, , 28F
02/01 10:19, 28F
→
02/01 10:19, , 29F
02/01 10:19, 29F