Question 1 |

The minimum height of an AVL tree with n nodes is

\text{Ceil } (\log_2(n+1)) | |

1.44\ \log_2n | |

\text{Floor } (\log_2(n+1)) | |

1.64\ \log_2n |

Question 1 Explanation:

Question 2 |

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.

\Theta (\log n ) | |

\Theta (\log n +k) | |

\Theta (k \log n ) | |

\Theta (n \log k ) |

Question 2 Explanation:

Question 3 |

What is the worst case time complexity of inserting n^2 elements into an AVL-tree with n elements initially?

\Theta (n^4) | |

\Theta (n^2) | |

\Theta (n^2 \log n) | |

\Theta (n^3) |

Question 3 Explanation:

Question 4 |

Access time of the symbolic table will be logarithmic if it is implemented by

Linear list | |

Search tree | |

Hash table | |

Self organization list |

Question 4 Explanation:

Question 5 |

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^{a}log^{b}n+m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is _______.

100 | |

110 | |

10 | |

1010 |

Question 5 Explanation:

There are 5 questions to complete.