A2 Data Structures

Question 1

Stacks

Answer 1

A stack is a container of objects that are inserted and removed according to the last-in first-out

Question 2

Characteristics of Stacks

Answer 2

It is a limited access data structure - elements can be added and removed from the stack only at the top.
A stack is either empty or it consists of a top and the rest which is a stack. Underflow occurs when an attempt is made to remove from an empty stack. Overflow occurs when an attempt is made to add to a full stack.

Question 3

Queues

Answer 3

A queue data structure operates on the first in first out principle. Data items are added at the end of the queue and removed from the front.

Question 4

Characteristics of queues

Answer 4

enqueue(item) - Add item to the rear of the queue.
dequeue() - Remove and return item from the front.
isEmpty() / isFull() - In a linear queue, empty spaces at the front cannot be reused, so the queue may become “full” even though there are empty cells earlier in the array.

Question 5

Linked Lists

Answer 5

A linked list is a dynamic data structure, as it can grow and shrink in size after it is declared.
Each element is known as a node; the first element is the head node. Each node consists of the data itself and the address/pointer to the next node.
Linked lists do not provide direct or random access to elements, which makes them less efficient when searching.
Linked lists can be traversed sequentially, starting from the head node, and moving through each node until the end is reached.

Question 6

Trees

Answer 6

A tree is a non‑linear data structure used to represent hierarchical relationships. They consist of nodes, which are sometimes called leaves and links between them using pointers, which are called branches or edges.
Trees are used to represent hierarchical data, such as file systems representing folders and subfolders.
Trees are used to model decision-making processes in AI/games.

Question 7

Binary Trees

Answer 7

A binary tree is like a standard rooted data structure consisting of nodes and pointers. With a binary tree, each node can only have zero, one or at most two nodes. Binary trees can be stored as arrays.

Question 8

In order traversal

Answer 8

In-order traversal is applied by visiting the left subtree first, then the root and finally the right subtree.
This method could be used when searching for a file in the file system.

Question 9

Pre-order traversal

Answer 9

Pre-order traversal is applied by visiting the root first, then the left subtree and finally the right subtree.
This method could be used to create a copy of files in the file system.

Question 10

Post-order traversal

Answer 10

Post-order traversal is applied by visiting the left subtree first, then the right subtree and finally the root.
This method could be used to delete all files in the file system.