Section 2: Fundamentals of data structures

Question 1

What is an array?

Answer 1

A set of related data items stored under a single identifier

Question 2

What is a “static” data structure?

Answer 2

A method of storing data where the amount of data stored (and memory required to store it) is fixed

Question 3

What is a “dynamic” data structure?

Answer 3

A method of storing data where the amount of data stored(and the memory required to store it) can vary while the program is being run

Question 4

What is meant by a “LIFO” structure?

Answer 4

Last In First Out

Question 5

What is meant by a “FIFO” structure?

Answer 5

First In First Out

Question 6

What type of structure is a “stack”?

Answer 6

LIFO

Question 7

What is a stack?

Answer 7

A structure where the last item of data added is the first to be dealt with when the data is looked at/ referenced

Question 8

What is a stack frame?

Answer 8

When a stack is used to store information about a running program. A pointer is used to identify the start point of the frame

Question 9

What is an interrupt?

Answer 9

A signal sent by a device or program to the processor requesting its attention

Question 10

What is recursion?

Answer 10

When a subroutine calls on itself

Question 11

What type of structure is a “queue”?

Answer 11

FIFO

Question 12

What is a queue?

Answer 12

A structure where the first item of data added is the first item to be looked at when the data is looked at / referenced

Question 13

When are queue structures used?

Answer 13

Peripherals, e.g. keyboard

Question 14

What is meant by a “circular” queue?

Answer 14

A type of queue that can be represented in a circular format, where the front of the queue is joined to the back of the queue.

Question 14

What is meant by a “linear” queue?

Answer 14

A standard queue, the data can be represented as a line. However the maximum size of the queue is fixed in this case

Question 14

What is another word for a “circular queue”?

Answer 14

Circular buffer

Question 15

What is a “priority” queue?

Answer 15

A priority queue is identical to a standard queue apart from how it adds a priority to each item. This allows higher priority items to “skip” the lower priority items in the queue.

Question 16

What is a graph?

Answer 16

A mathematical structure that models the relationship between pairs of objects

Question 17

What is an “arc”?

Answer 17

A join or relationship between 2 nodes, aka an “edge”

Question 18

What are vertex/vertices?

Answer 18

Objects in a graph (aka nodes)

Question 19

What is an edge?

Answer 19

A join or relation between 2 nodesW

Question 20

What is a weighted graph?

Answer 20

A graph where the edges (joins between nodes) have values

Question 21

What is a undirected graph?

Answer 21

A graph with edges that have no defined direction

Question 22

What is a directed graph?

Answer 22

A graph with edges that point in defined directions

Question 23

What is meant by "latency"?

Answer 23

The time delay that occurs when transmitting data between devices

Question 24

What is an adjacency list?

Answer 24

A data structure that stores a list of nodes with their adjacent nodes

Question 25

What is an adjacency matrix?

Answer 25

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

Question 26

What is a node?

Answer 26

An object in a graph - aka a vertex

Question 27

What is a tree?

Answer 27

A data structure similar to a graph, with no loops

Question 28

What is meant by a root?

Answer 28

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

Question 29

What is meant by a parent?

Answer 29

A type of node in a tree where there a further nodes beneath it

Question 30

What is a child?

Answer 30

A node in a tree that has nodes above it in the hierarchy

Question 31

What is a leaf?

Answer 31

A node that doesn't have any other nodes beneath it

Question 32

What is a binary tree?

Answer 32

A tree where each node can have up to 2 child nodes attached to it

Question 33

What is a hash table?

Answer 33

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

Question 34

What is meant by a hashing algorithm?

Answer 34

Code that creates a unique index from given key items of data

Question 35

What is cache?

Answer 35

A high speed temporary area of memory

Question 36

What is a collision in hashing?

Answer 36

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

Question 37

What is clustering in hashing?

Answer 37

When a hashing algorithm produces indices that are not randomly distributed

Question 38

What is meant by index?

Answer 38

The location where values will be stored, calculated from the key

Question 39

What is meant by chaining in hashing?

Answer 39

A technique for generating a unique index when there is a collision by adding the key/value to a list stored at the same index.

Question 40

What is meant by Rehashing?

Answer 40

The process of running a hashing algorithm again when a collision occurs

Question 41

What is an associative array?

Answer 41

A two dimensional data structure containing key/value pairs of data

Question 42

What is meant by dot product?

Answer 42

Multiplying two vectors together to produce a number

Question 43

What is meant by "convex combination"?

Answer 43

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

Question 44

What is meant by vector space?

Answer 44

A collection of elements that can be formed by adding or multiplying vectors together