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
Question 6
The number of rotations required to insert a sequence of elements 9, 6, 5, 8, 7, 10 into an empty AVL tree is?
A
0
B
1
C
2
D
3
ISRO CSE 2013   Data Structure
Question 7
The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements is
A
\Theta (n log n)
B
\Theta n2^{n}
C
\Theta (n)
D
\Theta (log n)
GATE CSE 2012   Data Structure
Question 8
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
A
2
B
3
C
4
D
5
GATE CSE 2009   Data Structure
Question 9
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is
A
\Theta (n)
B
\Theta (nlog n)
C
\Theta (n^{2})
D
\Theta (n^{2}log n)
GATE CSE 2004   Data Structure
Question 10
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the let sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following ?
A
log_{2}n
B
log_{4/3}n
C
log_{3}n
D
log_{3/2}n
GATE CSE 2002   Data Structure
There are 10 questions to complete.

Leave a Comment