Dijkstra’s algorithm is used to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It uses a priority queue to efficiently select the next vertex to explore.
What is the primary advantage of Merge Sort?
A In-place sorting
B Simple to implement
C O(n log n) time
D Faster than Quick Sort
Merge Sort has a guaranteed time complexity of O(n log n) in all cases (best, worst, and average). It is highly efficient for large datasets, particularly when compared to algorithms like Bubble Sort.
Which algorithm is used to find the minimum spanning tree?
A Quick Sort
B Bellman-Ford
C Binary Search
D Kruskal’s Algorithm
Kruskal’s algorithm is a greedy algorithm used to find the minimum spanning tree of a graph. It sorts all edges in increasing order of their weights and adds them to the tree if they don’t form a cycle.
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)
Quick Sort has a worst-case time complexity of O(n^2), which occurs when the pivot selection is poor (e.g., when the array is already sorted or nearly sorted). However, it performs well on average.
Which of these algorithms uses the divide-and-conquer approach?
A Merge Sort
B Binary Search
C Quick Sort
D All of the above
Merge Sort, Quick Sort, and Binary Search all use the divide-and-conquer approach. They divide the problem into smaller subproblems, solve them independently, and combine the solutions to get the final result.
(“All of the above” remains in position D.)
What is the primary disadvantage of the Bubble Sort algorithm?
A Requires too much memory
B Does not handle sorted arrays
C Slow for large datasets
D Needs recursion
Bubble Sort has a time complexity of O(n^2) in the worst and average cases. This makes it inefficient for large datasets, as it repeatedly compares adjacent elements and swaps them until the array is sorted.
Which algorithm is typically used to find the shortest path in a graph with non-negative edge weights?
A Dijkstra’s Algorithm
B Bellman-Ford
C Floyd-Warshall
D Kruskal’s Algorithm
Dijkstra’s algorithm is designed to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It uses a greedy approach with a priority queue for efficiency.
What is the space complexity of Merge Sort?
A O(1)
B O(n)
C O(log n)
D O(n log n)
Merge Sort requires additional space to store temporary subarrays during the merging process. The space complexity is O(n), where n is the number of elements in the array being sorted.
What is the purpose of the Floyd-Warshall algorithm?
A Shortest path between two vertices
B Minimum spanning tree
C All-pairs shortest path
D Maximum flow
The Floyd-Warshall algorithm computes the shortest paths between all pairs of vertices in a weighted graph. It considers all possible intermediate vertices and updates the shortest paths iteratively.
What is the time complexity of Heap Sort in the worst case?
A O(n log n)
B O(n^2)
C O(log n)
D O(n)
Heap Sort has a worst-case time complexity of O(n log n). It works by converting the array into a max-heap and repeatedly extracting the largest element, which takes logarithmic time for each element.
Which algorithm is used to find the largest element in a heap?
A Merge Sort
B Extract-Max
C Quick Sort
D Heapify
In a max-heap, the largest element is always at the root. The Extract-Max operation removes the root element and reheapifies the heap to maintain the heap property, ensuring the next largest element is at the root.
Which of these sorting algorithms is considered unstable?
A Merge Sort
B Bubble Sort
C Insertion Sort
D Heap Sort
Heap Sort is considered unstable because it can change the relative order of equal elements. In contrast, algorithms like Merge Sort and Insertion Sort are stable, preserving the relative order of equal elements.
What does Kruskal’s algorithm require to work efficiently?
A A priority queue
B A directed graph
C A sorted edge list
D A hash table
Kruskal’s algorithm works by sorting all edges in increasing order of weight and adding edges to the minimum spanning tree as long as they don’t form a cycle. Sorting the edges is crucial to its efficiency.
What is the primary purpose of the Bellman-Ford algorithm?
A Find shortest path in a graph
B Find minimum spanning tree
C Find the maximum flow
D Sort elements
Bellman-Ford is used to find the shortest path in a graph, even with negative edge weights. Unlike Dijkstra’s algorithm, it can handle graphs with negative edge weights and can detect negative weight cycles.
Which algorithm is best suited for large datasets where the data is not already sorted?
A Quick Sort
B Bubble Sort
C Merge Sort
D Heap Sort
Merge Sort is highly efficient for large datasets, especially when the data is not already sorted. It guarantees O(n log n) time complexity and works well for external sorting, such as sorting data stored on disk.