CCS Data Structures and Algorithms 3

Question 1

What property distinguishes a max-heap from a min-heap?

Accepted Answer

Max-heap has the largest element at the root; min-heap has the smallest

Answer

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?

Accepted Answer

Adjacency list

Answer

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?

Accepted Answer

To avoid recomputing overlapping subproblems by storing results

Answer

Dynamic programming stores solutions to overlapping subproblems (memoization or tabulation) to avoid redundant computation.

Question 4

In a doubly linked list, each node contains:

Accepted Answer

Two pointers: one to the next and one to the previous node

Answer

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?

Accepted Answer

O(1)

Answer

Inserting at the head of a linked list only requires updating one pointer, which is O(1).

(CCS) Certified Coding Specialist Practice Test