Mastering DSA Concepts

What is the time complexity of Bubble Sort in the worst case?

• O(n^2)

• O(n log n)

• O(log n)

• O(n)

Answer explanation

Bubble Sort has a worst-case time complexity of O(n^2) because it requires n passes through the list, and each pass involves comparing adjacent elements, leading to n * n comparisons in total.

Which of the following is a stable sorting algorithm?

• Selection Sort

• Merge Sort

• Bubble Sort

• Insertion Sort

Answer explanation

Merge Sort is a stable sorting algorithm because it maintains the relative order of equal elements. In contrast, Selection Sort, Bubble Sort, and Insertion Sort are not guaranteed to be stable.

What is the primary data structure used in a binary search tree?

• Node

• Leaf

• Tree

• Graph

Answer explanation

In a binary search tree, the primary data structure is a Node. Each Node contains a value and references to its left and right children, allowing for efficient searching, insertion, and deletion operations.

Which algorithm is used to find the shortest path in a graph?

• A* algorithm

• Dijkstra's algorithm

• Bellman-Ford algorithm

• Floyd-Warshall algorithm

Answer explanation

Dijkstra's algorithm is specifically designed to find the shortest path in a graph with non-negative edge weights. It efficiently calculates the shortest distance from a starting node to all other nodes, making it the correct choice.

What is the space complexity of Merge Sort?

• O(n)

• O(log n)

• O(1)

• O(n log n)

Answer explanation

Merge Sort has a space complexity of O(n) because it requires additional space for the temporary arrays used during the merging process. This makes O(n) the correct choice, as it reflects the linear space needed.

In which scenario would you use a Hash Table?

• When frequent updates to data are required without key access.

• When data needs to be stored in a linear format.

• When data is accessed in a sequential manner.

• When fast access to data via key-value pairs is required.

Answer explanation

A Hash Table is ideal for scenarios requiring fast access to data via key-value pairs, allowing for efficient retrieval and storage. Other options do not leverage the strengths of a Hash Table.

What is the main advantage of Quick Sort over other sorting algorithms?

• Its average-case time complexity of O(n log n) and in-place sorting capability.

• Its worst-case time complexity of O(n^2) is better than others.

• It is the only algorithm that can sort linked lists efficiently.

• It requires additional memory for sorting.

Answer explanation

The main advantage of Quick Sort is its average-case time complexity of O(n log n), which is efficient for large datasets, and its in-place sorting capability, allowing it to sort without requiring additional memory.

Which of the following is not a searching algorithm?

• Binary tree traversal

• Sorting algorithm (e.g., quicksort) is not a searching algorithm.

• Depth-first search

• Linear search

Answer explanation

The correct choice is 'Sorting algorithm (e.g., quicksort) is not a searching algorithm.' because sorting algorithms organize data, while searching algorithms locate specific data within a structure.

What is the base case in recursion?

• The base case is the first call made by a recursive function.

• The base case is the condition under which a recursive function stops calling itself.

• The base case is the maximum depth of recursion allowed.

• The base case is the variable that tracks the number of recursive calls.

Answer explanation

The base case is crucial in recursion as it defines the condition that stops further recursive calls, preventing infinite loops. This ensures that the function can eventually return a result, making the correct choice the second option.

What is the time complexity of linear search?

• O(log n)

• O(1)

• O(n^2)

• O(n)

Answer explanation

The time complexity of linear search is O(n) because in the worst case, it checks each element in the list once, leading to a linear relationship between the number of elements and the number of comparisons.