Which of the following graph traversal algorithms uses a queue?
A BFS
B A*
C DFS
D Dijkstra
Breadth-First Search (BFS) uses a queue to explore nodes level by level, starting from the source node. It processes all neighbors at the current depth before moving on to the next level, making it ideal for finding the shortest path in unweighted graphs.
What is the primary advantage of quicksort over merge sort?
A Faster for small arrays
B Stable sorting
C Lower space complexity
D Better worst-case time
Quicksort has a lower space complexity compared to merge sort. While merge sort requires O(n) extra space due to the need for auxiliary arrays, quicksort sorts in-place, only requiring O(log n) additional space for recursion.
Which traversal algorithm is used to find the shortest path in an unweighted graph?
A Dijkstra
B BFS
C Bellman-Ford
D DFS
BFS is used to find the shortest path in an unweighted graph. It explores the graph level by level, ensuring that the first time a node is visited, it is reached via the shortest path.
Which sorting algorithm has the best average-case time complexity?
A Quick Sort
B Heap Sort
C Merge Sort
D Bubble Sort
Quick Sort has an average time complexity of O(n log n), which makes it faster than algorithms like Bubble Sort (O(n²)) and Merge Sort (O(n log n)) due to its in-place sorting mechanism and smaller overhead.
Which search algorithm is used to find the shortest path in a weighted graph with non-negative edges?
A BFS
B DFS
C Dijkstra
D A*
Dijkstra’s algorithm is used for finding the shortest path in a weighted graph where the edges have non-negative weights. It maintains a priority queue to explore the nodes in order of their shortest known distance from the source.
Which of the following is true about a depth-first search (DFS)?
A It never backtracks
B It can get stuck in infinite loops
C It always finds a cycle
D It is faster than BFS
DFS explores a graph by visiting the deepest unvisited node. If not managed properly (i.e. by marking visited nodes), DFS can get stuck in infinite loops, especially in cyclic graphs.
Which sorting algorithm is best suited for sorting linked lists?
A Heap Sort
B Merge Sort
C Quick Sort
D Selection Sort
Merge Sort is particularly efficient for linked lists because it doesn’t require random access to elements. It splits the list into smaller sublists, recursively sorts them, and merges them back together, maintaining O(n log n) time complexity.
Which of the following is not a property of a BFS traversal?
A It visits nodes level by level
B It is used for finding shortest paths in weighted graphs
C It uses a queue
D It can visit nodes in a random order
BFS visits nodes in a level-order fashion, ensuring all nodes at the current depth are explored before moving on. It cannot visit nodes randomly as it follows a strict queue-based order.
Which of the following is a characteristic of the Merge Sort algorithm?
A Time complexity O(n²)
B Recursive
C In-place sorting
D Not stable
Merge Sort is a recursive sorting algorithm. It divides the array into two halves, recursively sorts each half, and then merges the results. Merge Sort has a stable sorting mechanism with O(n log n) time complexity.
Which of the following algorithms is used to detect cycles in a directed graph?
A Bellman-Ford
B DFS
C Dijkstra
D BFS
DFS can be used to detect cycles in a directed graph by keeping track of visited nodes. If a node is revisited during the traversal, a cycle is present in the graph.
Which sorting algorithm is based on the divide-and-conquer principle?
A Merge Sort
B Bubble Sort
C Insertion Sort
D Quick Sort
Merge Sort is a divide-and-conquer algorithm. It recursively divides the input into two halves, sorts each half, and merges the results. This approach ensures efficient sorting with a time complexity of O(n log n).
What is the time complexity of finding the minimum element in a binary heap?
A O(n log n)
B O(n)
C O(1)
D O(log n)
In a binary heap, the minimum element is always at the root (in a min-heap) or the maximum element (in a max-heap). Therefore, finding the minimum element takes constant time, O(1).
Which of the following is true about the Bellman-Ford algorithm?
A It always produces the shortest path
B It can handle graphs with negative weights
C It only works with unweighted graphs
D It is faster than Dijkstra’s algorithm
The Bellman-Ford algorithm is capable of handling graphs with negative edge weights. It works by repeatedly relaxing all edges, ensuring that the shortest path is found even when negative weights are present.
Which of the following is the correct sequence for quicksort’s operations?
A Partition, Sort, Recursion
B Recursion, Sort, Partition
C Sort, Partition, Recursion
D Partition, Recursion, Sort
Quicksort first partitions the array around a pivot, placing elements smaller than the pivot on one side and larger on the other. Then it recursively sorts the subarrays, leading to a fully sorted array.
Which sorting algorithm performs well when the range of data is small?
A Bubble Sort
B Merge Sort
C Counting Sort
D Quick Sort
Counting Sort performs well when the range of the data is small. It counts the frequency of each element and uses this information to place elements directly into their correct positions, offering a time complexity of O(n + k), where k is the range of the input.