40 MCQs of Advance Data Structure

1) What is the load factor for an open addressing technique?

1. 1
2. 0
3. 5
4. 5

Show Answer Workspace

2) For the given hash table, in what location will the element 58 be hashed using quadratic probing?

0     49  1  2  3  4  5  6  7  8     18  9     89  

1. 1
2. 2
3. 7
4. 6

Show Answer Workspace

3) Which one of the following data structures are preferred in database-system implementation?

1. AVL tree
2. B-tree
3. B+ – tree
4. Splay tree

Show Answer Workspace

4) Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the

hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is

inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

1. 8, _, _, _, _, _, 10
2. 1, 8, 10, _, _, _, 3
3. 1, _, _, _, _, _,3
4. 1, 10, 8, _, _, _, 3

Show Answer Workspace

5) What maximum difference in heights between the leafs of a AVL tree is possible?

1. log(n) where n is the number of nodes
2. n where n is the number of nodes
3. 0 or 1
4. Atmost 1

Show Answer Workspace

6) How can you save memory when storing color information in Red-Black tree?

1. using least significant bit of one of the pointers in the node for color information
2. using another array with colors of each node
3. storing color information in the node structure
4. using negative and positive numbering

Show Answer Workspace

7) What are the worst case and average case complexities of a binary search tree?

1. O(n), O(n)
2. O(log n), O(log n)
3. O(logn), O(n)
4. O(n), O(log n)

Show Answer Workspace

8) Which of the following is the efficient data structure for searching words in dictionaries?

1. BST
2. Linked List
3. Balanced BST
4. Trie

Show Answer Workspace

9) In the following given hash table, use linear probing to find the location of 49.

0  1  2  3  4  5  6  7  8 18  9 89  

1. 7
2. 6
3. 2
4. 0

Show Answer Workspace

10) When we have red-black trees and AVL trees that can perform most of operations in logarithmic times, then what is the need for splay trees?

1. no there is no special usage
2. In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
3. redblack and AVL are not upto mark
4. they are just another type of self-balancing binary search trees

Show Answer Workspace

11) We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

1. 0
2. 1
3. n!
4. 1/n+1

Show Answer Workspace

12) Which of the following is true?

1. larger the order of B-tree, less frequently the split occurs
2. larger the order of B-tree, more frequently the split occurs
3. smaller the order of B-tree, more frequently the split occurs
4. smaller the order of B-tree, less frequently the split occurs

Show Answer Workspace

13) If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m,

where n ≤ m, the expected number of collisions involving a particular key x is less than _______.

1. 1
2. 1/n
3. 1/m
4. n/m

Show Answer Workspace

14) Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?

1. 14
2. 7
3. 11
4. 5

Show Answer Workspace

15) A dictionary has a set of ——- and each key has a single associated value.

1. Keys
2. Index
3. Both keys and index
4. None of the above

Show Answer Workspace

16) Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

1. 8 – – – – – 10
2. 1 8 10 – – – 3
3. 1 – – – – – 3
4. 1 10 8 – – – 3

Show Answer Workspace

17) Consider the below left-left rotation pseudo code where the node contains value pointers to left, right child nodes and a height value and Height() function returns height value stored at a particular node.

 avltree leftrotation(avltreenode z):   avltreenode w =x-left   x-left=w-right   w-right=x   x-height=max(Height(x-left),Height(x-right))+1    w-height=max(missing)+1    return w  

What is missing?

1. Height(w-left), x-height
2. Height(w-right), x-height
3. Height(w-left), x
4. Height(w-left)

Show Answer Workspace

18) Which hashing technique is free from clustering?

1. Linear Probing
2. Double hashing
3. Quadratic hashing
4. Rehashing

Show Answer Workspace

19) We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

1. 0
2. 1
3. n!
4. (1/(n+1)).2nCn

Show Answer Workspace

20) Which hash function is used in the division method?

1. h(k) = k/m
2. h(k) = k mod m
3. h(k) = m/k
4. h(k) = m mod k

Show Answer Workspace

21) When it would be optimal to prefer Red-black trees over AVL trees?

1. when there are more insertions or deletions
2. when more search is needed
3. when tree must be balanced
4. when log(nodes) time complexity is needed

Show Answer Workspace

22) In the balanced binary tree in Fig. given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?

1. 1
2. 3
3. 4
4. 7

Show Answer Workspace

23) What is the special property of red-black trees and what root should always be?

1. a color which is either red or black and root should always be black color only
2. height of the tree
3. a color which is either green or black
4. pointer to next node

Show Answer Workspace

24) What is the disadvantage of using splay trees?

1. height of a splay tree can be linear when accessing elements in non-decreasing order
2. splay operations are difficult
3. splay tree performs unnecessary splay when a node is only being read
4. no significant disadvantage

Show Answer Workspace

25) Which of the following data structure can provide efficient searching of the elements?

1. unordered lists
2. Binary Search tree
3. treap
4. 2-3 tree

Show Answer Workspace

26) Consider the pseudo code:

int avl(binarysearchtree root): if(not root) return 0 left….tree….height = avl(left….of….root) if(left….tree….height== -1) return left….tree….height right….tree….height= avl(right….of….root) if(right….tree….height==-1) return

right….tree….height.

Does the above code can check if a binary search tree is an AVL tree?

1. YES
2. NO

Show Answer Workspace

27) Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?

1. just build the tree with the given input
2. find the median of the set of elements given, make it as root and construct the tree
3. use trial and error
4. use dynamic programming to build the tree

Show Answer Workspace

28) If several elements are competing for the same bucket in the hash table, what is it called?

1. Diffusion
2. Replication
3. Collision
4. Duplication

Show Answer Workspace

29) Which of the following is not the self balancing binary search tree?

1. AVL Tree
2. Red – Black Tree
3. Splay Tree
4. None of the above

Show Answer Workspace

30) What is the output of the following piece of code?

1. 3 and 5
2. 5 and 3
3. 2 and 4
4. 4 and 2

Show Answer Workspace

31) 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.

1. 2
2. 3
3. 4
4. 5

Show Answer Workspace

32) What output does the below pseudo code produces?

1. right rotation of subtree
2. left rotation of subtree
3. zig-zag operation
4. zig-zig operation

Show Answer Workspace

33) What can be the value of m in the division method?

1. Any prime number
2. Any even number
3. 2p – 1
4. 2p

Show Answer Workspace

34) What does the following piece of code do?

1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
4. Level order traversal

Show Answer Workspace

35) At what position the number 72 gets inserted in the following table?

Index Key

0   22  1   34  2  3  4  5   56  6  7   18  8   41  9  10  

1. 3
2. 10
3. 7
4. 6

Show Answer Workspace

36) To restore the AVL property after inserting an element, we start at the insertion point and move towards root of that tree. is this statement true?

1. TRUE
2. FALSE

Show Answer Workspace

37) Why we need to a binary tree which is height balanced?

1. to avoid formation of skew trees
2. to save memory
3. to attain faster memory access
4. to simplify storing

Show Answer Workspace

38) What are the operations that could be performed in O(logn) time complexity by red-black tree?

1. insertion, deletion, finding predecessor, successor
2. only insertion
3. only finding predecessor, successor
4. for sorting

Show Answer Workspace

39) A dictionary is also called

1. a hash
2. a map
3. a hashmap
4. All of above

Show Answer Workspace

40) Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

1. h(i)=i*i mod 10
2. h(i)=i*i*i mod 10
3. h(i)=(11∗i*i) mod 10
4. h(i)=(12∗i) mod 10

Show Answer Workspace