Objective Type Questions & Answers

Data Structures Objective Type Question Bank-Unit-4

1. Which of the following is true about Depth-First Search (DFS) of a graph?

A . It traverses by exploring the highest-depth nodes first before backtracking.

B . It can be implemented using a queue data structure.

C . It is used to compute the shortest path in a graph.

D . It can get trapped in loops or cycles if the graph is cyclic and not properly handled.

Answer

2. What is the time complexity of Breadth-First Search (BFS) on a graph?

A . O(V)

B . O(V + E)

C . O(E)

D . O(log V)

Answer

3. In Breadth-First Search (BFS), which data structure is typically used to hold the nodes that are next to be visited?

A . Stack

B . Queue

C . Priority Queue

D . Linked List

Answer

4. Which of the following scenarios is more efficiently solved using Depth-First Search (DFS)?

A . Finding the shortest path in a weighted graph.

B . Finding connected components in a graph.

C . Finding the minimum spanning tree.

D . Implementing Dijkstra`s algorithm.

Answer

5. What is a key characteristic of Breadth-First Search (BFS)?

A . It is recursive.

B . It visits nodes as far from the root as possible before backtracking.

C . It can be used to detect cycles in a directed graph.

D . It explores all neighbors of a node before moving on to the next level of nodes.

Answer

6. In which case would you prefer BFS over DFS?

A . When you need to find paths with the minimum number of edges.

B . When the graph has cycles and you want to avoid getting trapped.

C . When the solution is likely to be far from the root node.

D . When memory usage is a critical concern.

Answer

7. Which of the following statements about graph traversal is FALSE?

A . BFS can be used to find the shortest path in an unweighted graph.

B . DFS can be implemented both recursively and iteratively.

C . BFS always requires more memory than DFS.

D . In DFS, if a graph is tree-structured, the traversal visits every edge exactly twice.

Answer

8. Which data structure is used to implement a graph using an adjacency list?

A . Array

B . Linked List

C . Hash Table

D . Tree

Answer

9. In an adjacency matrix representation of a graph, how is an edge between vertices `u` and `v` represented?

A . By setting the value at position (u, v) to 0

B . By setting the value at position (u, v) to the weight of the edge or 1 if the graph is unweighted

C . By incrementing the value at position (u, v)

D . By inserting the value at the end of the matrix

Answer

10. What is the time complexity of adding a new edge in the adjacency list representation?

A . O(1)

B . O(V)

C . O(E)

D . O(V + E)

Answer

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)?

A . Adjacency list representation is more space-efficient than adjacency matrix.

B . Adjacency matrix representation is more space-efficient than adjacency list.

C . Adjacency matrix representation takes more time for adding a new edge compared to adjacency list.

D . Adjacency list representation takes more time for checking the existence of an edge compared to adjacency matrix.

Answer

12. In an adjacency list representation, what does each index of the array represent?

A . An edge in the graph

B . A vertex in the graph

C . The weight of an edge

D . The total number of vertices

Answer

13. What is the space complexity of a graph with `V` vertices and `E` edges when using an adjacency matrix representation?

A . O(V)

B . O(E)

C . O(V + E)

D . O(V^2)

Answer

14. Which representation is generally preferred for graphs with lots of vertices but few edges (sparse graphs)?

A . Adjacency Matrix

B . Adjacency List

C . Both are equally preferable

D . Neither of them is preferable

Answer

15. How is a self-loop (an edge that connects a vertex to itself) represented in an adjacency matrix?

A . By setting the value at position (u, u) to 0

B . By setting the value at position (u, u) to 1 or the weight of the edge

C . By leaving the position (u, u) undefined

D . By setting the value at position (u, u) to -1

Answer

16. What is the average time complexity of Quick Sort?

A . O(n^2)

B . O(n log n)

C . O(log n)

D . O(n)

Answer

17. What is the worst-case time complexity of Quick Sort?

A . O(n^2)

B . O(n log n)

C . O(log n)

D . O(n)

Answer

18. In Quick Sort, what is the purpose of the `partition` operation?

A . To divide the array into two halves

B . To sort the entire array

C . To rearrange the elements so that all elements less than the pivot are on the left, and all greater are on the right

D . To find the maximum element of the array

Answer

19. Which of the following is not a strategy for choosing a pivot in Quick Sort?

A . Always pick the first element as the pivot

B . Pick a random element as the pivot

C . Pick the median as the pivot

D . Pick the element with the highest value as the pivot

Answer

20. What is the main advantage of Quick Sort over other sorting algorithms like Merge Sort?

A . Quick Sort is easier to implement

B . Quick Sort uses less memory

C . Quick Sort is stable

D . Quick Sort has a better worst-case time complexity

Answer

21. What is a characteristic of Quick Sort when the pivot element is always the greatest or the smallest element?

A . It results in the best performance

B . It results in the worst performance

C . It does not change the performance

D . It makes Quick Sort a stable sort

Answer

22. Which of the following is true about Quick Sort?

A . It is a stable sorting algorithm

B . It is a comparison-based sorting algorithm

C . It is not a comparison-based sorting algorithm

D . It uses a divide and conquer strategy but does not combine the results

Answer

23. What is the space complexity of Quick Sort in its general implementation (not the in-place version)?

A . O(n)

B . O(log n)

C . O(1)

D . O(n log n)

Answer

24. What is the time complexity of building a heap for Heap Sort?

A . O(n log n)

B . O(n)

C . O(log n)

D . O(n^2)

Answer

25. What is the worst-case time complexity of Heap Sort?

A . O(n)

B . O(n log n)

C . O(log n)

D . O(n^2)

Answer

26. Heap Sort is primarily implemented using which data structure?

A . Array

B . Linked List

C . Binary Tree

D . Complete Binary Heap

Answer

27. Which of the following is a characteristic of a max heap used in Heap Sort?

A . The value of each node is greater than or equal to the values of its children.

B . The value of each node is less than or equal to the values of its children.

C . All leaf nodes are at the same level.

D . All levels of the tree, except possibly the last one, are fully filled.

Answer

28. In Heap Sort, after the initial build heap phase, where is the largest element of the heap?

A . At the end of the array

B . At the start of the array

C . At the middle of the array

D . At the root of the heap

Answer

29. What does the Heapify process do in Heap Sort?

A . It sorts the entire array.

B . It swaps the first and last elements of the heap.

C . It creates a new heap from an unordered array.

D . It maintains the heap property by adjusting the position of elements in the heap.

Answer

30. What is the space complexity of Heap Sort?

A . O(n)

B . O(log n)

C . O(1)

D . O(n log n)

Answer

31. Which of the following statements is true regarding Heap Sort?

A . Heap Sort is a stable sorting algorithm.

B . Heap Sort is not a comparison-based sorting algorithm.

C . Heap Sort is an in-place sorting algorithm.

D . Heap Sort performs better than Quick Sort in all cases.

Answer

32. What is the time complexity of Merge Sort in the worst-case scenario?

A . O(n)

B . O(n log n)

C . O(log n)

D . O(n^2)

Answer

33. Merge Sort is a classic example of which algorithmic principle?

A . Dynamic Programming

B . Greedy Algorithm

C . Divide and Conquer

D . Backtracking

Answer

34. Which of the following is true about the space complexity of Merge Sort?

A . It`s in-place and uses O(1) extra space.

