Category: Data Structure Objective Questions

250+ TOP MCQs on Double Ended Queue (Dequeue) and Answers

Data Structure Multiple Choice Questions on “Double Ended Queue (Dequeue)”.

1. What is a dequeue?
a) A queue with insert/delete defined for both front and rear ends of the queue
b) A queue implemented with a doubly linked list
c) A queue implemented with both singly and doubly linked lists
d) A queue with insert/delete defined for front side of the queue
Answer: a
Clarification: A dequeue or a double ended queue is a queue with insert/delete defined for both front and rear ends of the queue.

2. Select the function which performs insertion at the front end of the dequeue?
a)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		temp.setNext(trail);
		head.setNext(temp);
	}
	else
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	size++;
}

b)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		temp.setNext(trail);
		head.setNext(trail);
	}
	else
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	size++;
}

c)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	else
	{
		temp.setNext(trail);
		head.setNext(temp);
	}
	size++;
}

d)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		cur.setNext(temp);
	}
	else
	{
		head.setNext(trail);
		trail.setNext(temp);
	}
	size++;
}

View Answer

Answer: a
Clarification: Create a new node, if the current list is empty, the ‘head’ points to this node and this new node points to ‘trail’. Otherwise, ‘head’ points to the new node and this in turn points to the current first element(head.getNext()).

 
 
3. What is the functionality of the following piece of code?

public void function(Object item)
{
	Node temp=new Node(item,trail);
	if(isEmpty())
	{
		head.setNext(temp);
		temp.setNext(trail);
	}
	else
	{
		Node cur=head.getNext();
		while(cur.getNext()!=trail)
		{
			cur=cur.getNext();
		}
		cur.setNext(temp);
	}
	size++;
}

a) Insert at the front end of the dequeue
b) Insert at the rear end of the dequeue
c) Fetch the element at the rear end of the dequeue
d) Fetch the element at the front end of the dequeue
Answer: b
Clarification: If the list is empty, this new node will point to ‘trail’ and will be pointed at by ‘head’. Otherwise, traverse till the end of the list and insert the new node there.

4. What are the applications of dequeue?
a) A-Steal job scheduling algorithm
b) Can be used as both stack and queue
c) To find the maximum of all sub arrays of size k
d) To avoid collision in hash tables
Answer: d
Clarification: All of the mentioned can be implemented with a dequeue.

5. Which of the following can be used to delete an element from the front end of the queue?
a)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp;
		Object e = temp.getEle();
		head.setNext(cur);
		size--;
		return e;
	}
}

b)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		head.setNext(cur);
		size--;
		return e;
	}
}

c)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		head.setNext(temp);
		size--;
		return e;
	}
}

d)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		temp.setNext(cur);
		size--;
		return e;
	}
}

View Answer

Answer: b
Clarification: Have two pointers, one(temp) pointing to the first element and the other(cur) pointing to the second element. Make the ‘head’ point to the second element, this removes all reference for ‘temp’.

 
 
6. Which of the following can be used to delete an element from the rear end of the queue?
a)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp;
		while(temp.getNext() != trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		cur.setNext(trail);
		size--;
		return e;
	}
}

b)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = head;
		while(temp != trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		cur.setNext(trail);
		size--;
		return e;
	}
}

c)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
	throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = head;
		while(temp.getNext()!=trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		cur.setNext(trail);
		size--;
		return e;
	}
}

d)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
	throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = head;
		while(temp.getNext()!=trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		temp.setNext(trail);
		size--;
		return e;
	}
}

View Answer

Answer: c
Clarification: Traverse till the end of the list with a pointer ‘temp’ and another ‘cur’ which is trailing behind temp, make ‘cur’ point to trail, this removes all reference for ‘temp’.

 
 
7. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer

Answer: c
Clarification: Since a singly linked list is used, first you have to traverse till the end, so the complexity is O(n).

8. After performing these set of operations, what does the final list look contain?

InsertFront(10);
InsertFront(20);
InsertRear(30);
DeleteFront();
InsertRear(40);
InsertRear(10);
DeleteRear();
InsertRear(15);
display();

a) 10 30 10 15
b) 20 30 40 15
c) 20 30 40 10
d) 10 30 40 15
Answer: d
Clarification: A careful tracing of the given operation yields the result.
10
20 10
20 10 30
10 30
10 30 40
10 30 40 10
10 30 40
10 30 40 15

