Data Structures

Question 1

What is a compound or complex data type?

Answer 1

When existing data types are combined to create a new data type

Question 2

What is a data structure?

Answer 2

An organised collection of data that can be processed more easily

Question 3

What is a static data structure?

Answer 3

A certain amount of memory is reserved for the data structure when it is created

Question 4

What is a dynamic data structure?

Answer 4

Memory efficient data structure as memory is used when needed and only limited to the memory allocation of the program (the heap)

Question 5

What type of data structure is a stack?

Answer 5

A First In Last Out (FILO) data structure

Question 6

What is used to reference the value at the top of the stack?

Answer 6

A pointer variable holding the index of the value

Question 7

What type of data structure is a queue?

Answer 7

A First In First Out (FIFO) data structure

Question 8

How are pointers used in a queue?

Answer 8

There are front and rear pointers that hold the indexes of the front and rear values

Question 9

What is a priority queue?

Answer 9

Adds values at different priority levels in a queue instead of in the order they are added

Question 10

What is the heap?

Answer 10

A large chunk of unallocated RAM that can be used by dynamic data structures

Question 11

What is the purpose of a circular queue?

Answer 11

Solves the problem that occurs when the end of a queue is reached and there empty spaces but data can’t be added

Question 12

How does a dictionary store data?

Answer 12

As key-value pairs

Question 13

What is the main advantage of using keys in data structures such as dictionaries?

Answer 13

They allow direct access which is quicker to access than unordered data

Question 14

How are dictionaries often implemented using?

Answer 14

Hash tables

Question 15

What are buckets in a hash table?

Answer 15

A position in the hash table array

Question 16

What is the load factor in a hash table?

Answer 16

The proportion of buckets occupied, the optimal is 0.75

Question 17

How is the load factor of a hash table calculated?

Answer 17

Number of occupied buckets / total number of buckets

Question 18

What is a hash function?

Answer 18

An algorithm that converts a hash key to a hash value

Question 19

What are the two main methods of avoiding collisions in a hash table?

Answer 19

Linear probing and chaining

Question 20

When is rehashing needed in a hash table?

Answer 20

When performance degrades due to many values being added or deleted

Question 21

What are rainbow tables?

Answer 21

Tables that store pre-hashed values of possible passwords

Question 22

What is a random salt?

Answer 22

A random piece of data added to a password before they are hashed that is stored with the user id

Question 23

What does a graph represent?

Answer 23

Complex, non-linear relationships (edges) between objects (nodes)

Question 24

What are directed graphs?

Answer 24

Graphs with edges represented with arrows to show which direction the nodes can be visited

Question 25

What are weighted graphs?

Answer 25

Where values are associated with edges

Question 26

What is an adjacency matrix (when used to implement a graph)?

Answer 26

A 2D array that has values for whether there is an edge and a weight, it is symetrical if the graph is undirected

Question 27

What is an adjacency list (when used to implement a graph)?

Answer 27

A list of all neighbours for each node which can include other values such as weight

Question 28

What is a tree?

Answer 28

A connected, undirected graph with no cycles

Question 29

What is a rooted tree?

Answer 29

A tree with a specific starting node that is normally represented above all other nodes

Question 30

What is a binary tree?

Answer 30

A rooted tree where every node can only have up to two child nodes

Question 31

What is a binary search tree?

Answer 31

A tree used to optimise searching by placing values lower than the root the left and the higher values to the right

Question 32

What are the three main tree traversals?

Answer 32

Pre-order (root, left, right), in-order (left, root, right), post-order (left, right, root)

Question 33

What are breath-first and depth-first tree traversals?

Answer 33

Breath-first means visiting all nodes of a certain level before their children and depth-first is where an entire branch is visited before moving onto other branches

Question 34

What is Dijkstra's shortest path algorithm?

Answer 34

An algorithm that works out the shortest path between two nodes using a weighted graph

Question 35

How is the cost of a path calculated in Dijkstra's shortest path algorithm?

Answer 35

The cost is calculated by adding the weight of all edges along the shortes route