[理工] 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樹

繼續閱讀