[考題] 88年國安資料結構

看板Examination作者 (MJIB)時間12年前 (2013/04/27 14:56), 編輯推噓4(4推 0噓 4→)
留言8則, 3人參與, 最新討論串1/1
高度為h且度數為d之樹，至多可包含多少節點? 至多可包含多少個空指標? A:(王致強老師/資料結構) (1) 1+d+...+d(h-1次方)=d(h次方)-1除以d-1 想法：這邊沒問題，用等比級數 (2) 當節點最多時，空指標數也多=d(h次方) 想法：不太清楚這邊的空指標是指? 如果是終端節點，那應該是d(h-1次方)，也不是d(h次方) 謝謝回覆了 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.167.51.72
推
04/27 15:24, , 1F
終端節點的高度+1 你可以先用簡單的d=3的full tree 代入看看
04/27 15:24, 1F
→
04/27 15:25, , 2F
通常也是看你高度是多少開始算 不過看你(1)應該是從0開始
04/27 15:25, 2F
→
04/27 15:34, , 3F
對了 這題從0開始 所以我帶入3階二元樹 樹葉是4
04/27 15:34, 3F
→
04/27 15:34, , 4F
所以d的h次方 就是2的2次方 就沒錯 謝謝
04/27 15:34, 4F
推
04/27 18:11, , 5F
這裡的空指標是指終端節點的分支 因為它們沒有再指向其他節點
04/27 18:11, 5F
推
04/27 22:10, , 6F
怎麼我看w大你的敘述高度是從1開始阿...
04/27 22:10, 6F
→
04/27 22:10, , 7F
是我搞錯了嗎?請多多指點~
04/27 22:10, 7F
推
04/27 23:00, , 8F
是1沒錯 這題簡單來說就是d^(h-1)(節點數) * d(分支)
04/27 23:00, 8F
‣ 更多 whiteshirts 的文章
文章代碼(AID): #1HUtQXRu (Examination)