Studied by 2 people
[ 1.4.2 ]
what is an array?
an ordered, finite set of elements of a single type
what is a one-dimensional array?
a linear array
what is a two-dimensional array?
it can be visualised as a table/spreadsheet
when searching an array, first go down the rows and then across the columns
what is a three-dimensional array?
it can be visualised as a multi-page spreadsheet
an element is represented by: myArray[x][y][z]
x = array number, y = row number, z = column number
what is a list?
a data structure that consists of a number of ordered items
items can occur more than once
data is stored in non-contiguous locations
can contain items of different data types
what is the function of the list operation isEmpty() ?
checks if the list is empty
what is the function of the list operation append(value) ?
adds a new value to the end of the list
what is the function of the list operation remove(value) ?
removes the value the first time it occurs in the list
what is the function of the list operation search(value) ?
searches for a value in the list
what is the function of the list operation length() ?
returns the length of the list
what is the function of the list operation index(value) ?
returns the position of the item
what is the function of the list operation insert(position, value) ?
inserts a value at a given position
what is the function of the list operation pop() ?
returns and removes the last item in the list
what is the function of the list operation pop(position) ?
returns and removes the item at the given position
what is a record?
more commonly referred to as a row in a file
a record is made up of fields, and is widely used in databases
each field in a record can be identified by recordName.fieldName
when a record is created, the program must declare the data type for each field
what is a tuple?
an ordered set of values of any data type
immutable and static, meaning it cannot be changed
initialised with regular brackets rather than square brackets
what is a queue?
a first in first out (FIFO) data structure
items are added to the end and are removed from the front of the queue
uses two pointers (head and tail)
used in printers, keyboards and simulators
what is a linear queue?
items are added into the next available space, starting from the front
items are removed from the front of the queue
uses two pointers: pointing to the front/back of the queue
uses space inefficiently, as positions from which data has been removed cannot be reused
what is a circular queue?
a queue that uses a rear pointer
it loops back to the front of the queue and utilises empty space at the front, if it’s available
harder to implement that a linear queue
what is the function of the queue operation enQueue(value) ?
adds a new item to the end of the queue
what is the function of the queue operation deQueue() ?
removes and returns the item from the front of the queue
what is the function of the queue operation isEmpty() ?
checks if the queue is empty
what is the function of the queue operation isFull() ?
checks if the queue is full
what is a linked list?
a dynamic data structure used to hold an ordered sequence
items do not have to be in contiguous data locations
each item is called a node, and contains a data field and a link (pointer field)
a linked list must also store a start index/pointer, to identify the beginning of the list
what is held in the data field of an item in a linked list?
contains the actual data associated with the list
what is held in the pointer field of an item in a linked list?
contains the address of the next item in the list
steps to traverse a linked list.
go to the first position, indicated by the start pointer
from the first position, read the next pointer value
follow this pointer to the next value, and continue until you reach the desired item
what is a stack?
a last in first out (LIFO) data structure
items can only be popped/pushed from the top of the stack
used to reverse actions, (eg. back buttons/undo buttons)
can be implemented as a static or dynamic structure
uses one pointer (head pointer)
what is a tree?
a connected graph, with a root and child nodes
what is an edge?
an edge connects two nodes together (also called a branch/arc)
what is a node?
an item in a tree/graph
what is a root?
a node with no incoming edges
what is a child node?
a node with incoming edges
what is a parent node?
a node with outgoing edges
what is a subtree?
a part of a tree consisting of a parent and children
what is a leaf?
a node with no children
what are the two ways to traverse a tree?
trees can be traversed by a depth-first search (DFS) or a breadth-first search (BFS)
what is a graph?
a set of vertices/nodes connected by edges/arcs
implemented using an adjacency matrix or an adjacency list
what is a directed graph?
a graph where edges are assigned a direction
what is a undirected graph?
a graph where edges can be traversed in both directions
what is a weighted graph?
a graph where each arc has a cost attached to it
what is a hash table?
a data structure which holds key-value pairs
they are used in situations where a lot of data needs to be stored with constant access times
e.g in caches and databases
a good hashing algorithm should…
be calculated quickly
have a low rate of collisions
use as little memory as possible
what is a hashing function?
a function applied to an item to determine a hash value (a unique index in the hash table)
what is a hashing collision and how are they handled?
collisions occur if two keys produce the same hash value
in this situation the item is usually placed in the next available location (open addressing)
to find the item later, the hashing function delivers a start position, from which a linear search can be applied (linear probing)
what is a binary search tree?
a type of tree where each node has a maximum of two child nodes
stores information in a way that is easy to search through
commonly represented by storing each node with a left pointer and a right pointer
what are the three types of depth-first search?
pre-order
in-order
post-order
Note
Flashcard