250+ TOP MCQs on Parallel Array and Answers

Data Structure Multiple Choice Questions on “Parallel Array”.

1. What are parallel arrays?
a) Arrays of the same size
b) Arrays allocated one after the other
c) Arrays of the same number of elements
d) Arrays allocated dynamically
Answer: c
Clarification: Different arrays can be of different data types but should contain same number of elements. Elements at corresponding index belong to a record.

2. Which of the following can be called a parallel array implementation?
a)

   firstName  = ['Joe','Bob','Frank','Hans']
   lastName   = ['Smith','Seger','Sinatra','Schultze']
   heightInCM = [169,158,201,199]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

b)

   firstName  = ['Joe','Bob','Frank','Hans']
   lastName   = ['Smith','Seger']
   heightInCM = [169,158]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

c)

   firstName  = ['Joe','Bob']
   lastName   = ['Smith','Seger','Sinatra','Schultze']
   heightInCM = [169,158]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

d)

   firstName  = ['Joe','Bob']
   lastName   = ['Smith','Seger' ,'Schultze']
   heightInCM = [169,158]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

View Answer

Answer: a
Clarification: All the arrays must have equal length, that is, contain same number of elements.

 
 

3. Which of the following is a disadvantage of parallel array over the traditional arrays?
a) When a language does not support records, parallel arrays can be used
b) Increased locality of reference
c) Ideal cache behaviour
d) Insertion and Deletion becomes tedious
Answer: d
Clarification: Insertion and deletion of elements require to move every element from their initial positions. This will become tedious. For Record collection, locality of reference and Ideal Cache behaviour we can use parallel arrays.

4. Which of the following is an advantage of parallel arrays?
a) Poor locality of reference for non-sequential access
b) Very little direct language support
c) Expensive to shrink or grow
d) Increased Locality of Reference
Answer: d
Clarification: Elements in the parallel array are accessed sequentially as one arrays holds the keys whereas other holds the values. This sequential access generally improves Locality of Reference. It is an advantage.

5. What is a sorted array?
a) Arrays sorted in numerical order
b) Arrays sorted in alphabetical order
c) Elements of the array are placed at equally spaced addresses in the memory
d) All of the mentioned
Answer: d
Clarification: The array can be sorted in any way, numerical, alphabetical or any other way but the elements are placed at equally spaced addresses.

6. To search for an element in a sorted array, which searching technique can be used?
a) Linear Search
b) Jump Search
c) Binary Search
d) Fibonacci Search
Answer: c
Clarification: Since the array is sorted, binary search is preferred as its time complexity is O(logn).

7. Which of the following is not an application of sorted array?
a) Commercial computing
b) Priority Scheduling
c) Discrete Mathematics
d) Hash Tables
Answer: d
Clarification: Sorted arrays have widespread applications as all commercial computing involves large data which is very useful if it is sorted. It makes best use of locality of reference and data cache. Linked lists are used in Hash Tables not arrays.

8. What is the worst case time complexity of inserting an element into the sorted array?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: c
Clarification: In the worst case, an element must added to the front of the array, which means that rest of the elements have to be shifted, hence the worst case time complexity becomes O(n).

250+ TOP MCQs on Preorder Traversal and Answers

Data Structure Multiple Choice Questions on “Preorder Traversal”.

1. Select the code snippet which performs pre-order traversal.
a)

public void preorder(Tree root)
{
	System.out.println(root.data);
	preorder(root.left);
	preorder(root.right);
}

b)

public void preorder(Tree root)
{
	preorder(root.left);
	System.out.println(root.data);
	preorder(root.right);
}

c)

public void preorder(Tree root)
{
	System.out.println(root.data);
	preorder(root.right);
	preorder(root.left);
}

d)

public void preorder(Tree root)
{
	preorder(root.right);
	preorder(root.left);
        System.out.println(root.data); 
}

Answer: a
Clarification: Pre-order traversal follows NLR(Node-Left-Right).

2. Select the code snippet which performs post-order traversal.
a)

public void postorder(Tree root)
{
	System.out.println(root.data);
	postorder(root.left);
	postorder(root.right);
}

b)

public void postorder(Tree root)
{
	postorder(root.left);
	postorder(root.right);
	System.out.println(root.data);
}

c)

public void postorder(Tree root)
{
	System.out.println(root.data);
	postorder(root.right);
	postorder(root.left);
}

