[課業]97年高考資料結構題目！！(第二題)

看板Examination (國家考試)作者ymca123 (快樂交朋友)時間12年前 (2013/09/24 22:12)推噓1(1推 0噓 3→)

留言4則, 2人參與討論串1/1

二、有一個二元搜尋樹（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次(某補習班)，考試的答案兩種寫法都可以嗎？？感謝解答！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.165.41.116