Category: Data Structure Objective Questions

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.

Data Structure Multiple Choice Questions on “Directed Acyclic Graph”.

1. Every Directed Acyclic Graph has at least one sink vertex.
a) True
b) False
Answer: a
Clarification: A sink vertex is a vertex which has an outgoing degree of zero.

2. Which of the following is not a topological sorting of the given graph?

a) A B C D E F
b) A B F E D C
c) A B E C F D
d) A B C D F E
Answer: d
Clarification: Topological sorting is a linear arrangement of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. In A B C D F E, F comes before E in ordering.

3. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
a) (V*(V-1))/2
b) (V*(V+1))/2
c) (V+1)C2
d) (V-1)C2
Answer: a
Clarification: The first edge would have an outgoing degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2…. +1 equals (V*(V-1))/2.

4. The topological sorting of any DAG can be done in ________ time.
a) cubic
b) quadratic
c) linear
d) logarithmic
Answer: c
Clarification: Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.

5. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
a) Many Hamiltonian paths are possible
b) No Hamiltonian path is possible
c) Exactly 1 Hamiltonian path is possible
d) Given information is insufficient to comment anything
Answer: b
Clarification: For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.

6. What sequence would the BFS traversal of the given graph yield?

a) A F D B C E
b) C B A F E D
c) A B D C E F
d) E F D C B A
Answer: c
Clarification: In BFS nodes gets explored and then the neighbors of the current node gets explored, before moving on to the next levels.

7. What would be the output of the following C++ program if the given input is

0 0 0 1 1
0 0 0 0 1
0 0 0 1 0
1 0 1 0 0
1 1 0 0 0
 
#include 
using namespace std;
bool visited[5];
int G[5][5];
 
void fun(int i)
{
	cout<<i<<" ";
	visited[i]=true;
	for(int j=0;j<5;j++)
		if(!visited[j]&&G[i][j]==1)
			fun(j);
}
 
int main()
{   
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>G[i][j];
 
	for(int i=0;i<5;i++)
		visited[i]=0;
 
	fun(0);
		return 0;
}

a) 0 2 3 1 4
b) 0 3 2 4 1
c) 0 2 3 4 1
d) 0 3 2 1 4
Answer: b
Clarification: Given Input is the adjacency matrix of a graph G, whereas the function ‘fun’ prints the DFS traversal.

8. Which of the given statement is true?
a) All the Cyclic Directed Graphs have topological sortings
b) All the Acyclic Directed Graphs have topological sortings
c) All Directed Graphs have topological sortings
d) All the cyclic directed graphs hace non topological sortings
Answer: d
Clarification: Cyclic Directed Graphs cannot be sorted topologically.

9. For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?
a) True
b) False
Answer: b
Clarification: If such vertices exists it means that the graph contains a cycle which contradicts the first part of the statement.

10. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
a) Depends on a Graph
b) Will always be zero
c) Will always be greater than zero
d) May be zero or greater than zero
Answer: b
Clarification: Every Directed Acyclic Graph has a source and a sink vertex.

Data Structure Multiple Choice Questions on “Array and Array Operations”.

1. Which of these best describes an array?
a) A data structure that shows a hierarchical behavior
b) Container of objects of similar types
c) Arrays are immutable once initialised
d) Array is not a data structure
Answer: b
Clarification: Array contains elements only of the same type.

2. How do you initialize an array in C?
a) int arr[3] = (1,2,3);
b) int arr(3) = {1,2,3};
c) int arr[3] = {1,2,3};
d) int arr(3) = (1,2,3);
Answer: c
Clarification: This is the syntax to initialize an array in C.

3. How do you instantiate an array in Java?
a) int arr[] = new int(3);
b) int arr[];
c) int arr[] = new int[3];
d) int arr() = new int(3);
Answer: c
Clarification: Note that int arr[]; is declaration whereas int arr[] = new int[3]; is to instantiate an array.

4. Which of the following is the correct way to declare a multidimensional array in Java?
a) int[] arr;
b) int arr[[]];
c) int[][]arr;
d) int[[]] arr;
Answer: c
Clarification: The syntax to declare multidimensional array in java is either int[][] arr; or int arr[][];

5. What is the output of the following Java 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]);
	}
}

a) 3 and 5
b) 5 and 3
c) 2 and 4
d) 4 and 2
Answer: a
Clarification: Array indexing starts from 0.

6. What is the output of the following Java code?

public class array
{
	public static void main(String args[])
	{
		int []arr = {1,2,3,4,5};
		System.out.println(arr[5]);
	}
}

a) 4
b) 5
c) ArrayIndexOutOfBoundsException
d) InavlidInputException
Answer: c
Clarification: Trying to access an element beyond the limits of an array gives ArrayIndexOutOfBoundsException.

7. When does the ArrayIndexOutOfBoundsException occur?
a) Compile-time
b) Run-time
c) Not an error
d) Not an exception at all
Answer: b
Clarification: ArrayIndexOutOfBoundsException is a run-time exception and the compilation is error-free.

8. Which of the following concepts make extensive use of arrays?
a) Binary trees
b) Scheduling of processes
c) Caching
d) Spatial locality
Answer: d
Clarification: Whenever a particular memory location is referred to, it is likely that the locations nearby are also referred, arrays are stored as contiguous blocks in memory, so if you want to access array elements, spatial locality makes it to access quickly.

9. What are the advantages of arrays?
a) Objects of mixed data types can be stored
b) Elements in an array cannot be sorted
c) Index of first element of an array is 1
d) Easier to store elements of same data type
Answer: d
Clarification: Arrays store elements of the same data type and present in continuous memory locations.

10. What are the disadvantages of arrays?
a) Data structure like queue or stack cannot be implemented
b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
c) Index value of an array can be negative
d) Elements are sequentially accessed
Answer: b
Clarification: Arrays are of fixed size. If we insert elements less than the allocated size, unoccupied positions can’t be used again. Wastage will occur in memory.

11. Assuming int is of 4bytes, what is the size of int arr[15];?
a) 15
b) 19
c) 11
d) 60
Answer: d
Clarification: Since there are 15 int elements and each int is of 4bytes, we get 15*4 = 60bytes.

12. In general, the index of the first element in an array is __________
a) 0
b) -1
c) 2
d) 1
Answer: a
Clarification: In general, Array Indexing starts from 0. Thus, the index of the first element in an array is 0.

13. Elements in an array are accessed _____________
a) randomly
b) sequentially
c) exponentially
d) logarithmically
Answer: a
Clarification: Elements in an array are accessed randomly. In Linked lists, elements are accessed sequentially.