Category: Data Structure Objective Questions

Data Structure Multiple Choice Questions on “Priority Queue”.

1. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Heap
d) Tree
Answer: d
Clarification: Priority queue can be implemented using an array, a list, a binary search tree or a heap, although the most efficient one being the heap.

2. Which of the following is not an application of priority queue?
a) Huffman codes
b) Interrupt handling in operating system
c) Undo operation in text editors
d) Bayesian spam filter
Answer: c
Clarification: Undo operation is achieved using a stack.

3. Select the appropriate code that inserts elements into the list based on the given key value.
(head and trail are dummy nodes to mark the end and beginning of the list, they do not contain any priority or element)
a)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(temp);
			temp.setNext(dup);
		}
		count++;
	}
}

b)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = dup;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(temp);
			temp.setNext(dup);
		}
		count++;
	}
}

c)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(dup);
			temp.setNext(cur);
		}
		count++;
	}
}

d)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = cur
				cur = cur.getNext();
			}
			cur.setNext(dup);
			temp.setNext(cur);
		}
		count++;
	}
}

View Answer

Answer: a
Clarification: Have two temporary pointers ‘dup’ and ‘cur’ with ‘cur’ trailing behind ‘dup’. Traverse through the list until the given key is greater than some element with a lesser key, insert the new node ‘temp’ in that position.

4. What is the time complexity to insert a node based on key in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
Answer: c
Clarification: In the worst case, you might have to traverse the entire list.

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

public Object delete_key() 
{
	if(count == 0)
	{
		System.out.println("Q is empty");
		System.exit(0);
	}
	else
	{
		Node cur = head.getNext();
		Node dup = cur.getNext();
		Object e = cur.getEle();
		head.setNext(dup);
		count--;
		return e;
	}
}

a) Delete the second element in the list
b) Return but not delete the second element in the list
c) Delete the first element in the list
d) Return but not delete the first element in the list
Answer: c
Clarification: A pointer is made to point at the first element in the list and one more to point to the second element, pointer manipulations are done such that the first element is no longer being pointed by any other pointer, its value is returned.

6. What is not a disadvantage of priority scheduling in operating systems?
a) A low priority process might have to wait indefinitely for the CPU
b) If the system crashes, the low priority systems may be lost permanently
c) Interrupt handling
d) Indefinite blocking
Answer: c
Clarification: The lower priority process should wait until the CPU completes the processing higher priority process. Interrupt handling is an advantage as interrupts should be given more priority than tasks at hand so that interrupt can be serviced to produce desired results.

7. Which of the following is not an advantage of a priority queue?
a) Easy to implement
b) Processes with different priority can be efficiently handled
c) Applications with differing requirements
d) Easy to delete elements in any case
Answer: d
Clarification: In worst case, the entire queue has to be searched for the element having the highest priority. This will take more time than usual. So deletion of elements is not an advantage.

8. What is the time complexity to insert a node based on position in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
Answer: c
Clarification: In the worst case, you might have to traverse the entire list.

Data Structure Multiple Choice Questions on “Dynamic Array”.

1. What is a dynamic array?
a) A variable size data structure
b) An array which is created at runtime
c) The memory to the array is allocated at runtime
d) An array which is reallocated everytime whenever new elements have to be added
Answer: a
Clarification: It is a varying-size list data structure that allows items to be added or removed, it may use a fixed sized array at the back end.

2. What is meant by physical size in a dynamic array?
a) The size allocated to elements
b) The size extended to add new elements
c) The size of the underlying array at the back-end
d) The size visible to users
Answer: c
Clarification: Physical size, also called array capacity is the size of the underlying array, which is the maximum size without relocation of data.

3. The number of items used by the dynamic array contents is its __________
a) Physical size
b) Capacity
c) Logical size
d) Random size
Answer: c
Clarification: The number of items used by the dynamic array contents is called logical size. Physical size is the size of the underlying array, which is the maximum size without reallocation of data.

4. How will you implement dynamic arrays in Java?
a) Set
b) Map
c) HashMap
d) List
Answer: d
Clarification: ArrayList is used to implement dynamic arrays in Java.

5. Which of the following is the correct syntax to declare an ArrayList in Java?
a) ArrayList al = new ArrayList();
b) ArrayList al = new ArrayList[];
c) ArrayList al() = new ArrayList();
d) ArrayList al[] = new ArrayList[];
Answer: a
Clarification: This is a non-generic way of creating an ArrayList.

6. Array is divided into two parts in ____________
a) Hashed Array Tree
b) Geometric Array
c) Bounded-size dynamic array
d) Sparse Array
Answer: c
Clarification: The first part stores the items of the dynamic array and the second part is reserved for new allocations.

7. Which of the following is a disadvantage of dynamic arrays?
a) Locality of reference
b) Data cache utilization
c) Random access
d) Memory leak
Answer: d
Clarification: Dynamic arrays share the advantage of arrays, added to it is the dynamic addition of elements to the array. Memory can be leaked if it is not handled properly during allocation and deallocation. It is a disadvantage.

