ISRO CS 2019 : DS Booster Quiz 4

Consider a binary tree with the following conditions :

* The elements present in left sub-tree of a specific node are smaller than that node and elements present in right sub-tree of a specific node are greater than that node.

* The tree is always balanced i.e. the height of left sub-tree and right sub-tree is approximately same. (maximum differ by 1)

What is the worst case time complexity to run membership test for an element on this tree ?

Suppose we want to search for an element 70 in a Binary Search tree. Which of the following probe sequences are not valid while searching a Binary Search tree?

Consider a BST with some extra features added to it in order to improve its data storing efficiency. After adding those features , the time complexity of the basic operations in BST like insertion , deletion or searching may change. Now consider the following two features added :
• BST is always made balanced
• Splaying : Bringing the recently accessed element to root
Now after adding these two features BST is modified Which of the following statements are true regarding the modified BST :
I. Worst case searching time = O(logn)
II. Worst case searching time = O(1)
III. Locality of reference is achieved
IV. Insertion/Deletion time in modified BST is more than in ordinary BST
V. Splaying has added an extra time of O(n)

Consider a linked list as :

Now consider a direct pointer P is given to node with value 'd'. We want to delete the node pointed by P . How much time it will take if the length of linked list is assumed to be n.

Match the following :

Consider the following function recursion(a, b). What is the value of recursion( 8,6)?
int recursion(int a, int b)
{
if (a == 0)
return b;
return recursion( a -1, a + b);
}