d)

public void postorder(Tree root)
{
	postorder(root.right);
        System.out.println(root.data);
	postorder(root.left);
}

Answer: b
Clarification: Post order traversal follows NLR(Left-Right-Node).

3. Select the code snippet that performs pre-order traversal iteratively.
a)

public void preOrder(Tree root) 
{   
        if (root == null) return;
	Stack<Tree> stk = new Stack<Tree>();
        st.add(root);        
	while (!stk.empty()) 
        {
            Tree node = stk.pop();           
            System.out.print(node.data + " ");
			if (node.left != null) stk.push(node.left);
            if (node.right != null) stk.push(node.right);
        }
}

b)

public void preOrder(Tree root) 
{   
        if (root == null) return;
		Stack<Tree> stk = new Stack<Tree>();      
	while (!stk.empty()) 
        {
            Tree node = stk.pop();           
            System.out.print(node.data + " ");
            if (node.right != null) stk.push(node.right);
            if (node.left != null) stk.push(node.left);
        }
}

c)

public void preOrder(Tree root) 
{   
        if (root == null) return;
	Stack<Tree> stk = new Stack<Tree>();
        st.add(root);        
	while (!stk.empty()) 
        {
            Tree node = stk.pop();           
            System.out.print(node.data + " ");
            if (node.right != null) stk.push(node.right);
            if (node.left != null) stk.push(node.left);
        }
}

d)

public void preOrder(Tree root) 
{   
        if (root == null) return;
	Stack<Tree> stk = new Stack<Tree>();
        st.add(root);        
	while (!stk.empty()) 
        {
            Tree node = stk.pop();           
            System.out.print(node.data + " ");
            if (node.right != null) stk.push(node.left);
            if (node.left != null) stk.push(node.right);
        }
}

Answer: c
Clarification: Add the root to the stack first, then continously check for the right and left children of the top-of-the-stack.

4. Select the code snippet that performs post-order traversal iteratively.
a)

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.right;
            }
	    node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

b)

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
            node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

c)

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

d)

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeLeft;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

Answer: b
Clarification: The left and right children are added first to the stack, followed by the node, which is then popped. Post-order follows LRN policy.

5. What is the time complexity of pre-order traversal in the iterative fashion?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)

Answer: b
Clarification: Since you have to go through all the nodes, the complexity becomes O(n).

6. What is the space complexity of the post-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)

Answer: d
Clarification: In the worst case we have d stack frames in the recursive call, hence the complexity is O(d).

7. To obtain a prefix expression, which of the tree traversals is used?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal

Answer: b
Clarification: As the name itself suggests, pre-order traversal can be used.

8. Consider the following data. The pre order traversal of a binary tree is A, B, E, C, D. The in order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is _________
a) A, C, D, B, E
b) A, B, C, D, E
c) A, B, C, E, D
d) D, B, E, A, C
Answer: b

9. Consider the following data and specify which one is Preorder Traversal Sequence, Inorder and Postorder sequences.
S1: N, M, P, O, Q
S2: N, P, Q, O, M
S3: M, N, O, P, Q
a) S1 is preorder, S2 is inorder and S3 is postorder
b) S1 is inorder, S2 is preorder and S3 is postorder
c) S1 is inorder, S2 is postorder and S3 is preorder
d) S1 is postorder, S2 is inorder and S3 is preorder

Answer: c
Clarification: Preorder traversal starts from the root node and postorder and inorder starts from the left child node of the left subtree. The first node of S3 is different and for S1 and S2 it’s the same. Thus, S3 is preorder traversal and the root node is M. Postorder traversal visits the root node at last. S2 has the root node(M) at last that implies S2 is postorder traversal. S1 is inorder traversal as S2 is postorder traversal and S3 is preorder traversal. Therefore, S1 is inorder traversal, S2 is postorder traversal and S3 is preorder traversal.

250+ TOP MCQs on Threaded Binary Tree and Answers

Data Structure Multiple Choice Questions on “Threaded Binary Tree”.

1. What is a threaded binary tree traversal?
a) a binary tree traversal using stacks
b) a binary tree traversal using queues
c) a binary tree traversal using stacks and queues
d) a binary tree traversal without using stacks and queues
Answer: d
Clarification: This type of tree traversal will not use stack or queue.