8. What is the time complexity for inserting/deleting at the beginning of the array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer: b
Clarification: All the other elements will have to be moved, hence O(n).

9. Dynamic arrays overcome the limit of static arrays.
a) True
b) False
Answer: a
Clarification: Static arrays have fixed capacity. The capacity must be specified during memory allocation. Dynamic arrays don’t require to specify their capacity during memory allocation. Dynamic arrays have fixed physical size at backend and its capacity increases if required. Thus, Dynamic arrays overcome the limit of static arrays.

10. The size of the dynamic array is deallocated if the array size is less than _________% of the backend physical size.
a) 30
b) 40
c) 10
d) 20
Answer: a
Clarification: The size of the dynamic array is decreased/deallocated if the actual size of the array is less than 30% of the backend physical size. This is used to avoid memory wastage.

11. Both Dynamic array and Dynamically memory allocated array are same.
a) True
b) False
Answer: b
Clarification: Physical size of a Dynamic array is fixed with a larger value. Dynamically memory allocated arrays are arrays whose memory is allocated at run time rather than at compile time. Dynamically memory allocated arrays don’t have physical size at the backend. Thus, Dynamic arrays and Dynamically memory allocated arrays are different.

12. In which of the following cases dynamic arrays are not preferred?
a) If the size of the array is unknown
b) If the size of the array changes after few iterations
c) If the memory reallocation takes more time i.e. expensive
d) If the array holds less number of elements
Answer: d
Clarification: Dynamic arrays are preferred when the size of the array is unknown during memory allocation or the size changes after few iterations or the memory reallocation is expensive. If array holds less number of elements, the physical size is reduced and reduction takes more time. In that case, we can use normal arrays instead of dynamic arrays.

13. The growth factor of ArrayList in Java is _______
a) 1
b) 1.5
c) 2
d) 0
Answer: b
Clarification: The growth factor of dynamic arrays (Array List) in Java is 3/2.
The new array capacity is calculated as new_array_size = (old_array_size*3)/2+1.

14. In special case, the time complexity of inserting/deleting elements at the end of dynamic array is __________
a) O (n)
b) O (n^1/2)
c) O (log n)
d) O (1)
Answer: a
Clarification: In general, the time complexity of inserting or deleting elements at the end of dynamic array is O (1). Elements are added at reserved space of dynamic array. If this reserved space is exceeded, then the physical size of the dynamic array is reallocated and every element is copied from original array. This will take O(n) time to add new element at the end of the array.

15. Which of the following arrays are used in the implementation of list data type in python?
a) Bit array
b) Dynamic arrays
c) Sparse arrays
d) Parallel arrays
Answer: b
Clarification: Dynamic arrays are used in the implementation of list data type in python. Sparse arrays are used in the implementation of sparse matrix in Numpy module. All bit array operations are implemented in bitarray module.

Data Structures & Algorithms Multiple Choice Questions on “Treap”.

1. What is the space complexity of a treap algorithm?
a) O(N)
b) O(log N)
c) O(log N)
d) O(N²)

Answer: a
Clarification: The average case and worst case space complexity of a treap is mathematically found to be O(N).

2. A treap is a combination of a tree and a heap.
a) false
b) true

Answer: b
Clarification: A treap is a combination of a tree and a heap. The structure of a treap is determined by the fact that it is heap-ordered.

3. Which is the simplest of all binary search trees?
a) AVL tree
b) Treap
c) Splay tree
d) Binary heap

Answer: b
Clarification: A treap is the simplest of all binary search trees. Each node is given a numeric priority and implementation is non recursive.

4. What is the reason behind the simplicity of a treap?
a) Each node has data and a pointer
b) Each node is colored accordingly
c) It is a binary search tree following heap principles
d) Each node has a fixed priority field

Answer: d
Clarification: A treap is the simplest of all because we don’t have to worry about adjusting the priority of a node.

5. What is the condition for priority of a node in a treap?
a) a node’s priority should be greater than its parent
b) a node’s priority should be at least as large as its parent
c) the priority is randomly assigned and can have any value
d) a node’s priority is always given in decreasing order

Answer: b
Clarification: A node’s priority should satisfy heap order. That is, any node’s priority should be at least as large as its parent.

6. Several other operations like union set difference and intersection can be done in treaps.
a) True
b) False

Answer: a
Clarification: Other than insertion, deletion and search operations, several operations like union, intersection and set difference can be done in treaps.

7. What is the average running time of a treap?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(M log N)

Answer: c
Clarification: The average case and worst case analysis of a treap are mathematically found to be O(log N).

8. Which node has the lowest priority in a treap?
a) root node
b) leaf node
c) null node
d) centre node

Answer: a
Clarification: A root node has the lowest priority in a treap since the node’s priority is based on heap order.

9. What is the priority of a null node?
a) 1
b) 0
c) random number
d) infinity

Answer: d
Clarification: The priority of a null node is set to be infinity in a treap so that during deletion, priority of that particular node is set to infinity, rotated and freed.

