1.4.2 Data Structures

Question 1

Types

Answer 1

Array: Fixed size, static, holds a single data type
List: No fixed size, dynamic, hold multiple data types
Tuple: Is immutable. Round brackets not square brackets
Record: Made up of fields

Question 2

Linked list

Answer 2

Each item is called a node
Datafield: The actual data
Start Pointer
NextFree Pointer
For each record: Index, Data, Pointer

Question 3

Graphs

Answer 3

Implemented using an adjency matrix or adjacency list

Directed Graph: Only traversed on direction
Undirect Graph: Edges traversed both directions
Weighted graph: Each arc has a cost

Question 4

Stacks

Answer 4

Stack underflow: When item called but is empty
peek() – returns top value

Used to reverse actions

Question 5

Queues

Answer 5

Queue overflow
Head and tail pointer

Circular queues:
Rear point that can loop back to the front

Question 6

Trees

Answer 6

Node
Edge
Root
Child
Parent
Subtree (Section)
Leaf (No children)

Question 7

Binary tree

Answer 7

Each node stored with left and right pointer

Question 8

Hash tables

Answer 8

Array coupled with hash function
Colision: Next available location

Question 9

Pre-order

Answer 9

Root node, left subtree, right subtree
(Pass)

Question 10

In-order

Answer 10

Left, root, right
(Pass under)

Question 11

Post-order

Answer 11

Left, right, root
(pass on right)