[理工] 兩個資結小問題

[ssssIssss (O_O)]

1.In representing graphs, the adjacency matrix always uses more storage than

the adjacency lists do

2.The maximum number of internal modes in a binary tree of depth k is 2^k - 1


是一些基本題，不過有點小疑惑，講義上給的答案1.False 2.True

但1.照理說矩陣都會用比較多吧？ 還是這裡是在指complete graph就會相等？

  2.internal node不是不包含葉子嗎，這麼一來應該是2^(k-1) - 1 ...?


以上，寫完卡卡的很想發問QQ，祝大家考上心目中的理想學校！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485220890.A.676.html
→ yupog2003: 1.complete graph在adjacency list中不僅要存|V|^2的
→ yupog2003: node，還有pointer也會佔空間
→ yupog2003: 2.這又要看depth是從0開始還是1開始了@@如果從1開始的
→ yupog2003: 話，full binary tree可以造出最多internal node，
→ yupog2003: 1+2+2^2+2^3+...+2^(k-1)=2^k - 1
→ yupog2003: 阿說錯，從0開始的話才是2^k - 1
→ ken52011219: https://goo.gl/UXfGqF 關於 level high depth
→ ken52011219: 我考試除非有講 不然應該會以這個網站所說的為主
→ ken52011219: 講的感覺蠻有道理的(?
→ yupog2003: 目前做到交大大概都會講，其他學校不一定，我覺得這個
→ yupog2003: 網站好清楚
→ joeboy: 台大一律不講
→ joeboy: 裡面提到的Depth有點像是path的概念？
→ ken52011219: 台大記得有一年 是考 level 和 depth 還是 height 的
→ ken52011219: 差別
→ yupog2003: 就長度來說有點像，然後depth的終點是root這樣
→ ken52011219: 以連結說的 第二題是 2^(K+1-1) -1 (?
是的，如果以連結來看，depth為k則樹的最多node量為2^(k+1)-1，而這題要問internal-

node量，所以是2^(k+1-1)-1

另外我又有個小問題，要怎麼分辨leaf？？依據連結中，leaf是沒有key的，那我們在畫

binary tree之類的樹時，也把沒有兒子的node稱作leaf....?
※ 編輯: ssssIssss (114.27.185.222), 01/26/2017 14:08:34