CCP Data Structures & Abstract Data Types Flashcards

In graph theory, a graph where all edges have a direction is called a:

Answer: Directed graph (digraph)

A directed graph (digraph) has edges with a specific direction, represented by arrows from one vertex to another.

Which traversal visits a binary tree's left subtree, then the root, then the right subtree?

Answer: In-order

In-order traversal (Left → Root → Right) visits nodes in ascending order for a binary search tree.

What is the worst-case time complexity of insertion into a hash table that uses open addressing?

Answer: O(n)

In the worst case (e.g., all keys hash to the same slot), open addressing degrades to O(n) as every slot must be probed.

A circular linked list differs from a standard linked list in that the last node's pointer points to the:

Answer: Head (first) node

In a circular linked list, the tail node's next pointer wraps back to the head, forming a continuous loop.

Which data structure is best suited for implementing breadth-first search (BFS) in a graph?

Answer: Queue

BFS uses a queue to explore vertices level by level, processing each neighbor before moving deeper.

The space complexity of an adjacency list representation for a graph with V vertices and E edges is:

Answer: O(V + E)

An adjacency list stores each vertex once and each edge once (or twice for undirected), giving O(V + E) space.