AVL Tree


Question 1
The minimum height of an AVL tree with n nodes is
A
\text{Ceil } (\log_2(n+1))
B
1.44\ \log_2n
C
\text{Floor } (\log_2(n+1))
D
1.64\ \log_2n
ISRO CSE 2020   Data Structure
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.
A
\Theta (\log n )
B
\Theta (\log n +k)
C
\Theta (k \log n )
D
\Theta (n \log k )
GATE CSE 2020   Data Structure


Question 3
What is the worst case time complexity of inserting n^2 elements into an AVL-tree with n elements initially?
A
\Theta (n^4)
B
\Theta (n^2)
C
\Theta (n^2 \log n)
D
\Theta (n^3)
GATE CSE 2020   Data Structure
Question 4
Access time of the symbolic table will be logarithmic if it is implemented by
A
Linear list
B
Search tree
C
Hash table
D
Self organization list
ISRO CSE 2016   Data Structure
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 _______.
A
100
B
110
C
10
D
1010
GATE CSE 2014 SET-3   Data Structure


There are 5 questions to complete.

Leave a Comment