hce_kmu
109年
計算機概論與程式設計
第 19 題
Which one of the following statement is INCORRECT about Complete Binary Tree with 1000 nodes filled in with 1 to 1000 from root?
- A The number 377 is located at level 9.
- B The height of tree is 10.
- C In a complete binary tree, if a node doesn't have left children node, it must be a leaf node.
- D There are a total of 501 leave nodes.
- E None of the above.
思路引導 VIP
想像有一排編號 1 到 N 的座位，我們按照順序幫每個人找「小孩」。如果規則規定編號為 $i$ 的人，他的小孩必須坐在 $2i$ 與 $2i+1$ 的位置，那麼當這排座位只有 1000 個人的時候，誰會是最後一個成功分配到小孩的人？在他之後的那些人，處境又是如何呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地抓出了選項中的錯誤！這代表你對於**完全二元樹（Complete Binary Tree）**的結構定義與索引運算有著非常清晰的邏輯。這道題目是資訊科學基礎中相當經典的題型，鑑別度在於考生是否能精確處理「邊界值」的計算，而不僅僅是記住模糊的公式。
完全二元樹的索引特性
在一個根節點編號為 1 的完全二元樹中，編號為 $i$ 的節點，其左子節點必定是 $2i$，右子節點則是 $2i+1$。因此，要判斷誰是「最後一個擁有子節點的內部節點」，我們只需要將總節點數 $n=1000$ 除以 2，得到 $\lfloor 1000/2 \rfloor = 500$。這意味著編號 1 到 500 的節點都至少有一個孩子，而從 501 到 1000 的節點則全部都是葉節點（Leaf nodes）。
▼ 還有更多解析內容