---
# System prepended metadata

title: 台大電信丙

---

# 台大電信丙
## 108
![](https://i.imgur.com/INcj7b8.png)
> False
> Dijkstra不行用在有negative weight edge的圖，就算圖是DAG也不行，因為在Dijkstra中，不會對已經被extract min掉的vertex再次進行relax，這也就是Dijkstra的正確性需要edge都是正的的原因。

![](https://i.imgur.com/HQKjiaR.png)
> F
> ![](https://i.imgur.com/PAygAQA.png)
![](https://i.imgur.com/f4iRo4b.png)
![](https://i.imgur.com/Ea6ynUC.png)


![](https://i.imgur.com/eCI7DfK.png)
> FT
> https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard
![](https://i.imgur.com/Rs1lmw7.png)
![](https://i.imgur.com/6ag1hCM.png)
![](https://i.imgur.com/aOyN701.png)


![](https://i.imgur.com/ApEUwpS.png)
> C
> 印度神法 https://www.youtube.com/watch?v=OynWkEj0S-s&t=784s
![](https://i.imgur.com/1PKUMQa.png)


![](https://i.imgur.com/DMwvyCL.png)
> A 
> Binomial heap insert amortized $\theta(1)$
> ![](https://i.imgur.com/NjzEcaA.png)
> ![](https://i.imgur.com/AeRwzoT.png)


![](https://i.imgur.com/bnIzjtm.png)
> A
> $2019 = 1024 + 512 + 256 + 128 + 64 + 32 + 2 + 1$
> $2019 = 2^{10} + 2^{9} + 2^{8} + 2^{7} + 2^{6} + 2^{5} + 2^{1} + 2^{0}$
> degree k的binomial **tree** root下 child的degree為 k-1, k-2, ..., 0
> degree 5的binomial **tree** root下有 1個 node degree = 5
> degree 6的binomial **tree** root下有 1個 node degree = 5
> degree 7的binomial **tree** root下有 degree 6, 5 的child，總共有1 + 1 = 2個node degree = 5
> degree 8的binomial **tree** root下有 degree 7, 6, 5 的child，總共有1 + 1 + 2 = 4個node degree = 5
> 以此類推，degree 10的binomial **heap**會有 1 + 1 + 2 + 4 + 8 + 16 = 32個node degree = 5

---
![](https://i.imgur.com/oj3QZ0i.png)
> D
> $F_0 = 0, F_1 = 1, F_2 = 2, ..., F_{13} = 233, F_{14} = 377$
> $F_{13} = 233 < 256 <  F_{14} = 377$ 所以 degree即是13 - 2 = 11

![](https://i.imgur.com/Qh63gl0.png)
> C
> $F_{6+2} = F_8 = 21$

* 這兩題在問的是同一件事情，就是給定一個degree = k的Fibonacci heap，求其最少node數？
* 以下為推導過程

> ![](https://i.imgur.com/tgAyYCC.png)
> ![](https://i.imgur.com/hlUSAs9.png)
![](https://i.imgur.com/zvRLq0u.png)
![](https://i.imgur.com/YShT3bu.png)
![](https://i.imgur.com/ltlhfCR.png)
![](https://i.imgur.com/vojS1BC.png)
![](https://i.imgur.com/an03BEd.png)


![](https://i.imgur.com/oyXwJOa.png)
> A
> Fibonacci one decrease key amortized $\theta(1)$

![](https://i.imgur.com/5zlj64C.png)
> D
>  Fibonacci one decrease key worst case $O(n)$

![](https://i.imgur.com/Z9kFFSH.png)
> C
> degree 6 node 的child degree 為 0, 0, 1, 2, 3, 4, 5，至多失去一個child，所以child degree 為 0, 0, 1, 2, 3, 4。

![](https://i.imgur.com/nFdlPpl.png)
> B
![](https://i.imgur.com/5AyOzKZ.png)

![](https://i.imgur.com/CvlVVeb.png)
> C
> with weighted union and path compression, one find operation worst case?
> cost of find operation is bounded by height, with weighted union it is $O(logn)$
![](https://i.imgur.com/oPZjKpt.png)



## 109
![](https://i.imgur.com/24b7PNu.png)
> A
> 計算？
> Binomial insert amortized $\theta(1)$

![](https://i.imgur.com/eVdqCSK.png)
> A
> ![](https://i.imgur.com/AeRwzoT.png)
> Binomial insert amortized $\theta(1)$



![](https://i.imgur.com/p6xaKO0.png)
> C

![](https://i.imgur.com/ITFh3Rr.png)
> C
> ![](https://i.imgur.com/YC6gu7i.png)


![](https://i.imgur.com/2jHpgMI.png)
> B 
> height 最少的情況發生於Complete binary tree
> Complete binary tree height k 有 $2^{k+1} -1$個 node
> $2^{6+1} -1 = 63 < 100$
> $2^{7+1} -1 = 127 > 100$
> so AVL tree of 100 nodes has height **at least** 6


![](https://i.imgur.com/MC1ak4p.png)
> D
> $F_{k}$ is the $k^{th}$ fibonacci number
> AVL tree h = 0, #node = 1 = $F_2$ - 1
> AVL tree h = 1, #node = 2 = $F_3$ - 1
> AVL tree h = k, #node = 1 = $F_{k+2}$ - 1
> AVL tree h = 8, #node = 1 = $F_{8+2} - 1 = 89 - 1 = 88$
> AVL tree h = 9, #node = 1 = $F_{9+2} - 1 = 144 - 1 = 143$
> $88 < 100 < 143$
> so AVL tree of 100 nodes has height **at most** 8

![](https://i.imgur.com/zL0zEvp.png)
> A
> $4^{3+1} - 1 = 255$
> ![](https://i.imgur.com/KMgLQnK.png)

![](https://i.imgur.com/4VufJjv.png)
> E
> $2^{7+1} - 1 = 255$


![](https://i.imgur.com/6GIlBz4.png)
> D
> 2020 = 1024 + 512 + 256 + 128 + 64 + 32 + 4


![](https://i.imgur.com/H05r5lm.png)
> C
> Fibonacci delete-min amortized $O(logn)$

![](https://i.imgur.com/rhjJML0.png)
> ABCE
> ![](https://i.imgur.com/FWb5BdC.png)
> ![](https://i.imgur.com/egEtXib.png)


![](https://i.imgur.com/KUWs7pL.png)
![](https://i.imgur.com/RuFEfqB.png)
> AB

--

![](https://i.imgur.com/08k0b0D.png)
![](https://i.imgur.com/FFgryU3.png)
![](https://i.imgur.com/WxtQ1vp.png)
![](https://i.imgur.com/H0axYk7.png)
![](https://i.imgur.com/ngxfaDX.png)
![](https://i.imgur.com/1KivvyR.png)
![](https://i.imgur.com/d2kDRev.png)
![](https://i.imgur.com/JHEDrUv.png)
![](https://i.imgur.com/SmnNybr.png)
![](https://i.imgur.com/B633kMc.png)
![](https://i.imgur.com/AZn9k9B.png)
![](https://i.imgur.com/fRxn3We.png)

---
* Fibonacci heap專題
![](https://i.imgur.com/J34CVOy.png)
> Find-min 若有維持min pointer --> O(1)
> Union若是用doubly linked list串起來就是O(1)
![](https://i.imgur.com/8ntFs6X.png)
> find-min O(n) if you don't maintain a min-pointer
![](https://i.imgur.com/qYJax3o.png)
![](https://i.imgur.com/C4xmNhm.png)
![](https://i.imgur.com/q5JFsnK.png)
![](https://i.imgur.com/ymPOyao.png)
![](https://i.imgur.com/QUt6wu9.png)
![](https://i.imgur.com/uki2WhJ.png)
![](https://i.imgur.com/2eKgVAM.png)
![](https://i.imgur.com/1gr4suI.png)
![](https://i.imgur.com/9JS3sBo.png)