2. What are the disadvantages of normal binary tree traversals?
a) there are many pointers which are null and thus useless
b) there is no traversal which is efficient
c) complexity in implementing
d) improper traversals
Answer: a
Clarification: As there are majority of pointers with null value going wasted we use threaded binary trees.

3. In general, the node content in a threaded binary tree is ________
a) leftchild_pointer, left_tag, data, right_tag, rightchild_pointer
b) leftchild_pointer, left_tag
c) leftchild_pointer, left_tag, right_tag, rightchild_pointer
d) leftchild_pointer, left_tag, data
Answer: a
Clarification: It contains additional 2 pointers over normal binary tree node structure.

4. What are null nodes filled with in a threaded binary tree?
a) inorder predecessor for left node and inorder successor for right node information
b) right node with inorder predecessor and left node with inorder successor information
c) they remain null
d) some other values randomly
Answer: a
Clarification: If preorder or postorder is used then the respective predecessor and successor info is stored.

5. Which of the following tree traversals work if the null left pointer pointing to the predecessor and null right pointer pointing to the successor in a binary tree?
a) inorder, postorder, preorder traversals
b) inorder
c) postorder
d) preorder
Answer: a
Clarification: In threaded binary trees, the null left pointer points to the predecessor and the right null pointer point to the successor. In threaded binary trees, we can use in-order, preorder and postorder traversals to visit every node in the tree.

6. What are double and single threaded trees?
a) when both left, right nodes are having null pointers and only right node is null pointer respectively
b) having 2 and 1 node
c) using single and double linked lists
d) using heaps and priority queues
Answer: a
Clarification: They are properties of double and single threaded binary trees respectively.

7. What is wrong with below code for inorder traversal of inorder threaded binary tree:

   inordertraversal(threadedtreenode root):
   threadedtreenode q = inorderpredecessor(root)
   while(q!=root):
   q=inorderpredecessor(q)
   print q.data

a) inordersuccessor instead of inorderpredecessor must be done
b) code is correct
c) it is code for post order
d) it is code for pre order
Answer: a
Clarification: Property of inorder threaded binary tree is left node with inorder predecessor and right node with inorder successor information are stored.

8. What is inefficient with the below threaded binary tree picture?
data-structure-questions-answers-threaded-binary-tree-q8
a) it has dangling pointers
b) nothing inefficient
c) incorrect threaded tree
d) space is being used more
Answer: a
Clarification: The nodes extreme left and right are pointing to nothing which could be also used efficiently.

250+ TOP MCQs on Binary Heap and Answers

Data Structure Multiple Choice Questions on “Binary Heap”.

1. What is the space complexity of searching in a heap?
a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)
Answer: b
Clarification: The space complexity of searching an element in heap is O (n). Heap consists of n elements and we need to compare every element. Here no addition or deletion of elements takes place. Hence space complexity is O (n).

2. What is the best case complexity in building a heap?
a) O(nlogn)
b) O(n2)
c) O(n*longn *logn)
d) O(n)
Answer: d
Clarification: The best case complexity occurs in bottom-up construction when we have a sortes array given.

3. Given the code, choose the correct option that is consistent with the code. (Here A is the heap)

	build(A,i)
	left-> 2*i
	right->2*i +1
	temp- > i
	if(left<= heap_length[A] ans A[left] >A[temp])
	temp -> left
	if (right = heap_length[A] and A[right] > A[temp])
	temp->right
	if temp!= i
	swap(A[i],A[temp])
	build(A,temp)

a) It is the build function of max heap
b) It is the build function of min heap
c) It is general build function of any heap
d) It is used to search element in any heap
Answer: a
Clarification: Since in every condition we are comparing the current value is less than the parent of that node. So this is build function of Max heap.

4. What is the location of a parent node for any arbitary node i?
a) (i/2) position
b) (i+1)/ position
c) floor(i/2) position
d) ceil(i/2) position
Answer: c
Clarification: For any node child nodes are located at either 2*i, 2*i +1 So the parent node could be found by taking the floor of the half of child node.

5. State the complexity of algorithm given below.

	int function(vector<int> arr)
	int len=arr.length();
	if(len==0)
	return;
	temp=arr[len-1];
	arr.pop_back();
	return temp;

a) o(n)
b) O(logn)
c) O(1)
d) O(n logn)
Answer: c
Clarification: Deletion in a min-heap is in O(1) time.

