CCS Data Structures and Algorithms 3 ā Questions and Answers
Question 1: What property distinguishes a max-heap from a min-heap?
- Max-heap stores sorted data; min-heap does not
- Max-heap has the largest element at the root; min-heap has the smallest (Correct answer)
- Max-heap uses more memory than min-heap
- Max-heap supports O(1) search; min-heap does not
Correct answer: Max-heap has the largest element at the root; min-heap has the smallest
In a max-heap the root is always the maximum element, while in a min-heap the root is always the minimum.
Question 2: Which graph representation is most space-efficient for a sparse graph?
- Adjacency matrix
- Adjacency list (Correct answer)
- Edge list stored in a 2D array
- Incidence matrix
Correct answer: Adjacency list
An adjacency list uses space proportional to the number of edges, which is efficient for sparse graphs.
Question 3: What is the purpose of dynamic programming?
- To sort data in linear time
- To avoid recomputing overlapping subproblems by storing results (Correct answer)
- To allocate memory at runtime
- To traverse graphs without a visited set
Correct answer: To avoid recomputing overlapping subproblems by storing results
Dynamic programming stores solutions to overlapping subproblems (memoization or tabulation) to avoid redundant computation.
Question 4: In a doubly linked list, each node contains:
- One pointer to the next node only
- Two pointers: one to the next and one to the previous node (Correct answer)
- A key-value pair and a hash
- A left child and a right child pointer
Correct answer: Two pointers: one to the next and one to the previous node
A doubly linked list node holds data plus pointers to both the next and previous nodes, enabling bidirectional traversal.
Question 5: What is the time complexity of inserting an element at the beginning of a singly linked list?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(nĀ²)
Correct answer: O(1)
Inserting at the head of a linked list only requires updating one pointer, which is O(1).
Question 6: Which algorithm finds the shortest path in a weighted graph with non-negative edges?
- Depth-first search
- Bellman-Ford
- Dijkstra's algorithm (Correct answer)
- Kruskal's algorithm
Correct answer: Dijkstra's algorithm
Dijkstra's algorithm greedily finds shortest paths from a source in graphs with non-negative edge weights.
Question 7: What is a collision in the context of hash tables?
- Two keys map to the same index (Correct answer)
- A key is deleted while still referenced
- The table exceeds its maximum size
- Two values are identical
Correct answer: Two keys map to the same index
A collision occurs when two different keys produce the same hash index, requiring a resolution strategy like chaining or open addressing.
CCS Data Structures and Algorithms 3
What property distinguishes a max-heap from a min-heap?