Advance Data Structure MCQs
40 MCQs of Advance Data Structure
1) What is the load factor for an open addressing technique?
1
0
5
0.5
Answer: c) 0.5
Explanation:
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
2
7
6
Answer: b) 2
3) Which one of the following data structures are preferred in database-system implementation?
AVL tree
B-tree
B+ - tree
Splay tree
Answer: c) B+ - tree
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.
8, _, _, _, _, _, 10
1, 8, 10, _, _, _, 3
1, _, _, _, _, _,3
1, 10, 8, _, _, _, 3
Answer: b) 1, 8, 10, _, _, _, 3
5) What maximum difference in heights between the leafs of a AVL tree is possible?
log(n) where n is the number of nodes
n where n is the number of nodes
0 or 1
Atmost 1
Answer: a) log(n) where n is the number of nodes
6) How can you save memory when storing color information in Red-Black tree?
using least significant bit of one of the pointers in the node for color information
using another array with colors of each node
storing color information in the node structure
using negative and positive numbering
Answer: a) using least significant bit of one of the pointers in the node for color information
7) What are the worst case and average case complexities of a binary search tree?
O(n), O(n)
O(log n), O(log n)
O(logn), O(n)
O(n), O(log n)
Answer: d) O(n), O(log n)
8) Which of the following is the efficient data structure for searching words in dictionaries?
BST
Linked List
Balanced BST
Trie
Answer: d) trie
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
7
6
2
0
Answer: d) 0
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?
no there is no special usage
In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
redblack and AVL are not upto mark
they are just another type of self-balancing binary search trees
Answer: b) In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
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?
0
1
n!
1/n+1
Answer: b) 1
12) Which of the following is true?
larger the order of B-tree, less frequently the split occurs
larger the order of B-tree, more frequently the split occurs
smaller the order of B-tree, more frequently the split occurs
smaller the order of B-tree, less frequently the split occurs
Answer: a) larger the order of B-tree, less frequently the split occurs
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/n
1/m
n/m
Answer: a) 1
14) Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
14
7
11
5
Answer: c) 11
15) A dictionary has a set of ------- and each key has a single associated value.
Keys
Index
Both keys and index
None of the above
Answer: a) Keys
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.
8 - - - - - 10
1 8 10 - - - 3
1 - - - - - 3
1 10 8 - - - 3
Answer: b) 1 8 10 - - - 3
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?
Height(w-left), x-height
Height(w-right), x-height
Height(w-left), x
Height(w-left)
Answer: a) Height(w-left), x-height
18) Which hashing technique is free from clustering?
Linear Probing
Double hashing
Quadratic hashing
Rehashing
Answer: b) Double hashing
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?
0
1
n!
(1/(n+1)).2nCn
Answer: b) 1
20) Which hash function is used in the division method?
h(k) = k/m
h(k) = k mod m
h(k) = m/k
h(k) = m mod k
Answer: b) h(k) = k mod m
21) When it would be optimal to prefer Red-black trees over AVL trees?
when there are more insertions or deletions
when more search is needed
when tree must be balanced
when log(nodes) time complexity is needed
Answer: a) when there are more insertions or deletions
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
3
4
7
Answer: b) 3
23) What is the special property of red-black trees and what root should always be?
a color which is either red or black and root should always be black color only
height of the tree
a color which is either green or black
pointer to next node
Answer: a) a color which is either red or black and root should always be black color only
24) What is the disadvantage of using splay trees?
height of a splay tree can be linear when accessing elements in non-decreasing order
splay operations are difficult
splay tree performs unnecessary splay when a node is only being read
no significant disadvantage
Answer: a) height of a splay tree can be linear when accessing elements in non-decreasing order
25) Which of the following data structure can provide efficient searching of the elements?
unordered lists
Binary Search tree
treap
2-3 tree
Answer: d) 2-3 tree
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?
YES
NO
Answer: a) YES
27) Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
just build the tree with the given input
find the median of the set of elements given, make it as root and construct the tree
use trial and error
use dynamic programming to build the tree
Answer: b) find the median of the set of elements given, make it as root and construct the tree
28) If several elements are competing for the same bucket in the hash table, what is it called?
Diffusion
Replication
Collision
Duplication
Answer: c) Collision
29) Which of the following is not the self balancing binary search tree?
AVL Tree
Red - Black Tree
Splay Tree
None of the above
Answer: d) None of the above
30) What is the output of the following piece of code?
public class array
{
public static void main(String args[])
{
int []arr = {1,2,3,4,5};
System.out.println(arr[2]);
System.out.println(arr[4]);
}
} public class array { public static void main(String args[]) { int []arr = {1,2,3,4,5}; System.out.println(arr[2]); System.out.println(arr[4]); } }
3 and 5
5 and 3
2 and 4
4 and 2
Answer: a) 3 and 5
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.
2
3
4
5
Answer: b) 3
32) What output does the below pseudo code produces?
Tree_node function(Tree_node x)
{
Tree_node y = x.left;
x.left = y.right;
y.right = x;
return y;
} Tree_node function(Tree_node x) { Tree_node y = x.left; x.left = y.right; y.right = x; return y; }
right rotation of subtree
left rotation of subtree
zig-zag operation
zig-zig operation
Answer: a) right rotation of subtree
33) What can be the value of m in the division method?
Any prime number
Any even number
2p - 1
2p
Answer: a) Any prime number
34) What does the following piece of code do?
public void func(Tree root)
{
func(root.left());
func(root.right());
System.out.println(root.data());
} public void func(Tree root) { func(root.left()); func(root.right()); System.out.println(root.data()); }
Preorder traversal
Inorder traversal
Postorder traversal
Level order traversal
Answer: c) Postorder traversal
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
3
10
7
6
Answer: d) 6
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?
TRUE
FALSE
Answer: a) TRUE
37) Why we need to a binary tree which is height balanced?
to avoid formation of skew trees
to save memory
to attain faster memory access
to simplify storing
Answer: a) to avoid formation of skew trees
38) What are the operations that could be performed in O(logn) time complexity by red-black tree?
insertion, deletion, finding predecessor, successor
only insertion
only finding predecessor, successor
for sorting
Answer: a) insertion, deletion, finding predecessor, successor
39) A dictionary is also called
a hash
a map
a hashmap
All of above
Answer: d) All of the above
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?
h(i)=i*i mod 10
h(i)=i*i*i mod 10
h(i)=(11∗i*i) mod 10
h(i)=(12∗i) mod 10
Answer: b) h(i)=i*i*i mod 10
Comments
Post a Comment