Aqa Computing A-Level: Fundamentals Of Data Structures 2/2

Front 1

Graph

Back 1

A mathematical structure that models the relationship between pairs of objects.

Front 2

Uses of Graphs

Back 2

Transport Networks, where the stations departure and arrival points are nodes and the routes are the edges.

The internet, where each devices is a vertex and the physical connection is an edge.

Front 3

Latency

Back 3

The time delay that occurs when transmitting data between devices.

Front 4

Adjacency List

Back 4

A data Structure that stores a list of nodes with their adjacent nodes.

Front 5

Adjacency Matrix

Back 5

A data structure set up as a grid that shows whether there is an edge between each pair of nodes.

Front 6

Advantages of an Adjacency List:

Back 6

Good for graphs with fewer edges than nodes (a sparse graph)

Only stores data where there is an adjacency edge so less memory is required.

Front 7

Advantages of an Adjacency Matrix:

Back 7

Good for graphs with more edges than nodes (a dense graph)

Adjacencies can be identified more quickly as every combination is already stored

Front 8

Tree

Back 8

A connected, undirected graph with no cycles.

Front 9

Root

Back 9

The starting node in a rooted tree structure from which all other nodes branch off.

Front 10

Parent

Back 10

A type of node in a tree where there are further nodes below it.

Front 11

Child

Back 11

A node in a tree that has nodes above it.

Front 12

Leaf

Back 12

A node that has no other nodes beneath it.

Front 13

Binary Tree

Back 13

A tree where each node has a maximum of two child nodes attached to it.

Front 14

Hash Table

Back 14

A data structure that stores key/value pairs based on an index calculated from an algorithm.

Front 15

Hashing Algorithm

Back 15

Carried out on the key, which then acts as an index to the specific location of that data item within the table.

Front 16

Uses of hashing algorithms:

Back 16

Used to created indices for databases enabling quick storage and retrieval of data.

Used to generate memory addresses where data will be stored

Calculate a checksum value from a set of data that is going to be transmitted. When the data is received the algorithm is run again to see if the data was corrupted during transmission.

Front 17

Collisions

Back 17

When a hashing algorithm produces the same index for two ore more different keys.

Front 18

Rehashing

Back 18

The hashing algorithm is run again, or an alternative algorithm is run until a unique key is created.

Front 19

Chaining

Back 19

The colliding key/value is added to a list stored at the same index.

Front 20

Dictionary

Back 20

A data structure that maps keys to data.

Front 21

Associative array

Back 21

A two dimensional structure containing key/value pairs of data (for example, a dictionary).

Front 22

Clustering

Back 22

when a hashing algorithm produces indices that are not randomly distributed.

Front 23

Load factor

Back 23

The number of keys divided by the number of slots.

The higher the load factor, the harder it is for the algorithm to produce a unique result

Front 24

Convex Combination

Back 24

A method of multiplying two vectors together that produces a resulting vector within the convex hull.

Front 25

Convex Hull

Back 25

The area confined by two vectors.