97年高考資料結構題目！！(第二題) - 考試

二、有一個二元搜尋樹（Binary Search Tree） T如下：

11
╯ ╰
8 13
╯ ╰ ╯ ╰
3 10 12 15
╯
14
(一)若欲搜尋的鍵值（Key）平均分布在1到100之間，請算出該值於搜尋樹中平均要比較
幾次？？
ans..






高X:2點多次
某補習班:3點多次


┌──────────────┐
│ key │比較次數│機率 │
└──────────────┘
│1-2(失敗)│ 3 │0.02
└──────────────┘
│3 │ 3 │0.01
└──────────────┘
│4-7(失敗)│ 3 │0.04
└──────────────┘
│8 │ 2 │0.01
└──────────────┘
│9 (失敗) │ 3 │0.01
└──────────────┘
│10 │ 3 │0.01
└──────────────┘
│11 │ 1 │0.01
└──────────────┘
│12 │ 3 │0.01
└──────────────┘
│13 │ 2 │0.01
└──────────────┘
│14 │ 4 │0.01
└──────────────┘
│15 │ 3 │0.01
└──────────────┘
│16-100(失敗) 3 │0.85
└──────────────┘

請問關於key值失敗的比較次數是3次(高X),或4次(某補習班)，考試的答案兩種寫法都可
以嗎？？

感謝解答！！




--