1.4.2 Data Structures Flashcards
What is an array?
An ordered, finite set of elements of a single type
What is meant by a 1D array?
A linear array
What is meant by a 2D array?
Visualised as a table/spreadsheet
What is meant by a 3D array?
Visualised as a multi-page spreadsheet
What is a record?
A row in a database
Made up of fields
What is a list?
A finite, ordered set of elements
Items can occur more than once
How are lists initialised?
With square brackets
What is a tuple?
An ordered set of values of any data type
How are tuples initialised?
With regular brackets
Are static data structures mutable or immutable?
Immutable
Are dynamic data structures mutable or immutable?
Mutable
What does immutable mean?
Size of a structure is defined at run-time and cannot change
What does mutable mean?
Size of a structure is defined at run-time and is able to change
Which data structures are static?
Arrays
Stacks
Queues
Trees
Which data structures are dynamic?
Lists
Linked lists
Trees
Hash tables
What is a linked list?
Holds an ordered sequence
Describe how linked lists are stored.
Items do not have to be in contiguous data locations
Each node contains a data field & a link or pointer field
What is the data field of a node?
Actual data associated with list
What is the pointer field of a node?
Address of the next item in list
What is a graph?
Set of vertices/nodes connected by edges/arcs
What is a directed graph?
Edges can only be traversed in one direction
What is an undirected graph?
Edges can be traversed in both directions
What is a weighted graph?
Each edge has a cost attached
How are graphs implemented?
Adjacency matrix or adjaceny list
Give 2 advantages of using an adjacency matrix.
Convenient to work with
Easy to add nodes
Give an advantage of using an adjacency list.
Space efficient for large sparse networks
What is a stack?
A Last In First Out data structure
Can be implemented as static or dynamic
What are stacks used for?
Reversing actions
What is meant by Last In First Out?
Items can only be added to/removed from the top
What is a queue?
First In First Out data structure
What are queues used for?
Printers, keyboards & simulators
What is meant by First In First Out?
Items are added to the end and are removed from the front
What is a linear queue?
Items are added into the next avaiable space, starting from the front
What are 3 features of a linear queue?
Items are removed from front of the queue
Uses two pointers, front/back
Uses space inefficiently as positions cannot be reused once data has been removed
What is a circular queue?
Can loop back to the front of the queue and use empty space at front
What is a disadvantage of a circular queue?
Harder to implement
What is a tree?
A connected graph with root & child nodes
What is a node?
Item in a tree
What is an edge?
Connects two nodes together
Also called branch/arc
What is a root?
Node with no incoming nodes
What is a child?
Node with incoming edges
What is a parent?
Node with outgoing edges
What is a subtree?
Section of a tree including a parent and its children
What is a leaf?
Node with no children
What is a binary tree?
A type of tree where each node has a maximum of two children
What is a hash table?
An array coupled with a hash function
What is pre-order traversal?
Follows root node, left subtree, right subtree
What is in-order traversal?
Follows left subtree, root node, rightsubtree
What is post-order traversal?
Follows left subtree, right subtree, root node
What is the function of isEmpty( ) with a list?
Checks if the list is empty
What is the function of append(value) with a list?
Adds a new value to the end of the list
What is the function of remove(value) with a list?
Removes the value the first time it occurs in the list
What is the function of search(value) with a list?
Searches for a value in a list
What is the function of length( ) with a list?
Returns the length of a list
What is the function of index(value) with a list?
Returns the position of the item
What is the function of insert(position, value) with a list?
Inserts a value at a given position
What is the function of pop( ) with a list?
Returns & removes the last item in the list
What is the function of pop(position) with a list?
Returns & removes the item at the given position
What is the function of enQueue(value) with a queue?
Adds a new item to the end of the queue
What is the function of deQueue( ) with a queue?
Removes the item from the front of the queue
What is the function of isEmpty( ) with a queue?
Checks if the queue is empty
What is the function of isFull( ) with a queue?
Checks if the queue is full
Describe how a new value is added to a linked list.
Add the new value to the end of the linked list
Update the “NextFree” pointer
The pointer field of the value to come before the new value is updated to the position of the new value
The pointer field of the new value is updated to the position of the value to come after the new value
Describe how a value is removed from a linked list.
Update the pointer field of the value before the word to be removed to the value stored in the pointer field of the word to be removed
What is the function of isEmpty( ) with a stack?
Checks if the stack is empty
What is the function of push(value) with a stack?
Adds a new value to the end of a list
What is the function of peek( ) with a stack?
Returns the top value from the stack
What is the function of pop( ) with a stack?
Removes & returns the top value of the stack
What is the function of size( ) with a stack?
Returns the size of the stack
What is the function of isFull( ) with a stack?
Checks if the stack if full and returns a Boolean value
