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.