10. Who invented treaps?
a) Cecilia and Raimund
b) Arne Andersson
c) Donald Shell
d) Harris and Ross

Answer: a
Clarification: Cecilia and Raimund invented Treaps. Arne Andersson invented AA – Trees. Donald Shell invented shell sort and Harris and Ross formulated maximum flow problem.

Data Structure Multiple Choice Questions on “Heap”.

1. In a max-heap, element with the greatest key is always in the which node?
a) Leaf node
b) First node of left sub tree
c) root node
d) First node of right sub tree
Answer: c
Clarification: This is one of the property of max-heap that root node must have key greater than its children.

2. Heap exhibits the property of a binary tree?
a) True
b) False
Answer: a
Clarification: Yes, because the leaf nodes are present at height h or h-1, which is a property of complete binary tree.

3. What is the complexity of adding an element to the heap.
a) O(log n)
b) O(h)
c) O(log n) & O(h)
d) O(n)
Answer: c
Clarification: The total possible operation in re locating the new location to a new element will be equal to height of the heap.

4. The worst case complexity of deleting any arbitrary node value element from heap is __________
a) O(logn)
b) O(n)
c) O(nlogn)
d) O(n²)
Answer: a
Clarification: The total possible operation in deleting the existing node and re locating new position to all its connected nodes will be equal to height of the heap.

5. Heap can be used as ________________
a) Priority queue
b) Stack
c) A decreasing order array
d) Normal Array
Answer: a
Clarification: The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.

6. If we implement heap as min-heap, deleting root node (value 1)from the heap. What would be the value of root node after second iteration if leaf node (value 100) is chosen to replace the root at start.

a) 2
b) 100
c) 17
d) 3
Answer: a
Clarification: As the root is deleted and node with value 100 is used as replaced one. There is a violation of property that root node must have value less than its children. So there will be shuffling of node with value 100 with node of value 2. And thus 2 becomes root. And it will remain to be at root after all the possible operations. So the value at root will be 2.

7. If we implement heap as maximum heap , adding a new node of value 15 to the left most node of right subtree. What value will be at leaf nodes of the right subtree of the heap.

a) 15 and 1
b) 25 and 1
c) 3 and 1
d) 2 and 3
Answer: a
Clarification: As 15 is less than 25 so there would be no violation and the node will remain at that position. So leaf nodes with value 15 and 1 will be at the position in right sub tree.

8. An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in order of
a) O(n*n*logn)
b) O(n*logn)
c) O(n*n)
d) O(n *logn *logn)
Answer: b
Clarification: The total time taken will be N times the complexity of adding a single element to the heap. And adding a single element takes logN time, so That is equal to N*logN.

Data Structures & Algorithms Multiple Choice Questions on “Hash Tables Chaining using Doubly Linked Lists”.

1. Which of the following is used in hash tables to determine the index of any input record?
a) hash function
b) hash linked list
c) hash tree
d) hash chaining

Answer: a
Clarification: Hash table is an example of a data structure that is built for fast access of elements. Hash functions are used to determine the index of any input record in a hash table.

2. What is the advantage of a hash table as a data structure?
a) faster access of data
b) easy to implement
c) very efficient for less number of entries
d) exhibit good locality of reference

Answer: a
Clarification: Hash table is a data structure that has an advantage that it allows fast access of elements. Hash functions are used to determine the index of any input record in a hash table.

3. What is the use of a hash function?
a) to calculate and return the index of corresponding data
b) to store data
c) to erase data
d) to change data

Answer: a
Clarification: Hash function calculates and returns the index for corresponding data. This data is then mapped in a hash table.

4. What is the time complexity of insert function in a hash table using a doubly linked list?
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). Condition is that the number of collisions should be low.

5. What is the time complexity of search function in a hash table using a doubly linked list?
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 delete function in the hash table using a doubly linked list?
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. Hashing can be used to encrypt and decrypt digital signatures.
a) true
b) false

Answer: a
Clarification: Hashing is also used in encryption algorithms. It is used for encryption and decryption of digital signatures.

8. What is the advantage of using a doubly linked list for chaining over singly linked list?
a) it takes less memory
b) it is easy to implement
c) it makes the process of insertion and deletion faster
d) it causes less collisions

Answer: c
Clarification: Using a doubly linked list reduces time complexity significantly. Though it uses more memory to store the extra pointer.

9. Which of the following technique stores data in the hash table itself in case of a collision?
a) Open addressing
b) Chaining using linked list
c) Chaining using doubly linked list
d) Chaining using binary tree

Answer: a
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. Which of the following technique stores data in a separate entity in case of a collision?
a) Open addressing
b) Chaining using doubly linked list
c) Linear probing
d) Double hashing

Answer: b
Clarification: Chaining using doubly linked list is used to store data in a separate entity (doubly linked list in this case) in case of a collision. Whereas open addressing stores it in the table itself.

11. Collision is caused due to the presence of two keys having the same value.
a) True
b) False

Answer: a
Clarification: A collision is caused due to the presence of two keys having the same value. It is handled by using any one of the two methods namely:- Chaining and Open addressing.