Level 26 Level 28
Level 27

A2 1.4.2 - Data Structures


47 words 0 ignored

Ready to learn       Ready to review

Ignore words

Check the boxes below to ignore/unignore words, then click save at the bottom. Ignored words will never appear in any learning session.

All None

Ignore?
circular queue
an implementation of a queue that moves the pointers to the front and back of the queue, instead of moving all the items
program
Disadvantage of a Circular Queue: it is more difficult to ...
in advance
Disadvantage of a Circular Queue: it is less flexible than a dynamic data structure if the maximum number of items is not known ...
priority queue
an implementation of a queue where higher priority items are at the front of the queue and lower ones at the back
linked list
a dynamic data structure where each node points to the next one in the list or has a null pointer, meaning items do not have to be in contiguous data locations
call stack
the use of a stack to keep track of the current return address (where control should return to once the subroutine ends)
parameters
... required for a subroutine may be held on a call stack
heap space
storing local variables on the call stack is much more efficient than using dynamic memory allocation, which uses ...
stack frame
make up a call stack, where each one corresponds to a call to a subroutine which has not yet terminated
hashing algorithm
this can be applied to the value in the key field of a record to transform it into an address for the data to be stored at
synonym
a key that gives the same hash as another key when a hashing algorithm is applied
collision
when two record keys hash to the same memory address
hash table
a collection of items stored in memory locations corresponding to their value, allowing for them to be quickly located
folding
a method used in some hashing algorithms where the key is divided into equal parts and the parts are added to compute the hash value
fuller
it is more likely for collisions to occur as the hash table becomes ...
refreshing
the process of finding an empty slot when a collision has occured
dictionary
an abstract data type consisting of associated pairs of items, where each pair consists of a key and a value, implemented using hash tables
graph
a set of vertices/nodes connected by edges/arcs
undirected graph
a graph in which all edges are bidirectional
weighted
the edges in a graph may be ... to represent the cost of going from one vertex to the other
adjacency matrix
an implementation of a graph where each row and column represents a node and the presence of a value in a cell indicates an edge between the nodes
symmetric
an adjacency matrix will be ... when representing an undirected graph
adding an edge
Advantage of Adjacency Matrix: convenient to work with and ... is very simple
memory space
Disadvantage of Adjacency Matrix: ... will be wasted for large graphs with many nodes but few edges
delete nodes
Disadvantage of Adjacency Matrix: it can be more difficult to add or ... using a 2D array
adjacency list
a more-space efficient implementation for sparsely connected graphs, which consists of a list of all the nodes created and each node points to a list of the nodes it is linked to
list of dictionaries
an adjacency list for a weighted graph can be implemented by using a ...
sparsely connected
Advantage of Adjacency List: uses much less memory to represent a ... graph
depth-first traversal
the method of traversing a graph by going as far down one route as possible before backtracking and taking the next route
breadth-first traversal
the method of traversing a graph by firstly visiting all the neighbours of a node and then all the neighbours of the first node visited and all the neighbours of the second node and so on
networks
Application of a Graph: can be used to represent computer ...
between towns
Application of a Graph: can be used to represent roads ...
tasks
Application of a Graph: can be used to represent ... in a project
finite state machine
Application of a Graph: can be used to represent states in a ...
links
Application of a Graph: can be used to represent web pages and their ...
tree
a non-linear data structure made up of connected nodes, that has a root node and child nodes
hierarchical
Application of Trees: manipulating ... data
easier to search
Application of Trees: making information ...
sorted
Application of Trees: manipulating ... lists of data
leaf
a node in a tree that has no children
binary tree
a tree in which each node has a maximum of two children
binary search tree
a binary tree that holds items in such a way that the tree can be searched quickly and easily for an item and it can be traversed in order
pre-order traversal
the method of traversing a tree such that the centre node is returned first, then its left sub-tree, followed by its right sub-tree
in-order traversal
the method of traversing a tree such that the leftmost node is returned first, then its parent, then the right node
post-order traversal
the method of traversing a tree such that a node's left sub-tree is returned first, then its right sub-tree, followed by the node
right pointer
a binary search tree can be implemented using an array of records, where each node consists of a left pointer, the data item and a ...
subtrees
the depth-first traversal algorithms use recursion in order to traverse ...