推 WashFreeID:external可以當leaf也可以null, 看題目怎說吧 02/21 19:31
→ WashFreeID:這題就說是leaf了 02/21 19:31
→ a5120265:恩恩了解!所以所有BT外部點=內部點+1這種敘述要算False? 02/21 20:26
推 WashFreeID:同標題前面有一位大大有畫反例了 02/21 20:57
想請問100年第九題的B選項
文中所謂leaf node可以算external node嗎?
就我所知在extend or 紅黑樹下是把NULL視為external的
這時候原本的leaf就會被視為internal node吧(因為原本的leaf有child了)
而如果今天都不加external node(例如最原始的BST)
internal node定義的有child的node,leaf node就會不是internal node
那麼我們可以說leaf node = external node嗎?
會問這問題是因為
看到板上說這題B不能選是因為三元樹
1
| | |
2 3 4
|
5
這樣也是有2個internal node 3個leaf node
但題目有提及(ie. external node) 所以我會認為要把NULL視為external node
原本的leaf node 視為internal node
但這樣的話B就要選了吧??
我翻了原文書 並沒有特別針對這種狀況把leaf node定義為external node
想請問看到題目說external node時 是否就意味要把NULL視為external node?
謝謝指點
※ 引述《skybee (斯蓋比)》之銘言：
: 想問100 第8題的D選項
: double linked list 的話做一次O(n)
: 那做O(log n)回 不就是O(nlog n)
: 為什麼這選項不能選?
: ※ 引述《BuliBuchi (不離不棄)》之銘言：
: : http://tinyurl.com/cpkzwuq 101
: : http://tinyurl.com/cd77xza 100
: : 想跟大家對個答案
: : 不過寫起來蠻不順的
: : 所以有錯請大大指教
: : 101
: : 單選
: : 1~5.AECBD
: : 多選
: : 6.AD
: : 7.CDE
: : 8.AB
: : 9.ADE
: : 10.CDE
: : 11.AB
: : 100
: : 單選
: : 1~5.EACBD 6看不懂題目..
: : 多選
: : 7.CDE
: : 8.BC
: : 9.E
: : 10.CDE
: : 11.ABCD
: : 12.AE
: : 13.E
: : 14.ABCD
: : 15.ABE
: : 16.B
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.45.8
※ 編輯: a5120265 來自: 118.160.45.8 (02/21 18:38)