Fundamentals of data structures

topic two on paper one aqa a level computer science

how is data stored/ organised on a computer

as a series of files that contain records that contain fields

what type of data structures are queues

a fifo data structure

what are the three types of queues

linear, circular and priority

what is a linear queue

a queue where items are added to the end and removed from the front

what is a circular queue

a fixed capacity queue where the position of front and back pointers change depending on when items are added or removed to the queue

what is a priority queue

essentially two linear queues, where one of the two queues is the priority queue, and items will only be removed from the ‘normal’ queue if the priority queue is empty

how does adding to a queue work?

increase the back pointer by one and add the new item to the position it now specifies, this changes slightly for circular and priority

how does removing from a linear or priority queue work?

obtain item from the front pointer and increment accordingly

how does removing from a circular queue work?

remove item at front pointer and move front pointer along (this may not always be (+1) since if front pointer reaches position 8 and the next position is 0 it will become position 0.

how to know If a queue is empty

if the front pointer is equal to the back pointer

how to know if a linear or priority queue is full

if the back pointer is equal to the massive - 1

how to determine If a circular queue is full?

if the back pointer + 1, mod the size = 0

what type of data structures are stacks

a FILO data structure

what does pop, peek and push do in terms of stacks?

pop - removes the top value of the stack, peek views the top value without removal, push adds a new value onto the top of the stack

how to determine if a stack is full?

use isFull

what type of data structure are graphs

an abstract data structure

what does abstract data structure mean

makes use of other data structures to make a better designed way of storing data

what doe graphs consist of

nodes and edges, with weighted or unweighted edges that can be directed or undirected

what are the two ways graphs can be represented

as an adjacency list or adjacency matrix,

what is an adjacency matrix

a table in which a 1 (or the weight of that particular edge) is used to indicate two nodes are connected, and zero or infinity shows a lack of connection

what is an adjacency list

where the node, followed by the nodes it is connected to and their respected weights are stored as a list

what is the advantage of an adjacency list as opposed to an adjacency matrix

can use up less memory as only edges are stored, whereas this is not the case for an adjacency list

what is the advantage of an adjacency matrix

can be easier to query as not all nodes have to be sorted through whereas a list has to be stored sequentially

what is a tree

a connected undirected graph with no cycles

what is a binary tree

a tree where the maximum number of child nodes is two

what is a rooted tree

where the parent node is called the root, the nodes, stemming off of the the parent node are called child nodes, and child nodes with no nodes stemming off of them are called leaf nodes

what is a hash table

a table that stores key pair values, where the input is the key and the resulting hash is the value

what is a hashing algorithm

an algorithm that takes an input and returns a hash value that cannot be reversed

what is an example of a use of hashing algorithms

in passwords so that they cannot be retrieved

what is a collsiion in terms of a hash table

when two inputs result in the same hash, resulting in data being overwritten as they would be stored in the same locatio

what is the solution to a collision in hashing

rehashing

how does rehashing work?

by finding an available position in the table to store this hash according to an agreed procedure

what is an example of a rehashing procedure

moving along the table to find the next available location

what is a dictionary

a collection of key pair values, where the value is accessed by its key

what is dictionary based compression

where frequently used words are stored in a dictionary, and displayed as a series of keys.

how are vectors represented (definition version)

as a list of numbers, a function, or a geometric point in space

what are vectors used for

to reprisent spacial information and movement

how can vectors be represented?

as a list of numbers, as a dictionary, as a function or as a one dimensional array

what are the two methods of vector representation that are referred t as 4 vector over R

• lists

• dictionaries

what is translation in terms of vectors

vector addition

what is scalar vector multiplication

changing the magnitude of a vector based on a scalar value

what is convex combination in terms of vectors

where two vectors a and b are presented in the way ax + by, where both a and b are non zero values that add to make 1

what is convex combination used for

to produce the linear combination of two vectors

what is dot/ scalar product, in terms of vectors

multiplying the contents of each vector and adding them together, this is used to determine the angle between them

what is a static data structure

a fixed size data structure where data is stored sequentially

what is a dynamic data structure

a data structure that grows or shrinks to accommodate demands

what are the disadvantages static data structures

overflow error, potentially wasted memory allocation

what are the disadvantages of dynamic data structures

could potentially require more memory as position where data is stored needs to also be stored