BCS Data Structures and Algorithms 2 — Questions and Answers
Question 1: Which traversal of a BST visits nodes in ascending sorted order?
- Preorder
- Postorder
- Inorder (Correct answer)
- Level-order
Correct answer: Inorder
Inorder traversal (left → root → right) of a BST produces nodes in non-decreasing sorted order.
Question 2: What data structure is typically used to implement Breadth-First Search (BFS)?
- Stack
- Queue (Correct answer)
- Heap
- Array
Correct answer: Queue
BFS uses a queue to process nodes level by level in FIFO order.
Question 3: What is the time complexity of inserting an element into a hash table on average?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n log n)
Correct answer: O(1)
Hash table insertion is O(1) on average due to direct address computation via the hash function.
Question 4: A graph with V vertices and E edges represented as an adjacency matrix requires how much space?
- O(V)
- O(E)
- O(V + E)
- O(V²) (Correct answer)
Correct answer: O(V²)
An adjacency matrix stores a V×V boolean matrix, requiring O(V²) space regardless of the number of edges.
Question 5: Which algorithm finds the shortest path in a weighted graph with non-negative edge weights?
- Bellman-Ford
- Floyd-Warshall
- Dijkstra's algorithm (Correct answer)
- Prim's algorithm
Correct answer: Dijkstra's algorithm
Dijkstra's algorithm greedily finds the shortest path from a source to all vertices in graphs with non-negative weights.
Question 6: What is a heap data structure primarily used for?
- Sorting linked lists
- Implementing priority queues (Correct answer)
- Storing key-value pairs
- Balancing binary trees
Correct answer: Implementing priority queues
Heaps efficiently implement priority queues by maintaining the heap property to give O(log n) insert/extract-min operations.
BCS Data Structures and Algorithms 2
Which traversal of a BST visits nodes in ascending sorted order?