Is the answer 2.75

2 votes

Given a binary search trees for a set of n=5 keys with the following probabilities :

$\begin{array}{|l|l|l|l|l|l|l|}\hline \textbf{i} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} \\\hline \textbf{$p_i$} & \text{-} & \text{0.15} & \text{0.10} & \text{0.05} & \text{0.10} & \text{0.20} \\\hline \textbf{$q_i$} & \text{0.05} & \text{0.10} & \text{0.05} & \text{0.05} & \text{0.05} & \text{0.10} \\\hline \end{array}$

The expected optimal cost of the search is

- 2.65
- 2.70
- 2.75
- 2.80

2 votes

Directly taken from here,

http://www.cs.ntou.edu.tw/lincc/courses/al99/pdf/Algorithm-Ch15-Dynamic%20Programming-4.pdf