Study Glance
☑ MCQ PRACTICE

Data Structures Unit 4

Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.

📚 Data Structures
📖 Unit 4
🎯 MCQs

Data Structures - Unit-4

1
Which of the following is true about Depth-First Search (DFS) of a graph?
AIt traverses by exploring the highest-depth nodes first before backtracking.
BIt can be implemented using a queue data structure.
CIt is used to compute the shortest path in a graph.
DIt can get trapped in loops or cycles if the graph is cyclic and not properly handled.
Correct Answer It can get trapped in loops or cycles if the graph is cyclic and not properly handled.
2
What is the time complexity of Breadth-First Search (BFS) on a graph?
AO(V)
BO(V + E)
CO(E)
DO(log V)
Correct Answer O(V + E)
3
In Breadth-First Search (BFS), which data structure is typically used to hold the nodes that are next to be visited?
AStack
BQueue
CPriority Queue
DLinked List
Correct Answer Queue
4
Which of the following scenarios is more efficiently solved using Depth-First Search (DFS)?
AFinding the shortest path in a weighted graph.
BFinding connected components in a graph.
CFinding the minimum spanning tree.
DImplementing Dijkstra's algorithm.
Correct Answer Finding connected components in a graph.
5
What is a key characteristic of Breadth-First Search (BFS)?
AIt is recursive.
BIt visits nodes as far from the root as possible before backtracking.
CIt can be used to detect cycles in a directed graph.
DIt explores all neighbors of a node before moving on to the next level of nodes.
Correct Answer It explores all neighbors of a node before moving on to the next level of nodes.
6
In which case would you prefer BFS over DFS?
AWhen you need to find paths with the minimum number of edges.
BWhen the graph has cycles and you want to avoid getting trapped.
CWhen the solution is likely to be far from the root node.
DWhen memory usage is a critical concern.
Correct Answer When you need to find paths with the minimum number of edges.
7
Which of the following statements about graph traversal is FALSE?
ABFS can be used to find the shortest path in an unweighted graph.
BDFS can be implemented both recursively and iteratively.
CBFS always requires more memory than DFS.
DIn DFS, if a graph is tree-structured, the traversal visits every edge exactly twice.
Correct Answer BFS always requires more memory than DFS.
8
Which data structure is used to implement a graph using an adjacency list?
AArray
BLinked List
CHash Table
DTree
Correct Answer Linked List
9
In an adjacency matrix representation of a graph, how is an edge between vertices 'u' and 'v' represented?
ABy setting the value at position (u, v) to 0
BBy setting the value at position (u, v) to the weight of the edge or 1 if the graph is unweighted
CBy incrementing the value at position (u, v)
DBy inserting the value at the end of the matrix
Correct Answer By setting the value at position (u, v) to the weight of the edge or 1 if the graph is unweighted
10
What is the time complexity of adding a new edge in the adjacency list representation?
AO(1)
BO(V)
CO(E)
DO(V + E)
Correct Answer O(1)
11
Which of the following statements is true for a dense graph (a graph where the number of edges is close to the maximum number of edges)?
AAdjacency list representation is more space-efficient than adjacency matrix.
BAdjacency matrix representation is more space-efficient than adjacency list.
CAdjacency matrix representation takes more time for adding a new edge compared to adjacency list.
DAdjacency list representation takes more time for checking the existence of an edge compared to adjacency matrix.
Correct Answer Adjacency matrix representation is more space-efficient than adjacency list.
12
In an adjacency list representation, what does each index of the array represent?
AAn edge in the graph
BA vertex in the graph
CThe weight of an edge
DThe total number of vertices
Correct Answer A vertex in the graph
13
What is the space complexity of a graph with 'V' vertices and 'E' edges when using an adjacency matrix representation?
AO(V)
BO(E)
CO(V + E)
DO(V^2)
Correct Answer O(V^2)
14
Which representation is generally preferred for graphs with lots of vertices but few edges (sparse graphs)?
AAdjacency Matrix
BAdjacency List
CBoth are equally preferable
DNeither of them is preferable
Correct Answer Adjacency List
15
How is a self-loop (an edge that connects a vertex to itself) represented in an adjacency matrix?
ABy setting the value at position (u, u) to 0
BBy setting the value at position (u, u) to 1 or the weight of the edge
CBy leaving the position (u, u) undefined
DBy setting the value at position (u, u) to -1
Correct Answer By setting the value at position (u, u) to 1 or the weight of the edge
16
What is the average time complexity of Quick Sort?
AO(n^2)
BO(n log n)
CO(log n)
DO(n)
Correct Answer O(n log n)
17
What is the worst-case time complexity of Quick Sort?
AO(n^2)
BO(n log n)
CO(log n)
DO(n)
Correct Answer O(n^2)
18
In Quick Sort, what is the purpose of the 'partition' operation?
ATo divide the array into two halves
BTo sort the entire array
CTo rearrange the elements so that all elements less than the pivot are on the left, and all greater are on the right
DTo find the maximum element of the array
Correct Answer To rearrange the elements so that all elements less than the pivot are on the left, and all greater are on the right
19
Which of the following is not a strategy for choosing a pivot in Quick Sort?
AAlways pick the first element as the pivot
BPick a random element as the pivot
CPick the median as the pivot
DPick the element with the highest value as the pivot
Correct Answer Pick the element with the highest value as the pivot
20
What is the main advantage of Quick Sort over other sorting algorithms like Merge Sort?
AQuick Sort is easier to implement
BQuick Sort uses less memory
CQuick Sort is stable
DQuick Sort has a better worst-case time complexity
Correct Answer Quick Sort uses less memory
21
What is a characteristic of Quick Sort when the pivot element is always the greatest or the smallest element?
AIt results in the best performance
BIt results in the worst performance
CIt does not change the performance
DIt makes Quick Sort a stable sort
Correct Answer It results in the worst performance
22
Which of the following is true about Quick Sort?
AIt is a stable sorting algorithm
BIt is a comparison-based sorting algorithm
CIt is not a comparison-based sorting algorithm
DIt uses a divide and conquer strategy but does not combine the results
Correct Answer It is a comparison-based sorting algorithm
23
What is the space complexity of Quick Sort in its general implementation (not the in-place version)?
AO(n)
BO(log n)
CO(1)
DO(n log n)
Correct Answer O(log n)
24
What is the time complexity of building a heap for Heap Sort?
AO(n log n)
BO(n)
CO(log n)
DO(n^2)
Correct Answer O(n)
25
What is the worst-case time complexity of Heap Sort?
AO(n)
BO(n log n)
CO(log n)
DO(n^2)
Correct Answer O(n log n)
26
Heap Sort is primarily implemented using which data structure?
AArray
BLinked List
CBinary Tree
DComplete Binary Heap
Correct Answer Complete Binary Heap
27
Which of the following is a characteristic of a max heap used in Heap Sort?
AThe value of each node is greater than or equal to the values of its children.
BThe value of each node is less than or equal to the values of its children.
CAll leaf nodes are at the same level.
DAll levels of the tree, except possibly the last one, are fully filled.
Correct Answer The value of each node is greater than or equal to the values of its children.
28
In Heap Sort, after the initial build heap phase, where is the largest element of the heap?
AAt the end of the array
BAt the start of the array
CAt the middle of the array
DAt the root of the heap
Correct Answer At the start of the array
29
What does the Heapify process do in Heap Sort?
AIt sorts the entire array.
BIt swaps the first and last elements of the heap.
CIt creates a new heap from an unordered array.
DIt maintains the heap property by adjusting the position of elements in the heap.
Correct Answer It maintains the heap property by adjusting the position of elements in the heap.
30
What is the space complexity of Heap Sort?
AO(n)
BO(log n)
CO(1)
DO(n log n)
Correct Answer O(1)
31
Which of the following statements is true regarding Heap Sort?
AHeap Sort is a stable sorting algorithm.
BHeap Sort is not a comparison-based sorting algorithm.
CHeap Sort is an in-place sorting algorithm.
DHeap Sort performs better than Quick Sort in all cases.
Correct Answer Heap Sort is an in-place sorting algorithm.
32
What is the time complexity of Merge Sort in the worst-case scenario?
AO(n)
BO(n log n)
CO(log n)
DO(n^2)
Correct Answer O(n log n)
33
Merge Sort is a classic example of which algorithmic principle?
ADynamic Programming
BGreedy Algorithm
CDivide and Conquer
DBacktracking
Correct Answer Divide and Conquer
34
Which of the following is true about the space complexity of Merge Sort?
AIt's in-place and uses O(1) extra space.
BIt uses O(n) extra space.
CIt uses O(log n) extra space.
DIt uses O(n log n) extra space.
Correct Answer It uses O(n) extra space.
35
During the merge process in Merge Sort, what happens?
AThe array is divided into two halves.
BThe individual elements are sorted.
CTwo sorted arrays are combined into one sorted array.
DThe entire array is sorted at once.
Correct Answer Two sorted arrays are combined into one sorted array.
36
What is a significant advantage of Merge Sort?
AIt is the fastest sorting algorithm.
BIt has the least space complexity among all sorting algorithms.
CIt is a stable sort.
DIt works best on linked lists.
Correct Answer It is a stable sort.
37
Which of the following is NOT a characteristic of Merge Sort?
AIt has a consistent running time regardless of the initial order of the elements.
BIt is usually faster than Quick Sort for small datasets.
CIt requires additional memory for the temporary array used during the merge process.
DIt is an in-place sorting algorithm.
Correct Answer It is an in-place sorting algorithm.
38
In the context of Merge Sort, what does the 'conquer' step involve?
ADividing the array into smaller subarrays.
BCombining the sorted subarrays into a single sorted array.
CSorting the individual subarrays.
DSwapping elements to ensure the array is sorted.
Correct Answer Combining the sorted subarrays into a single sorted array.
39
How does Merge Sort perform on linked lists compared to arrays?
AIt performs worse because it's not a stable sort.
BIt performs better because it doesn't require random access.
CPerformance is the same as arrays.
DIt cannot be applied to linked lists.
Correct Answer It performs better because it doesn't require random access.

