WorksheetsTree
Total questions: 30
Worksheet time: 15mins
在樹中，若節點 X 直接連到節點 Y，則 X 與 Y 的關係正確的是哪一項？
X 是 Y 的祖先而非父節點
X 與 Y 為兄弟節點關係
X 是 Y 的父節點而非祖先
X 是 Y 的子節點而非後代
下列敘述何者正確描述「終端節點（leaf node）」？
具有至少一個子節點的節點
沒有任何父節點的根節點
沒有子節點且分支度為零的節點
與同一父節點共享邊的節點
一棵樹的高度（height）是指哪個量？
從根到最長路徑的邊數長度
某節點到其父節點的距離
根到某節點的最短路徑長度
樹中所有邊的總數量
若節點 A 與節點 B 具有相同的父節點，則 A 與 B 的正確關係為何？
非終端節點
祖先與後代
父子關係
兄弟節點
在樹中，層級（level）與深度（depth）的主要差異為何？
層級與深度皆為邊數總和的別名
層級描述世代位置，深度描述至根之路徑長度
層級只對葉節點定義，深度只對根定義
層級是最長路徑長度，深度是最短路徑長度
圖中提到「終點節點(又稱樹葉節點)：分支度為 0 的節點」。請問終點節點的正確定義是什麼？
高度為 0 的節點
沒有父節點的節點
分支度為 0 的節點
分支度為 1 的節點
若一棵樹的最大分支度為 k，並以固定長度的 LINK 欄位儲存每個節點的子連結，下列哪一項敘述最接近其所需欄位數與浪費的概念？
需要 n·k 個欄位，浪費約為 n·k−n 個欄位
需要 n·k 個欄位，浪費約為 n·k−(n−1) 個欄位
需要 n·k 個欄位，浪費約為 n·k−(n+1) 個欄位
需要 n·k 個欄位，毫無浪費
練習題：一棵樹的分支度為 6，並且有 50 個節點。使用固定 k=6 的 LINK 欄位配置，理論上需要多少 LINK 欄位？實際上使用了幾個？浪費了多少？選出最符合的數值組合。
理論 250，實用 200，浪費 50
理論 300，實用 250，浪費 50
理論 300，實用 300，浪費 0
理論 300，實用 49，浪費 251
下列關於二元樹與一般樹的敘述，何者正確？
二元樹必須每層節點數相同
一般樹一定有左子樹與右子樹
一般樹的節點度數皆等於二
二元樹的節點度數最多為二
滿枝二元樹的高度為 k（根的階層為 1），其節點總數最接近下列哪一式？
k2−1
2(k−1)+1
k×2k
2k−1
完整二元樹與滿枝二元樹的主要差異是什麼？
完整二元樹允許最後一層未滿
完整二元樹每層皆滿枝
滿枝二元樹允許中間層缺節點
滿枝二元樹需要索引陣列儲存
若一棵二元樹共有 128 個節點，分支度為 2 的節點數 n2 最合理是下列何者？（已知 n0 = n2 + 1）
n2 = 63
n2 = 32
n2 = 127
n2 = 64
假設二元樹根的階層為 1，整棵樹的階層數為 10，則最多節點數與第 9 階層最多節點數分別為？
最多 1023；第 9 層最多 256
最多 1024；第 9 層最多 256
最多 1023；第 9 層最多 512
最多 1024；第 9 層最多 512
下列哪一個敘述正確描述「中序遍歷」的步驟？
先訪左子樹，再訪根節點，再訪右子樹
先訪左子樹，再訪右子樹，最後訪根節點
先訪右子樹，再訪根節點，再訪左子樹
先訪根節點，再訪左子樹，再訪右子樹
將一般樹轉換為二元樹時，常用的「左孩子右兄弟」表示法意義為何？
每節點右鏈接指父節點，左鏈接指兄弟
每節點左右鏈接皆指子節點隊列
每節點左鏈接指父節點，右鏈接指叔父
每節點左鏈接指子節點，右鏈接指兄弟
在二元搜尋樹中，若要輸出由小到大的鍵值序列，應採用哪一種遍歷方法？
preorder
inorder
postorder
levelorder
如下圖所示二元樹，請利用「前序遍歷」寫出節點訪問順序。
ABEDCFGHI
ABEDF GCHI
ABE DFCGHI
ABDECFGHI
如下圖所示二元樹，請利用「後序遍歷」寫出節點訪問順序。
EFGDBIHCA
EFGDBIHAC
EFGDBIHCAI
EFGDBIHABC
若已知某二元樹的前序序列為 1,2,4,5,8,3,6,9,7，且中序序列為 4,2,8,5,1,9,6,3,7，則根節點為何？
3
2
1
4
關於引線二元樹(threaded binary tree)的敘述，何者正確？
以空LINK改存序列鄰接指標
以空DATA改存父節點索引
以空LINK改存隨機指標
以空DATA改存左右高度
在引線二元樹中，LBIT=0 表示什麼？
右LINK為正常指向
左LINK為引線
左LINK為正常指向
右LINK為引線
在二元搜尋樹中，關於節點鍵值的基本性質，哪一項正確？
左右子樹鍵值可以任意大小
右子樹鍵值均小於根鍵值
左子樹鍵值均小於根鍵值
左子樹鍵值均大於根鍵值
依序插入鍵值：50、30、70、55 至空的二元搜尋樹後，關於節點 55 的位置，哪一項描述正確？
位於 30 的左子點
位於 70 的右子點
位於 50 的左子點
位於 70 的左子點
若某樹的右子樹中存在一個鍵值小於根鍵值，則該樹的性質最可能是什麼？
一定是滿二元樹
僅在部分節點違規但可稱平衡樹
不是二元搜尋樹
仍為合法的二元搜尋樹
將鍵值依序插入空樹：25、35、15、55、65、40、45、10、20、30。插入完成後，節點 35 的中序前驅是誰？
20
25
30
40
考慮插入序列：40、20、30、50、70、55、35、28、85、72。完成後，根節點的右子樹高度相較左子樹高度，最可能的情形是？
左右子樹完全相等
右子樹明顯較高
無法由序列推論
左子樹明顯較高
觀察圖中對二元搜尋樹的描述，刪除「葉節點」時正確的基本步驟是什麼？
以左子樹最大節點替換並刪除
以右子樹最小節點替換並刪除
以該節點的父節點取代它的位置
直接移除該節點並不需調整指標
當刪除一個僅有「一個子節點」的節點時，最符合 BST 規則的處理方式是哪一項？
用該節點的父節點覆寫其鍵值
將其子節點提升接到被刪節點的父節點
改以中序前驅節點取代並刪除
改以中序後繼節點取代並刪除
刪除具有「兩個子節點」的節點時，常用的替換策略是下列何者？
以右子樹的最大鍵值節點替換
以左子樹的最小鍵值節點替換
以左子樹的最大鍵值節點替換
以根節點的鍵值覆寫被刪節點
依圖示練習：若在 BST 中刪除鍵值 60，並以右子樹「最小節點」作為替代，接著需要的正確調整是？
把被替代節點的左子樹接到替代節點右側
把替代節點的右子樹接回其原父節點
把替代節點的左子樹保留原位不變
把替代節點的父節點改指向被刪節點
