Basic Data Structures Flashcards

Which data structure would you use to detect a cycle in a linked list most efficiently?

Answer: Two pointers (Floyd's algorithm)

Floyd's cycle-detection uses a slow and a fast pointer, achieving O(n) time and O(1) space.

What is the space complexity of storing n elements in an array versus a singly linked list?

Answer: Linked list uses more space due to pointer overhead

Each linked list node stores data plus a next pointer, adding constant overhead per element compared to a bare array.

If a stack contains elements (bottom to top): 1, 2, 3, 4 — and you perform two pop operations, what is the new top?

Answer: 2

Popping removes 4 then 3 from the top, leaving 2 as the new top element.

An array-based queue of capacity N uses a circular approach to avoid false overflow. What is the condition for the queue being FULL?

Answer: (rear + 1) % N == front

In a circular queue, (rear + 1) % N == front means the slot just ahead of front is occupied, signaling a full queue.

Which of the following best describes an abstract data type (ADT)?

Answer: A mathematical model defining data and operations without implementation details

An ADT specifies what operations are supported and their behavior, independent of how they are implemented.

In an adjacency list representation of a graph with V vertices and E edges, what is the total space used?

Answer: O(V + E)

The adjacency list stores one list per vertex (O(V)) and each edge appears once (or twice for undirected), totaling O(V + E).

What distinguishes a tree from a general graph?

Answer: Trees are acyclic and connected with exactly V-1 edges for V nodes

A tree is a connected, acyclic undirected graph; with V nodes it always has exactly V-1 edges.