作者ko330 (ko330)
看板Grad-ProbAsk
标题[理工] 107台大电机丙 资结对答案
时间Tue Jan 29 16:50:48 2019
如题 有写这份的希望可以一起检讨
1~5 AABAB
6~10 ABBBA
11~15 BBBAA
16 ABCDE
17 BCD 我知道侦测cycle可以O(n) 但O(V+E)应该是可以选？
18 E
19 D
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.116.51.188
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548751851.A.8FB.html
※ 编辑: ko330 (223.136.50.221), 01/29/2019 16:54:33
※ 编辑: ko330 (223.136.50.221), 01/29/2019 17:25:53
1F：推 magic83v: 7.8我选AA 有t(node) 找中间相当於二分搜寻的速度01/29 17:35
2F：→ magic83v: 旋转可能会影响到整棵树s.t 花O(n)调整应该合理01/29 17:36
3F：→ magic83v: 想问1. 至少修改4个link 是哪4个01/29 17:40
4F：→ magic83v: 17c也看不太懂意思 qq01/29 17:58
7我是想说他没有说balance 所以worst case斜斜一条找中位数要O(n)
8是说整棵树的s跟t都可能要改吗，那可能是O(n)没错..
第1我记错了 是插入才要改4个
17c是考union find吧 一个component当成一个集合
※ 编辑: ko330 (223.136.50.221), 01/29/2019 18:51:47
5F：→ magic83v: 哦对 7A忘记skew的情况01/29 19:08
6F：推 anonimo: 第7题 他说can be found 所以我觉得应该选最小O(logn)01/29 20:21
7F：→ anonimo: 第8题应该不用整颗树改 只要改做ratation的部分就好01/29 20:23
8F：→ anonimo: *rotation01/29 20:24
第7我是觉得他想考的不是这个耶0.0
第8 rotation可能不只动三个点耶，下面subtree也全部会动到，你写看看106的11题也是
这样
※ 编辑: ko330 (114.137.158.87), 01/29/2019 21:55:19
9F：→ anonimo: 不太懂你的意思 只要把rotation node间的data换过去不就 01/29 23:19
10F：→ anonimo: 好了吗 106那题不也是动abc 3点之间吗？ 01/29 23:19
11F：→ anonimo: 这题其实就是是CLRS第14章 可以去看看课本 01/29 23:20
感谢 刚刚去翻了一下课本有写到纪录size可以用来查是第几个小的，插入一样O(logn)
题目的s(node)原本以为旋过去之後要调底下每一点的height
但好像根本不用记录在node上 我傻了，搜寻过程中每经过一点就+1就好
※ 编辑: ko330 (114.137.158.87), 01/30/2019 00:39:04
12F：推 silenteve: 请问第19题怎麽算呢 01/30 15:18
13F：推 ekids1234: 16应该没有E 因为splay 可skew 供之後人参考 02/16 21:52