[理工] 110电机丙资结 sdf456129 PTT批踢踢实业坊

楼主: sdf456129 (BiaH) 2021-02-02 17:04:44

有人知道
单选 AVL （x - y ）mod 5答案是多少吗
然后复选题AA树那题有小于三条水平线吗？

楼主: sdf456129 (BiaH) 2021-02-02 17:07:00

也求单选最后四题对于Dijkstra算法double link listbinomial heap 的total time

作者: JoJoEmbiid (嗯嗯嗯) 2021-02-02 17:09:00

AVL我写4（最高14最矮10）AAtree只有一条水平Dijkstra: mlogv mlogv vlogv v^2

楼主: sdf456129 (BiaH) 2021-02-02 17:11:00

咦 Fibonacci 不是 O (E + vlog v）吗

作者: JoJoEmbiid (嗯嗯嗯) 2021-02-02 17:14:00

对对，E没打到，是vlogv+E

楼主: sdf456129 (BiaH) 2021-02-02 17:14:00

mlog v 没看懂你写什么豪感恩所以 binomial 跟 binary 是 ElogvDouble link list 是 v^2 是为什么啊https://i.imgur.com/lLveZ5Z.jpg我以为像Binary可以写成O(vlogv + v^2)

作者: kopk159 (ChingYu) 2021-02-02 17:23:00

AVL 我算14-10 mod 5 = 4 暴力算到F17234 tree xy mod 5 = 0

作者: ssssandrew (工院蛇王) 2021-02-02 17:27:00

double Link List Extract min= V次*O(V) 找最小值要花时间假设有min指标也会因为要找新的最小值花时间； Decrease key: E*O(V) 假设找对应key不花时间也是E*O(1) 再怎么样都要V^2 我是这样看不保证正确

作者: JoJoEmbiid (嗯嗯嗯) 2021-02-02 17:33:00

是elogv没错，刚考完m,n e,v傻傻分不清xd

楼主: sdf456129 (BiaH) 2021-02-02 17:35:00

原来是这样感恩！

作者: hsnu7980 (老二) 2021-02-02 18:14:00

Avl那题是要插入2041之类的吗？我算max16 min11耶

楼主: sdf456129 (BiaH) 2021-02-02 18:36:00

一个node设为0

作者: hsnu7980 (老二) 2021-02-02 19:44:00

哎

楼主: sdf456129 (BiaH) 2021-02-02 22:16:00

楼上怎么惹

作者: hsnu7980 (老二) 2021-02-02 22:38:00

少看了设0了，辛苦导出来也没救了

楼主: sdf456129 (BiaH) 2021-02-02 22:55:00

如果你有写他的考古题会发现这是他们的惯例

作者: kopk159 (ChingYu) 2021-02-03 07:45:00

设0没设0 导出来相减应该一样吧两个都差1 会扣掉

作者: JoJoEmbiid (嗯嗯嗯) 2021-02-03 07:56:00

是说考卷最前面也有统一定义height跟depth

作者: hsnu7980 (老二) 2021-02-03 08:09:00

会不一样，avl max的single node有两层

作者: linnom (繁星) 2021-02-03 09:30:00

Avl那题其实很简单，因为求(xy)mod5，y算出来是五的倍数所以答案0说错，这题好像不是avl(?

楼主: sdf456129 (BiaH) 2021-02-03 10:13:00

嗯嗯你说的是234树

继续阅读