IT IT Data Structures and Algorithms 2 ā Questions and Answers
Question 1: Which graph traversal algorithm uses a queue and visits all neighbors before going deeper?
- Depth-First Search
- Breadth-First Search (Correct answer)
- Dijkstra's Algorithm
- A* Search
Correct answer: Breadth-First Search
Breadth-First Search (BFS) uses a queue to explore nodes level by level, visiting all neighbors before moving deeper.
Question 2: What is the worst-case time complexity of QuickSort?
- O(n log n)
- O(n)
- O(nĀ²) (Correct answer)
- O(log n)
Correct answer: O(nĀ²)
QuickSort degrades to O(nĀ²) when the pivot consistently produces unbalanced partitions, such as with an already-sorted array.
Question 3: Which data structure is most efficient for implementing a priority queue?
- Array
- Binary Heap (Correct answer)
- Stack
- Doubly Linked List
Correct answer: Binary Heap
A binary heap provides O(log n) insertion and O(log n) deletion of the minimum/maximum, making it ideal for priority queues.
Question 4: What does Big-O notation primarily describe?
- The exact running time of an algorithm
- The upper bound of an algorithm's growth rate (Correct answer)
- The memory usage of an algorithm
- The lower bound of an algorithm's growth rate
Correct answer: The upper bound of an algorithm's growth rate
Big-O notation describes the worst-case upper bound on how an algorithm's runtime or space grows relative to input size.
Question 5: In a graph, what is a spanning tree?
- A tree with the maximum number of edges
- A subgraph that connects all vertices with no cycles (Correct answer)
- A directed path through all nodes
- A tree rooted at the graph's center
Correct answer: A subgraph that connects all vertices with no cycles
A spanning tree is a subgraph that includes all vertices of the original graph and is connected with no cycles.
Question 6: Which algorithm finds the shortest path from a single source to all other vertices in a weighted graph?
- Bellman-Ford
- Kruskal's
- Prim's
- Dijkstra's (Correct answer)
Correct answer: Dijkstra's
Dijkstra's algorithm uses a greedy approach with a priority queue to find the shortest paths from one source vertex.
IT IT Data Structures and Algorithms 2
Which graph traversal algorithm uses a queue and visits all neighbors before going deeper?