**MCQ on Data Structure**

**Question: What is the time complexity of inserting an element at the end of an array?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: a) O(1)

Explanation: Inserting an element at the end of an array takes constant time since the element can be placed directly at the end without any shifting or rearranging of existing elements.

**Question: Which data structure follows the Last In First Out (LIFO) principle?**

a) Queue

b) Stack

c) Linked List

d) Tree

Answer: b) Stack

Explanation: A stack is a data structure where the last element inserted is the first one to be removed. It follows the LIFO principle, similar to a stack of books where the topmost book is accessed first.

**Question: Which data structure is suitable for implementing a priority queue?**

a) Stack

b) Queue

c) Heap

d) Linked List

Answer: c) Heap

Explanation: A priority queue is a data structure that allows elements with higher priority to be accessed before elements with lower priority. A heap data structure is commonly used to implement a priority queue efficiently.

**Question: What is the time complexity of searching for an element in a binary search tree (BST)?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: b) O(log n)

Explanation: In a binary search tree, each comparison reduces the search space by half. As a result, the time complexity of searching in a balanced BST is logarithmic with respect to the number of elements.

**Question: Which data structure is suitable for implementing a FIFO queue?**

a) Stack

b) Queue

c) Linked List

d) Tree

Answer: b) Queue

Explanation: A queue is a data structure that follows the First In First Out (FIFO) principle, where the first element inserted is the first one to be removed. It is commonly used to implement a waiting list or a buffer.

**Question: Which data structure allows efficient insertion and deletion at both ends?**

a) Queue

b) Stack

c) Linked List

d) Array

Answer: c) Linked List

Explanation: A linked list allows efficient insertion and deletion at both ends (head and tail) since it only requires updating a few pointers. In contrast, arrays have fixed sizes, and inserting or deleting elements at the beginning or middle requires shifting elements.

**Question: Which data structure uses a hash function for indexing elements?**

a) Stack

b) Queue

c) Hash Table

d) Tree

Answer: c) Hash Table

Explanation: A hash table or hash map uses a hash function to compute an index (or hash) for each element. This index is used to store and retrieve elements, making it efficient for searching and accessing data.

**Question: Which data structure represents a hierarchical relationship among elements?**

a) Queue

b) Stack

c) Linked List

d) Tree

Answer: d) Tree

Explanation: A tree is a hierarchical data structure composed of nodes, where each node can have child nodes. It represents a hierarchical relationship or structure, such as organization charts or file systems.

**Question: Which data structure is used for storing elements in a sorted order?**

a) Stack

b) Queue

c) Linked List

d) Array

Answer: d) Array

Explanation: Arrays can store elements in a contiguous block of memory, allowing for efficient access by index. They are commonly used for sorting algorithms since elements can be rearranged easily to maintain a sorted order.

**Question: Which data structure is based on the “divide and conquer” strategy?**

a) Stack

b) Queue

c) Linked List

d) Tree

Answer: d) Tree

Explanation: Trees are often used in algorithms that follow the “divide and conquer” strategy. The problem is divided into smaller subproblems, which are solved recursively using tree structures to combine the results.

**Question: What is the time complexity of inserting an element at the beginning of a linked list?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: a) O(1)

Explanation: Inserting an element at the beginning of a linked list takes constant time since it involves creating a new node, updating the new node’s pointers, and adjusting the head pointer.

**Question: Which data structure is best suited for implementing a LIFO behavior?**

a) Queue

b) Stack

c) Linked List

d) Array

Answer: b) Stack

Explanation: A stack is designed to follow the Last In First Out (LIFO) principle. It allows inserting and removing elements from the top, making it suitable for applications like function call stacks and expression evaluation.

**Question: What is the time complexity of searching for an element in an unsorted array?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: c) O(n)

Explanation: In an unsorted array, the only way to search for an element is to iterate through each element until a match is found. Since the worst-case scenario is checking all elements, the time complexity is linear.

