作者lienasd126 (迷途の狮子)
看板Grad-ProbAsk
标题110 阳交大 资结
时间Fri Oct 15 16:03:00 2021
https://i.imgur.com/I2F2NEo.jpg
想请问26.D 如果是Union by rank(Height)不是O(logn)
https://i.imgur.com/q8XUmhQ.jpg
21.如果是（0，1，2）应该degree都是 3 ，怎麽有2的，有2的是不是不能选？
https://i.imgur.com/92fvbDh.jpg
20如果不计较size是不是 Linked list 比较好，如果是 direct access那应该选 array?
!
D. 如果是push_back 为什麽要花 Theta(n)
https://i.imgur.com/3K7ReEr.jpg
18 D 是不是把他看成 Selection Problem 时间也一样？
https://i.imgur.com/una7Rgd.jpg
6.B floor (n/2) ^ floor(n/2) ，那个 floor要省略对吗？
https://i.imgur.com/zDUnZJH.jpg
1. E P包含於NP，所以也可以solve in polynomial time?
请各位大神帮忙回答，感谢感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 115.43.138.74 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1634284982.A.CEA.html
※ 编辑: lienasd126 (115.43.138.74 台湾), 10/15/2021 16:03:24
1F：→ BusterButter: 先回答Huffman code那题，如果是一般的binary Huffm10/15 16:54
2F：→ BusterButter: an tree, 不管有几个character要encode都ok10/15 16:54
3F：→ BusterButter: 但是这题是ternary Huffman tree, character数目要10/15 16:56
4F：→ BusterButter: 是奇数才可以建好（想像每三个char合并成一个，char10/15 16:56
5F：→ BusterButter: 数目会扣2，最後要剩下char数目必须要剩下一个）10/15 16:56
6F：→ BusterButter: 可是这题给的char数目是偶数，这时候我们必须要inse10/15 16:57
7F：→ BusterButter: rt一个权重是0的placeholder node, 等到建好的时候10/15 16:57
8F：→ BusterButter: 才remove, 这就是为什麽有些internal node的degree10/15 16:57
9F：→ BusterButter: 不是310/15 16:57
嗯嗯，我再想想看
10F：→ BusterButter: NP那题你的理由ok（毕竟题目没讲明problem是不是不10/15 17:04
11F：→ BusterButter: 在P里，NP包含P，所以在P里的problem就是反例）10/15 17:04
12F：推 BusterButter: 20. 如果空间不够，就要分配一块新的更大的mem, 再10/15 17:08
13F：→ BusterButter: 把旧东西搬过去，所以可能要linear time10/15 17:08
那这样B的描述是正确的吧？！ 他答案没给B,还有如果依照你那麽说应该时间复杂度是Bi
g-O,不是Theta,他amortized下来是Theta(1)
谢谢Buster大
※ 编辑: lienasd126 (27.51.50.28 台湾), 10/15/2021 17:16:32
14F：→ BusterButter: 18. 这选项应该是错的吧，光是merge就是O(nlgn)的时10/15 17:14
15F：→ BusterButter: 间了 （高度lgn - lglgn，每个level O(n) ）10/15 17:14
嗯嗯，对，我是想说题目的切法很像Selection,
所以搞不好时间复杂度很像XD
※ 编辑: lienasd126 (27.51.50.28 台湾), 10/15/2021 17:18:27
16F：→ BusterButter: 20.B应该是错在才多分配一单位吧== （m变成m+1，这 10/15 17:24
17F：→ BusterButter: 样很快用不够） 10/15 17:24
18F：→ BusterButter: 我看了一下vector的source code，至少也有+5 10/15 17:24
嗯嗯，好
Huffman code 那一题是不是要看 placeholder node放的位置，如果不是放在最底层的就
是不可能，因为他是拿来凑的，是吗？？
然後D选项是三位元树不能有一个以上degree为2的点
※ 编辑: lienasd126 (27.51.50.28 台湾), 10/15/2021 17:27:39
※ 编辑: lienasd126 (27.51.50.28 台湾), 10/15/2021 17:29:15
※ 编辑: lienasd126 (115.43.138.74 台湾), 10/15/2021 17:31:33
19F：→ BusterButter: 对我的想法跟你说得差不多 所以应该BCD是不可能的 10/15 17:55
20F：推 A4P8T6X9: union 完美版需要 O(a(n)) a 为 inverse Ackermann fun 10/16 07:38
21F：→ A4P8T6X9: ction 10/16 07:38
22F：推 joywilliamjo: 请问huffman那题的答案是多少啊 10/16 23:43
BCD
※ 编辑: lienasd126 (27.53.186.34 台湾), 10/17/2021 00:43:57
23F：推 joywilliamjo: huffman那题看不懂为什麽B不行，NP那题的话，NP那 10/17 01:12
24F：→ joywilliamjo: 个选项反例就NPC(有Poly的解只是是用猜的猜出来的) 10/17 01:12
25F：推 jimmy1112111: 因为level2才少一个node，必须要在最底层才能少 10/27 00:46