AVLTree Mock Test-1


Question 1
An AVL tree T contains n integers, all distinct. For a given integer k, what is time comlexity of an algorithm to find the element x in T such that |k-x| is minimized?
A
\Theta ( n)
B
\Theta (\log n)
C
\Theta (n \log n)
D
\Theta (n^2)
   Data Structure
Question 1 Explanation: 
INSERT k, then find the PREDECESSOR and SUCCESSOR of k. Return the one whose difference with k is smaller. All three methods take \Theta (\log n) time.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 2
Given a binary search tree containing N integers, time complexity of creating an AVL tree containing the same values without destroying the original BST in the process is
A
O(N)
B
O(log N)
C
O(N log N)
D
O(N log log N)
   Data Structure
Question 2 Explanation: 
Traverse the BST (in any order) as you visit a node, insert that value into the AVL Tree. Each AVL Tree insert takes O(log N). You have to perform such N insert. So, total time is O(N log N).
Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE


Question 3
We have n distinct values stored in a height balanced (AVL) binary search tree. Which of the following statements is always true?
A
The value at each node is the median of the values in the subtree rooted at that node.
B
The shortest path between any pair of nodes is at most O(log n).
C
For any node, the difference between the size of the left subtree and the right subtree is at most 3.
D
The number of leaf nodes is greater than or equal to the number of internal nodes.
   Data Structure
Question 3 Explanation: 
A height balanced tree has overall height at most O(log n), so the shortest path between any pair of nodes is always at most O(log n).
The following AVL tree is a counterexample for all other statements.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 4
The number of ways in which the numbers {1,2,3,4,5,6,7} can be inserted in an empty AVL tree, so that we don't have to perform any rotations on it and value of root node as 4, is _____.
A
64
B
24
C
48
D
128
   Data Structure
Question 4 Explanation: 
One possible is insert in the order {4, 2, 6, 1, 3, 5, 7} to make an AVL tree.
The ordering of {2, 6} and the ordering of {1, 3, 5, 7} do not matter. One can see the resulting tree is perfectly balance AVL tree.
Therefore, Total possible sequence of elements = 2!*4!=2*24=48
Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 5
What is the running time of an efficient method to merge two balanced binary search trees with n elements each into a balanced BST.
A
O(n log n)
B
O(n)
C
O(log n)
D
O(n log log n)
   Data Structure
Question 5 Explanation: 
We can start by doing an in-order walk of both trees concurrently. At each step, we compare the two tree elements and add the smaller one into a list, L, before calling that element's successor. When we finish walking both trees, L will contain a sorted list of elements from both trees. This takes O(n + n) = O(n) total time.
Now, from the sorted list, we want to create a balanced binary tree. We can do this by setting the root as the middle element of the list, and letting the first half of the list be its left subtree and the second half be its right subtree (recursively creating the balanced subtrees as well). This also takes O(n + n) = O(n) time.
The total time for this algorithm is therefore O(n)
Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE


There are 5 questions to complete.

Suggested Mock Test For You.

ALL FREE Mock Test of GATE CSE

GATE CSE Previous Years Questions on AVL Tree

GATE CSE Previous Years Questions on Data Structure

Leave a Comment