Unit 7 - Data Structures

Question 1

What is an Abstract Data Type?

Answer 1

An ADT (Abstract Data Type) is a logical description of how we view the data type and possible operations.

Question 2

What is encapsulation?

Answer 2

Encapsulation is a form of information hiding, a form of abstraction which ADTs use.

Question 3

Give the process of a queue.

Answer 3

Add an item to the rear
Remove an item from the front
Check if the queue is full
Check if the queue is empty

Question 4

What is a hash function?

Answer 4

A hash function is a function used to obtain the unique address of a record of a large data set.

Question 5

What is a collision?

Answer 5

A collision is where the algorithm generates the same address for different keys.

Question 6

Give one problem with hash tables.

Answer 6

One notable issue with hash tables is the increase in collisions as the table fills up.

Question 7

Give the names of hashing algorithms.

Answer 7

• Mid square method

- Folding method

Question 8

What is the mid-square method?

Answer 8

Mid square method is where a number is squared, then a few digits are extracted and the mod function is performed to get an address.

Question 9

What is the folding method?

Answer 9

The folding method is where the a number is divided into pieces of equal sizes, and these segments of the number are added together. The result will be mod by the table size, and the remainder obtained is the address.

Question 10

What is a graph?

Answer 10

A graph is an abstract data structure which represents complex relationships.

Question 11

Describe an undirected graph.

Answer 11

An undirected graph is a graph consisting of nodes being joined together by edges (links), each with a weight (number). But there are no arrows on the edges, hence there is no direction.

Question 12

Describe a directed graph.

Answer 12

A directed graph does show the direction of edges, so links between nodes can be identified. There are no weights on the edges, however.

Question 13

Define a graph.

Answer 13

A graph is a set of vertices and nodes connected by edges. The edges may sometimes have a weight value on them, representing the magnitude of a value.

Question 14

What are the two ways to represent a graph?

Answer 14

• Adjacency matrix

- Adjacency list

Question 15

Define an adjacency matrix.

Answer 15

The adjacency matrix is a square matrix grid representing the nodes and their connections to other nodes, in both weighted and unweighted graphs.

Question 16

What important property does an adjacency matrix have in an undirected graph?

Answer 16

In an undirected graph, the nodes in the adjacenvy matrix are symmetrical.

Question 17

Give an advantage of adjacency matrix.

Answer 17

It is a very convenient method to use when representing a graph, as it is very simple to understand.

Question 18

State a disadvantage of the adjacency matrix.

Answer 18

All the spaces on the matrix won’t be filled up and if there are many empty spaces then this can waste a lot of memory.

Question 19

What is an adjacency list?

Answer 19

An adjacency list is another method to represent a graph, involving a dictionary style structure.

Question 20

Describe the structure of the adjacency list.

Answer 20

In an adjacency list, each node will point to its adjacent nodes.

Question 21

Give some applications of graphs.

Answer 21

• Finite State Machines
• Computer Networks
• Search engine (most notably, Google)