B . It uses O(n) extra space.

C . It uses O(log n) extra space.

D . It uses O(n log n) extra space.

Answer

35. During the merge process in Merge Sort, what happens?

A . The array is divided into two halves.

B . The individual elements are sorted.

C . Two sorted arrays are combined into one sorted array.

D . The entire array is sorted at once.

Answer

36. What is a significant advantage of Merge Sort?

A . It is the fastest sorting algorithm.

B . It has the least space complexity among all sorting algorithms.

C . It is a stable sort.

D . It works best on linked lists.

Answer

37. Which of the following is NOT a characteristic of Merge Sort?

A . It has a consistent running time regardless of the initial order of the elements.

B . It is usually faster than Quick Sort for small datasets.

C . It requires additional memory for the temporary array used during the merge process.

D . It is an in-place sorting algorithm.

Answer

38. In the context of Merge Sort, what does the `conquer` step involve?

A . Dividing the array into smaller subarrays.

B . Combining the sorted subarrays into a single sorted array.

C . Sorting the individual subarrays.

D . Swapping elements to ensure the array is sorted.

Answer

39. How does Merge Sort perform on linked lists compared to arrays?

A . It performs worse because it`s not a stable sort.

B . It performs better because it doesn`t require random access.

C . Performance is the same as arrays.

D . It cannot be applied to linked lists.

Answer

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.

Answer

41. In Quick Sort, the choice of the ________ can greatly affect the algorithm`s performance.

Answer

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.

Answer

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.

Answer

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.

Answer

45. Merge Sort is particularly known for its ________ performance on large lists or arrays, as its time complexity is always O(n log n).

Answer

46. Quick Sort is generally faster than other O(n log n) algorithms like Merge Sort and Heap Sort, especially for ________ datasets.

Answer

47. One of the disadvantages of Merge Sort is that it requires additional ________, making it less memory efficient.

Answer

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.

Answer

49. The ________ nature of Merge Sort makes it advantageous for sorting linked lists.

Answer

50. A graph can be implemented using two common methods: the adjacency ________ and the adjacency ________.

Answer

51. An adjacency ________ is a 2D array where each cell [i][j] indicates whether there is an edge from vertex i to vertex j.

Answer

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.

Answer

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 ________.

Answer

54. ________ First Search (DFS) is a graph traversal method that explores as far as possible along each branch before backtracking.

Answer

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.

Answer

56. In DFS, a ________ data structure is typically used to remember the nodes to visit next.

Answer

57. In BFS, a ________ data structure is typically used to keep track of the nodes to visit next.

Answer

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.

Answer

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.

Answer