司法三等申論題
115年
[檢察事務官電子資訊組] 程式語言
第 三 題
📖 題組：
三、已知二元搜尋樹的節點定義如圖 3-1，請根據圖 3-2 的二元搜尋樹回答問題。 typedef struct TNode { int key; struct TNode *left; struct TNode *right; } TNode; 圖 3-1：節點定義
三、已知二元搜尋樹的節點定義如圖 3-1，請根據圖 3-2 的二元搜尋樹回答問題。 typedef struct TNode { int key; struct TNode *left; struct TNode *right; } TNode; 圖 3-1：節點定義
📝 此題為申論題，共 3 小題
小題 (三)
(三)圖 3-4 之函式可以用來在二元搜尋樹中搜尋指定值（target）。
1.請將圖 3-5 的三行指令分別填入圖 3-4 函式 A、B、C 的空格中（每個選項限填一次且不可重複填用）。（5 分）
2.根據圖 3-2 的二元搜尋樹，若執行 search(root, 7)，請問此函式最後回傳的指標所指向的節點，其 key 值為何？（5 分）
TNode *search(TNode *root, int target) {
while(root != NULL) {
if( A )
return root;
if( B )
root = root->left;
else
root = C ;
}
return NULL;
}
圖 3-4
root->right
root->key == target
target < root->key
圖 3-5
1.請將圖 3-5 的三行指令分別填入圖 3-4 函式 A、B、C 的空格中（每個選項限填一次且不可重複填用）。（5 分）
2.根據圖 3-2 的二元搜尋樹，若執行 search(root, 7)，請問此函式最後回傳的指標所指向的節點，其 key 值為何？（5 分）
TNode *search(TNode *root, int target) {
while(root != NULL) {
if( A )
return root;
if( B )
root = root->left;
else
root = C ;
}
return NULL;
}
圖 3-4
root->right
root->key == target
target < root->key
圖 3-5
思路引導 VIP
📋 事實梳理：這是標準的「二元搜尋樹（BST）」非遞迴尋找演算法。 🔍 爭點辨識：BST 的特性是什麼？左小、右大。
小題 (一)
(一)請分別說明二元樹的遞迴走訪函式中，下列兩種情況的目的與執行行為。（5 分）
基底情況（Base case）。
遞迴情況（Recursive case）。
基底情況（Base case）。
遞迴情況（Recursive case）。
思路引導 VIP
📋 事實梳理：任何遞迴函式在學理上都具備這兩大組成要件。 🔍 爭點辨識：如果沒有 Base case 會發生什麼事？Recursive case 負責做什麼事？
小題 (二)
(二)執行圖3-3 之函式，root 為圖3-2 二元搜尋樹根節點，low=5，high=10。
1.其最終回傳值為何？（5 分）
2.請依此函式實際遞迴走訪的先後順序，列出current = 1 節點key 值。
（5 分）
int countRange(TNode *root, int low, int high) {
if(root == NULL) return 0;
int current = (root->key >= low && root->key <= high) ? 1 : 0;
return current + countRange(root->left, low, high) + countRange(root->right, low, high);
}
圖 3-3
1.其最終回傳值為何？（5 分）
2.請依此函式實際遞迴走訪的先後順序，列出current = 1 節點key 值。
（5 分）
int countRange(TNode *root, int low, int high) {
if(root == NULL) return 0;
int current = (root->key >= low && root->key <= high) ? 1 : 0;
return current + countRange(root->left, low, high) + countRange(root->right, low, high);
}
圖 3-3
思路引導 VIP
📋 事實梳理：函式 countRange 目的是計算樹中有多少節點的 key 落在 low 和 high 之間。走訪方式為前序走訪（先算 current，再走 left，再走 right）。
🔍 爭點辨識：觀察圖 3-2 找出根節點（最上面的 10）。10 的左子是 5，右子是 12。5 的左子是 4，右子是 7。