1.4.2 DATA STRUCTURES EXAM
QUESTIONS AND ANSWERS
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)
QUESTIONS AND ANSWERS
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)
