OCR A Level Computer Science: Data Structures || A+
Guaranteed.
What is an array and its features? correct answers A variable that can contain more than 1 data
item, but all homogenous (the same) data type
- index (relative to address where array starts) used to access array contents, so ordered
collection of items
- contiguous section of memory allocated to store that data
Features:
- static data structure - size/length of structure cannot change at run-time
- mutable - structure/data can be changed at run-time
What is a one-dimensional (1D) array? correct answers Array where elements are stored linearly
and accessed individually/through 1 index
What is a two-dimensional (2D) array? correct answers Array where elements stored similar to a
table, accessed through 2 indexes (like rows and columns)
- e.g. Countries[0][0] = "Angola"
What is a three dimensional (3D) array? correct answers Array where elements stored/accessed
through 3 indexes (visually similar to a cube)
- e.g. Countries[2,2,2] = "USA"
What is a list and its features? correct answers Variable that can contain more than 1 data item,
and heterogenous (differing) data types
- splits up data and stored in varying chunks of memory locations (non-contiguous),
ordered/connected through pointers
Features:
- Mutable - structure/data can be changed at run-time
- Dynamic - structure size can change at run-time
What is a record data structure? correct answers A collection of related fields (variables) linked
to a single entity
- each field in record can be a different data type (i.e. records can have heterogenous data types)
How do you construct a record data structure? correct answers 1) Define record structure - what
fields will be in record?
2) Declare a variable/array to be used with record structure (e.g. Car1 = (record structure) TCar)
3) Assign and retrieve data from the variable inside record structure
What is a tuple and its features? correct answers Similar to an array - variable that can contain
more than 1 data item and referenced by an index (so ordered collection), but immutable + can
store heterogenous data types
, Features:
- Static - size/length of structure cannot change at run-time
- Immutable - structure/data it contains cannot be changed at run-time
What are the key features of a stack data structure? correct answers - Linear data structure - all
data stored in order added
- Last In First Out (LIFO) data structure - last item to be added to stack at the top of it, and are
first ones to be removed from it
- has a stack pointer that indicates the node/item at the top of it
- "push" = adding to stack, "pop" = removing from stack
- "peeking" = viewing the item at the top of the stack without removing it from the stack
What is stack overflow/underflow? correct answers Stack overflow - attempting to push an item
onto a full stack
Stack underflow - attempting to pop an item off of an empty stack
How are stacks implemented? correct answers Using a linked lists/array, but can use OOP
What are some examples of the uses of stacks? correct answers Used by processors to track the
flow of programs
- when subroutine called, PC stores instruction it has to return to once subroutine completed onto
stack
Performing depth-first searches on graph data structures
Keeping track of user inputs for undo operations
Backtracking algorithms
Evaluating mathematical expressions without brackets
What are the key features of a queue data structure? correct answers - Linear data structure - all
data stored in order added
- FIFO data structure - first item added to queue first one to be removed
- "enqueued" = adding to queue, "dequeue" = removing from queue
- can peek at front of queue like stacks can
- Has both a back/tail pointer (always points to last item in queue) and a front/head pointer
(always points to first item in queue)
- Can have priority queue where important items jump to front spaces in queue
What is queue overflow/underflow? correct answers Queue overflow - attempting to enqueue an
item onto a full stack
Queue underflow - attempting to dequeue an item off of an empty stack
How can queues be implemented? correct answers Using an array or OOP
- implementing with array can cause problems - front + back pointers move in same direction as
are added/removed and gradually move away from front of array, so it runs out of space
What are circular queues and how can they be useful? correct answers A type of queue where the
back pointer cycles back to the front of an array when it reaches the end of it
Guaranteed.
What is an array and its features? correct answers A variable that can contain more than 1 data
item, but all homogenous (the same) data type
- index (relative to address where array starts) used to access array contents, so ordered
collection of items
- contiguous section of memory allocated to store that data
Features:
- static data structure - size/length of structure cannot change at run-time
- mutable - structure/data can be changed at run-time
What is a one-dimensional (1D) array? correct answers Array where elements are stored linearly
and accessed individually/through 1 index
What is a two-dimensional (2D) array? correct answers Array where elements stored similar to a
table, accessed through 2 indexes (like rows and columns)
- e.g. Countries[0][0] = "Angola"
What is a three dimensional (3D) array? correct answers Array where elements stored/accessed
through 3 indexes (visually similar to a cube)
- e.g. Countries[2,2,2] = "USA"
What is a list and its features? correct answers Variable that can contain more than 1 data item,
and heterogenous (differing) data types
- splits up data and stored in varying chunks of memory locations (non-contiguous),
ordered/connected through pointers
Features:
- Mutable - structure/data can be changed at run-time
- Dynamic - structure size can change at run-time
What is a record data structure? correct answers A collection of related fields (variables) linked
to a single entity
- each field in record can be a different data type (i.e. records can have heterogenous data types)
How do you construct a record data structure? correct answers 1) Define record structure - what
fields will be in record?
2) Declare a variable/array to be used with record structure (e.g. Car1 = (record structure) TCar)
3) Assign and retrieve data from the variable inside record structure
What is a tuple and its features? correct answers Similar to an array - variable that can contain
more than 1 data item and referenced by an index (so ordered collection), but immutable + can
store heterogenous data types
, Features:
- Static - size/length of structure cannot change at run-time
- Immutable - structure/data it contains cannot be changed at run-time
What are the key features of a stack data structure? correct answers - Linear data structure - all
data stored in order added
- Last In First Out (LIFO) data structure - last item to be added to stack at the top of it, and are
first ones to be removed from it
- has a stack pointer that indicates the node/item at the top of it
- "push" = adding to stack, "pop" = removing from stack
- "peeking" = viewing the item at the top of the stack without removing it from the stack
What is stack overflow/underflow? correct answers Stack overflow - attempting to push an item
onto a full stack
Stack underflow - attempting to pop an item off of an empty stack
How are stacks implemented? correct answers Using a linked lists/array, but can use OOP
What are some examples of the uses of stacks? correct answers Used by processors to track the
flow of programs
- when subroutine called, PC stores instruction it has to return to once subroutine completed onto
stack
Performing depth-first searches on graph data structures
Keeping track of user inputs for undo operations
Backtracking algorithms
Evaluating mathematical expressions without brackets
What are the key features of a queue data structure? correct answers - Linear data structure - all
data stored in order added
- FIFO data structure - first item added to queue first one to be removed
- "enqueued" = adding to queue, "dequeue" = removing from queue
- can peek at front of queue like stacks can
- Has both a back/tail pointer (always points to last item in queue) and a front/head pointer
(always points to first item in queue)
- Can have priority queue where important items jump to front spaces in queue
What is queue overflow/underflow? correct answers Queue overflow - attempting to enqueue an
item onto a full stack
Queue underflow - attempting to dequeue an item off of an empty stack
How can queues be implemented? correct answers Using an array or OOP
- implementing with array can cause problems - front + back pointers move in same direction as
are added/removed and gradually move away from front of array, so it runs out of space
What are circular queues and how can they be useful? correct answers A type of queue where the
back pointer cycles back to the front of an array when it reaches the end of it
