1.4.2 Data structures - Nathan Flashcards
Define the term ‘array’
An array is a data structure that holds a number of elements of the same data type
Where does array indexing start?
Array indexes start at ‘0’. (at least, in most programming languages such as Python)
ADDITIONAL EXPLANATION:
So in the following array:
[“toast”, “eggs”, “ketchup”]
The ‘0th’ element is “toast”, the ‘1st’ element is “eggs” and the ‘2nd’ element is “ketchup”
How are the contents of an array stored in memory?
The contents of arrays are stored contiguously in memory (meaning one after another). This means that the position of each element of the array can be computer from the array’s base address.
Can the contents of an array be changed while the program is running?
The contents of an array are mutable - so they can be changed while the program is running
What’s the difference between a one dimensional array and a two dimensional one?
One dimensional array: an array containing data types such as integers, strings, etc
Two dimensional array: an array containing arrays: e.g:
my2dArray = [[1, 65, 3, 2],
[62, 7, 1, 6],
[6, 3, 76, 2]]
Where the first element of this array is, [1, 65, 3, 2]
What is a record?
A record is a data structure containing a fixed number of variables, called fields. Each field has an identifier (a name) and a data type. Each field can have a different data type.
PSEUDOCODE EXAMPLE:
PlayerRecord = RECORD
player_number: Integer
first_name: String
last_name: String
date_of_birth: Date
position: String
injured: Boolean
ENDRECORD
What is a list?
A list is an abstract data type. It describes a linear collection of data items in an order.
What operations can be done on a list?
create - create a new list
add - add a new element to the list
delete - delete an element from the list
traverse - visit the elements in the list one at a time
What is a tuple?
A tuple is an ordered sequence of of immutable elements (meaning the elements can’t be changed while the program is running).
Do elements in a tuple all have to be the same data type?
No, the elements of a tuple can all be different data types - e.g a mix of integers and strings
What is a linked list?
A linked list is a dynamic data structure - where each node points to the next one, forming a sequence with a start and end.
Why is it important that a linked list is dynamic?
Because a linked list is dynamic, it’s size can be changed at runtime.
What does a node in a linked list contain?
Nodes in a linked list contain the data relating to the element, and a pointer to the next node.
What is a graph?
A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects. They can be undirected, or directed (contain arrows).
What is a stack?
A stack is an abstract data type that holds an ordered, linear sequence of items. It is LIFO (last-in-first-out), similar to a stack of plates.
What are the main operations of a stack?
Push() - add element to top of stack
Pop() - remove element from top of stack
Peek() - return copy of element on top of stack (without removing it)
is_empty() - check whether the stack is empty
is_full() - check whether stack is at maximum capacity (if stored in a static (fixed-size) structure)
Name an application of a stack
One application of a stack is maintaining an ‘undo’ list
What is a queue
A queue is an abstract data type that holds an ordered, linear sequence of items. It is FIFO (first-in-first-out), similar to a queue of people at a cafe.
What are the main operations of a stack?
enqueue(data) - add element to queue
dequeue() - return an element from front of queue & remove it
is_empty() - check whether the stack is empty
is_full() - check whether stack is at maximum capacity (if the size of the queue is constrained)
What are some applications of a queue
Queues can be used for queuing up print tasks, or for simulations (e.g traffic or shopping simulations)
What is a tree?
A tree is a type of graph that’s undirected, and doesn’t contain cycles
What’s a binary tree?
A binary tree is a tree where each node has at most 2 children
What are some applications of trees?
- Syntax trees in compilers
- Used to represent boolean expressions to simplify them
What is a hash table?
A hash table is a type of data structure in which information is stored in an easy-to-retrieve and efficient manner, using key-value pairs
What is hashing
Hashing is the process of transforming any given key or a string of characters into another value
What is a data structure
A data structure is a collection of data that is organised to allow efficient processing
What’s a static data structure?
A static data structure reserves memory for a set amount of data
What’s a dynamic data structure?
A dynamic data structure is a memory efficient data structure with a capacity that isn’t fixed
What’s a dictionary?
A dictionary is an abstract data type that defines an unordered collection of data as a set of key-value pairs
How do you create a dictionary in Python?
results = {“Detra”: 17,
“Nova”: 84,
“Charlie”: 22,
“Hwa”: 75,
“Roxann”: 92,
“Elsa”: 29}