Fill in the Blanks

40 ________ Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.
Correct Answer Quick
41 In Quick Sort, the choice of the ________ can greatly affect the algorithm's performance.
Correct Answer pivot
42 ________ Sort is a comparison-based sorting technique based on the Binary Heap data structure, known for its ability to sort in O(n log n) time complexity.
Correct Answer Heap
43 The Heap Sort algorithm starts by building a ________ (max heap or min heap) and then repeatedly extracts the maximum or minimum element and rebuilds the heap.
Correct Answer heap
44 ________ Sort is a stable, divide-and-conquer, comparison-based sorting algorithm, most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output.
Correct Answer Merge
45 Merge Sort is particularly known for its ________ performance on large lists or arrays, as its time complexity is always O(n log n).
Correct Answer predictable
46 Quick Sort is generally faster than other O(n log n) algorithms like Merge Sort and Heap Sort, especially for ________ datasets.
Correct Answer small to medium
47 One of the disadvantages of Merge Sort is that it requires additional ________, making it less memory efficient.
Correct Answer space
48 Heap Sort can be preferred when the data is ________, meaning there are no constraints on the memory usage, and we require a guaranteed O(n log n) performance regardless of the input data.
Correct Answer large and external (or not in RAM)
49 The ________ nature of Merge Sort makes it advantageous for sorting linked lists.
Correct Answer stable
50 A graph can be implemented using two common methods: the adjacency ________ and the adjacency ________.
Correct Answer matrix, list
51 An adjacency ________ is a 2D array where each cell [i][j] indicates whether there is an edge from vertex i to vertex j.
Correct Answer matrix
52 An adjacency ________ is a collection of lists or sets, where each list or set represents a vertex in the graph and contains the list of neighbors or connected vertices.
Correct Answer list
53 The space complexity of an adjacency matrix is O(V^2), whereas the space complexity of an adjacency list is O(V + E), where V is the number of vertices and E is the number of ________.
Correct Answer edges
54 ________ First Search (DFS) is a graph traversal method that explores as far as possible along each branch before backtracking.
Correct Answer Depth
55 ________ First Search (BFS) is a graph traversal method that explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Correct Answer Breadth
56 In DFS, a ________ data structure is typically used to remember the nodes to visit next.
Correct Answer stack
57 In BFS, a ________ data structure is typically used to keep track of the nodes to visit next.
Correct Answer queue
58 The time complexity for both BFS and DFS is O(V + E) when implemented using an adjacency ________ for a graph with V vertices and E edges.
Correct Answer list
59 For weighted graphs, the adjacency ________ implementation can include weights in the matrix cells, with a special value (like 0 or infinity) indicating no direct connection between vertices.
Correct Answer matrix
← Back to All MCQs