免費開始練習
高考申論題 115年 [資訊處理] 資料結構

第 鿩 題

📖 題組：
給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵 AVL 樹。
樹的節點在 C 語言中宣告如下：
typedef struct Node {
  int key; // 節點的鍵值，所有節點的鍵值皆互不相同
  int size; // 以該節點為根的子樹節點總數 (包含自己)
  struct Node *left; // 指向左子節點
  struct Node *right; // 指向右子節點
} Node;
並定義以下函式：
`int size (Node *node)`：
若傳入的 node 為 NULL，則回傳 0；否則回傳 node -> size。
`int count_less_equal (Node *node, int val)`：
回傳以 node 為根的子樹中，所有鍵值小於等於 val 的節點總數。
`Node* select (Node *node, int r)`：
回傳以 node 為根的子樹中，第 r 小的節點指標，r 從 1 開始算。
`Node* greater_k_smallest (Node *root, int val, int k)`：
找出以 root 為根的整棵樹中，所有鍵值大於 val 的節點裡，第 k 小的節點，k 從 1 開始算。若第 k 小的節點不存在，則回傳 NULL。
完成下列程式碼的空格。（20 分）
int count_less_equal(Node *node, int val) {
  if (node == NULL) return 0;
  if (node->key > val)
    return count_less_equal(node->left, val);
  else return size(node->left)+ (1) ;
}
Node* select(Node *node, int r) {
  int left_size = size(node->left);
  if (r == (2) ) return node;
  else if (r <= left_size)
    return select(node->left, r);
  else return (3) ;
}
Node* greater_k_smallest(Node *root, int val, int k){
  int x = count_less_equal(root, val);
  int y = (4) ;
  if (y > size(root)) return NULL;
  return select(root, y);
}
📝 此題為申論題

思路引導 VIP

本題測試擴充的二元搜尋樹（Order Statistic Tree）操作。 (1) count_less_equal 中，若 current key <= val，則該節點及其左子樹所有點都 <= val。故數量應為 左子樹大小 + 1(自己) + 尋找右子樹中符合條件的數量。因此 (1) 應為 1 + count_less_equal(node->right, val)。

🤖
AI 詳解 AI 專屬家教

【考點分析】 二元搜尋樹（BST）的階序統計（Order Statistics）擴充，利用子樹大小（Size）來實作快速尋找第 K 小元素及區間計數。 【理論/法規依據】

▼ 還有更多解析內容

🏷️ 相關主題

樹狀資料結構：原理、演算法與應用
查看更多「[資訊處理] 資料結構」的主題分類考古題

📝 同份考卷的其他題目

查看 115年[資訊處理] 資料結構 全題

升級 VIP 無限刷題