6. Given an array of element 5, 7, 9, 1, 3, 10, 8, 4. Which of the following are the correct sequences of elements after inserting all the elements in a min-heap?
a) 1,3,4,5,7,8,9,10
b) 1,4,3,9,8,5,7,10
c) 1,3,4,5,8,7,9,10
d) 1,3,7,4,8,5,9,10
Answer: a
Clarification: Building a min-heap the result will a sorted array so the 1, 3, 4, 5, 7, 8, 9, 10 is correct. If we change the implementation strategy 1, 4, 3, 8, 9, 5, 7, 10 is also correct. (First filling the right child rather than left child first).

7. For construction of a binary heap with property that parent node has value less than child node. In reference to that which line is incorrect. Line indexed from 1.

1. add(int k)
2. {
3.     heap_size++;
4.     int i = heap_size - 1;
5.     harr[i] = k;
6.     while (i != 0 && harr[parent(i)] < harr[i])
7.     {
8.             swap(&harr[i], &harr[parent(i)]);
9.             i = parent(i);
10.    }
11. }

a) Line – 3
b) Line – 5
c) Line – 6
d) Line – 7
Answer: c
Clarification: The condition under while condition is wrong for a (min) binary heap The correct condition should be while(i!=0 && harr[parent(i)] > harr[i]). Otherwise the constructed heap will be a max-binary heap.

250+ TOP MCQs on Hash Tables Chaining with Binary Trees and Answers

Data Structures & Algorithms Multiple Choice Questions on “Hash Tables Chaining with Binary Trees”.

1. Which of the following variant of a hash table has the best cache performance?
a) hash table using a linked list for separate chaining
b) hash table using binary search tree for separate chaining
c) hash table using open addressing
d) hash table using a doubly linked list for separate chaining

Answer: c
Clarification: Implementation of the hash table using open addressing has a better cache performance as compared to separate chaining. It is because open addressing stores data in the same table without using any extra space.

2. What is the advantage of hashing with chaining?
a) cache performance is good
b) uses less space
c) less sensitive to hash function
d) has a time complexity of O(n) in the worst case

Answer: c
Clarification: Hashing with separate chaining has an advantage that it is less sensitive to a hash function. It is also easy to implement.

3. What is the disadvantage of hashing with chaining?
a) not easy to implement
b) takes more space
c) quite sensitive to hash function
d) table gets filled up easily

Answer: b
Clarification: Hashing with separate chaining has a disadvantage that it takes more space. This space is used for storing elements in case of a collision.

4. What is the time complexity of insert function in a hash table using a binary tree?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: Time complexity of insert function in a hash table is O(1) on an average. Condition is that the number of collisions should be low.

5. What is the time complexity of the search function in a hash table using a binary tree?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: Time complexity of search function in a hash table is O(1). Condition is that the number of collisions should be low.

6. What is the time complexity of the delete function in the hash table using a binary tree?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: Time complexity of delete function in a hash table is O(1). Condition is that the hash function should be such that the number of collisions should be low.

7. What is the advantage of a hash table over BST?
a) hash table has a better average time complexity for performing insert, delete and search operations
b) hash table requires less space
c) range query is easy with hash table
d) easier to implement

Answer: a
Clarification: Hash table and BST both are examples of data structures. Hash table has an advantage that it has a better time complexity for performing insert, delete and search operations.

8. What is the disadvantage of BST over the hash table?
a) BST is easier to implement
b) BST can get the keys sorted by just performing inorder traversal
c) BST can perform range query easily
d) Time complexity of hash table in inserting, searching and deleting is less than that of BST

Answer: d
Clarification: BST has an advantage that it is easier to implement, can get the keys sorted by just performing in-order traversal and can perform range query easily. Hash table has lesser time complexity for performing insert, delete and search operations.

9. Which of the following technique stores data separately in case of a collision?
a) Open addressing
b) Double hashing
c) Quadratic probing
d) Chaining using a binary tree

Answer: d
Clarification: Open addressing is used to store data in the table itself in case of a collision. Whereas chaining stores data in a separate entity.

10. Separate chaining is easier to implement as compared to open addressing.
a) true
b) false

Answer: a
Clarification: There are two methods of handling collisions in a hash table:- open addressing and separate chaining. Open addressing requires more computation as compared to separate chaining.

11. In open addressing the hash table can never become full.
a) True
b) False

Answer: b
Clarification: There are two methods of handling collisions in a hash table:- open addressing and separate chaining. In open addressing the hash table can become full.