**Question: Which data structure is used to implement depth-first search (DFS) algorithm?**

a) Queue

b) Stack

c) Linked List

d) Tree

Answer: b) Stack

Explanation: Depth-first search (DFS) explores a graph or tree by visiting deeper nodes before backtracking. It uses a stack to keep track of the nodes to visit, allowing the traversal to go deeper before coming back up.

**Question: What is the time complexity of removing an element from a binary search tree (BST)?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: b) O(log n)

Explanation: Removing an element from a balanced binary search tree requires searching for the element to remove, which has a time complexity of O(log n) in the average and best cases. After finding the element, the removal can be done in constant time.

**Question: Which data structure is used to implement breadth-first search (BFS) algorithm?**

a) Queue

b) Stack

c) Linked List

d) Tree

Answer: a) Queue

Explanation: Breadth-first search (BFS) explores a graph or tree by visiting all neighbors of a node before visiting their neighbors. It uses a queue to keep track of the nodes to visit, ensuring that nodes are visited in a level-by-level manner.

**Question: Which data structure allows efficient searching, insertion, and deletion of elements with a key?**

a) Hash Table

b) Stack

c) Queue

d) Tree

Answer: a) Hash Table

Explanation: Hash tables provide efficient searching, insertion, and deletion of elements with a key. They use a hash function to compute an index, which allows direct access to the elements without the need for searching.

**Question: What is the time complexity of merging two sorted arrays into a new sorted array?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: c) O(n)

Explanation: Merging two sorted arrays into a new sorted array involves comparing and rearranging the elements. Since each element from both arrays needs to be visited once, the time complexity is linear.

**Question: Which data structure represents a relationship of “many-to-many” between elements?**

a) Stack

b) Queue

c) Linked List

d) Graph

Answer: d) Graph

Explanation: A graph represents a relationship between elements where multiple elements can have connections or edges to multiple other elements. It is used to model various scenarios, such as social networks or transportation networks.

**Question: What is the time complexity of performing a linear search in an array?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: c) O(n)

Explanation: In a linear search, each element of the array is compared sequentially until a match is found or all elements have been checked. Therefore, the time complexity is linear, as the worst-case scenario requires checking all elements.

**Question: Which data structure allows efficient finding of the minimum and maximum elements?**

a) Queue

b) Stack

c) Linked List

d) Heap

Answer: d) Heap

Explanation: A heap data structure allows efficient finding of the minimum and maximum elements. A min-heap provides constant-time access to the minimum element, while a max-heap provides constant-time access to the maximum element.

**Question: What is the time complexity of inserting an element in a hash table with separate chaining collision resolution?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: a) O(1)

Explanation: In a hash table with separate chaining, collisions are resolved by storing multiple elements with the same hash key in a linked list. Inserting an element in a linked list takes constant time, resulting in an average time complexity of O(1).

**Question: Which data structure is used for backtracking algorithms?**

a) Queue

b) Stack

c) Linked List

d) Tree

Answer: b) Stack

Explanation: Backtracking algorithms explore all possible solutions by making choices and then undoing them if they lead to a dead end. A stack is used to keep track of the choices made so far, allowing the algorithm to backtrack efficiently.

**Question: What is the time complexity of performing a binary search in a sorted array?**

a) O(1)

b) O(log n)

c) O(n)

d) O(n^2)

Answer: b) O(log n)

Explanation: Binary search repeatedly divides the search space in half, making it very efficient. The time complexity is logarithmic because the search space is halved with each comparison.

**Question: Which data structure is used for finding the shortest path between two vertices in a graph?**

a) Stack

b) Queue

c) Linked List

d) Graph

Answer: d) Graph

Explanation: Finding the shortest path between two vertices in a graph is typically accomplished using algorithms like Dijkstra’s algorithm or Breadth-First Search (BFS), which operate on the graph data structure itself.