OCR A Level CS 1.4.2 Data Structures

What is an array?

An ordered, finite set of elements of a single type.

How are array elements accessed?

Using zero-based indexing (e.g., array[0] for the first element).

What is a two-dimensional array?

A table-like structure with rows and columns (e.g., array[1][2]).

What is a three-dimensional array?

A multi-layered structure that requires three indices (e.g., array[0][1][2]).

What is a record?

A data structure consisting of multiple fields of different types.

Where are records commonly used?

In databases, where each row represents a record.

How is a record different from an array?

Arrays store only one data type, while records store multiple types.

What is a list?

An ordered collection of elements where duplicates are allowed.

How do lists differ from arrays?

Lists are dynamic (can grow/shrink) and can store multiple data types.

What is a tuple?

A fixed, immutable ordered collection of elements.

How do you access tuple elements?

Using zero-based indexing, like an array.

What is a linked list?

A dynamic data structure where elements (nodes) are linked by pointers.

What are the two main types of linked lists?

Singly linked list (each node points to the next) and doubly linked list (nodes point both ways).

What are the advantages of linked lists?

✅ Efficient insertion/deletion
✅ No fixed size

What are the disadvantages of linked lists?

❌ More memory needed for pointers
❌ Slower search times compared to arrays

What is a graph?

A set of nodes (vertices) connected by edges.

What are the two types of graphs?

• Directed Graph → Edges have a direction.

• Undirected Graph → Edges can be traversed both ways.

What is a weighted graph?

A graph where edges have numerical weights (e.g., distances).

What are the two ways to represent graphs?

• Adjacency Matrix → 2D array storing connections.

• Adjacency List → Each node stores a list of connected nodes.

What is a stack?

A LIFO (Last In, First Out) data structure.

What are common stack operations?

✅ push(value) → Adds an item to the stack.
✅ pop() → Removes the top item.
✅ peek() → Returns the top item without removing it.
✅ isEmpty() → Checks if the stack is empty.

Where are stacks used?

• Undo/redo functionality

• Backtracking (e.g., browser history)

• Expression evaluation (e.g., postfix notation)

What is a queue?

A FIFO (First In, First Out) data structure.

What are the types of queues?

• Linear queue → Elements removed from the front.

• Circular queue → Reuses empty slots efficiently.

What are common queue operations?

✅ enqueue(value) → Adds an item to the back.
✅ dequeue() → Removes an item from the front.
✅ isEmpty() → Checks if the queue is empty.
✅ isFull() → Checks if the queue is full.

Where are queues used?

• Printer job scheduling

• Operating system task scheduling

• Handling requests on a web server

What is a tree?

A hierarchical data structure with nodes connected by edges.

What are important tree components?

✅ Root → The top node.
✅ Parent/Child → Nodes connected hierarchically.
✅ Leaf → A node with no children.

What is a binary search tree (BST)?

A tree where the left child is smaller, and the right child is larger than the parent.

What are the three tree traversal methods?

• Pre-order → Root → Left → Right

• In-order → Left → Root → Right

• Post-order → Left → Right → Root

What is a hash table?

A data structure that uses a hash function to map keys to values.

What is a collision in hashing?

When two keys map to the same index.

How are collisions resolved?

• Linear probing → Find the next available space.

• Chaining → Store multiple values at the same index using a list.

Where are hash tables used?

• Databases (fast lookups)

• Password storage (hashing passwords)

• Indexing data efficiently