[理工] 兩個資結小問題

看板Grad-ProbAsk作者 (O_O)時間9年前 (2017/01/24 09:21), 9年前編輯推噓0(0推 0噓 17→)
留言17則, 3人參與, 最新討論串1/1
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
→
01/24 09:27, , 1F
1.complete graph在adjacency list中不僅要存|V|^2的
01/24 09:27, 1F
→
01/24 09:27, , 2F
node，還有pointer也會佔空間
01/24 09:27, 2F
→
01/24 09:29, , 3F
2.這又要看depth是從0開始還是1開始了@@如果從1開始的
01/24 09:29, 3F
→
01/24 09:29, , 4F
話，full binary tree可以造出最多internal node，
01/24 09:29, 4F
→
01/24 09:30, , 5F
1+2+2^2+2^3+...+2^(k-1)=2^k - 1
01/24 09:30, 5F
→
01/24 09:32, , 6F
阿說錯，從0開始的話才是2^k - 1
01/24 09:32, 6F
→
01/24 09:35, , 7F
https://goo.gl/UXfGqF 關於 level high depth
01/24 09:35, 7F
→
01/24 09:36, , 8F
我考試除非有講 不然應該會以這個網站所說的為主
01/24 09:36, 8F
→
01/24 09:37, , 9F
講的感覺蠻有道理的(?
01/24 09:37, 9F
→
01/24 09:40, , 10F
目前做到交大大概都會講，其他學校不一定，我覺得這個
01/24 09:40, 10F
→
01/24 09:41, , 11F
網站好清楚
01/24 09:41, 11F
→
01/24 09:42, , 12F
台大一律不講
01/24 09:42, 12F
→
01/24 09:42, , 13F
裡面提到的Depth有點像是path的概念？
01/24 09:42, 13F
→
01/24 09:43, , 14F
台大記得有一年 是考 level 和 depth 還是 height 的
01/24 09:43, 14F
→
01/24 09:43, , 15F
差別
01/24 09:43, 15F
→
01/24 09:44, , 16F
就長度來說有點像，然後depth的終點是root這樣
01/24 09:44, 16F
→
01/24 09:47, , 17F
以連結說的 第二題是 2^(K+1-1) -1 (?
01/24 09:47, 17F
是的，如果以連結來看，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
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1OXgmQPs (Grad-ProbAsk)