B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 5 — Questions and Answers
Question 1: Which algorithm finds the minimum spanning tree of a graph by always adding the globally cheapest edge that doesn't form a cycle?
- Prim's algorithm
- Dijkstra's algorithm
- Kruskal's algorithm (Correct answer)
- Bellman-Ford algorithm
Correct answer: Kruskal's algorithm
Kruskal's algorithm sorts edges by weight and greedily adds the smallest safe edge using a Union-Find structure.
Question 2: What abstract data type is used internally by Dijkstra's shortest-path algorithm for efficiently selecting the next vertex to process?
- Stack
- Queue
- Min-priority queue (Correct answer)
- Hash table
Correct answer: Min-priority queue
Dijkstra's algorithm uses a min-priority queue to always extract the unvisited vertex with the smallest tentative distance.
Question 3: What is amortized time complexity?
- The time complexity in the absolute worst case
- The average cost per operation over a sequence of operations (Correct answer)
- The time complexity assuming uniform input distribution
- The space-time tradeoff factor
Correct answer: The average cost per operation over a sequence of operations
Amortized analysis averages the cost over a sequence of operations, smoothing out occasional expensive operations.
Question 4: In a circular linked list, what distinguishes it from a standard singly linked list?
- Nodes store two pointers instead of one
- The last node points back to the first node (Correct answer)
- Elements are stored in sorted order
- Memory is allocated on the stack
Correct answer: The last node points back to the first node
In a circular linked list, the tail node's next pointer points back to the head, forming a cycle.
Question 5: Which data structure is used to implement function call management in most programming languages?
- Queue
- Stack (Correct answer)
- Heap
- Graph
Correct answer: Stack
The call stack uses LIFO ordering so that the most recently called function is the first to return.
Question 6: What is the space complexity of an adjacency matrix representation for a graph with V vertices?
- O(V + E)
- O(E)
- O(V²) (Correct answer)
- O(V log V)
Correct answer: O(V²)
An adjacency matrix allocates a V×V matrix regardless of the number of edges, requiring O(V²) space.
Question 7: Which of the following best describes a disjoint set (Union-Find) data structure?
- A tree that balances itself after each insertion
- A structure that tracks connected components and supports efficient union and find operations (Correct answer)
- A hash table with open addressing
- A queue that processes elements by priority
Correct answer: A structure that tracks connected components and supports efficient union and find operations
Union-Find efficiently tracks which elements belong to the same set and merges sets with near-O(1) amortized operations.
B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 5
Which algorithm finds the minimum spanning tree of a graph by always adding the globally cheapest edge that doesn't form a cycle?