4.2 Fundamentals of Data structures

Question 1

What is a data structure

Answer 1

A way of organising and storing data in a computer so that it can be accessed and modified

Question 2

What is an array? What are its limitations?

Answer 2

An array is a data structure which:
- Can store multiple items
- Of the same data type
- 0-based (indexing begins at 0)
- Can have multiple dimensions (max 3 for A-Level)

Limitations:
- Static, size cannot be changed
- Must store multiple items of the same data type

Question 3

What is a record? What does it do? How is a record created?

Answer 3

A record is a data structure. It is used to group together a collection of related fields about a single object (under a single name)
- Can contain different data types

How is it created?
1. The structure is defined (what fields will it hold?)
2. A variable name is declared for a new record (single instance of the record for an object)
3. Data values are assigned to each field, and can be retrieved or manipulated

It is typically used in conjunction with arrays.

Question 4

What are lists and tuples?

Answer 4

Lists and tuples are Python’s version of arrays, with similar characteristics but slight differences

Tuple:
- Cannot be edited (values changed, added, deleted, or size changed) - IMMUTABLE
- Denoted by () e.g. newTuple = (2,3,4)

List:
- Data structure which can be appended, edited, and items can be added and deleted - MUTUABLE
- Unlike an array, its size can change
- Denoted by {} e.g. newList = {2,3,4,5}

As tuples are immutable, they have a slight performance benefit and uses less memory to manipulate.

Question 5

What is a graph? What are its components and features? What types of graph are there?

Answer 5

A graph is a data structure which is used to model some kind of network.
- Collection of edges (paths) and vertexes (nodes)
- Dynamic data structure
- Very versatile
- When the number of edges is smaller than the number of vertexes, it is a sparse graph
- When the number of edges is greater than the number of vertexes, it is a dense graph
- If there is at least one edge that is unidirectional, it is called a directed graph
- If all edges are bidirectional, it is called an undirected graph

Question 6

What are some ways to represent a graph?

Answer 6

1. Adjacency table
   
   • Shows all the edges in a table using the pairs of nodes (as well as their weight)
     e.g.
     A B C
     A - 4 2
     B 3 - -
     C 2 3 -
2. Adjacency list
   
   • Implemented as a list of dictionaries
   • The key in each dictionary is the node, and the weight of the dictionary is the edge

e.g.
A —> {B:8, C:4}
B —> {A:8, C:9}
C —> {A:4}

Question 7

What is the argument for adjacency tables and lists?

Answer 7

Tables
- Easy to add new edges and read edges off the table
- Easy and quick to work with
- If trying to represent a sparse graph with a table, lots of empty unused space
- Hard to add and delete nodes if using a 2D array to represent the table

Lists
- Uses space efficiently
- Less memeory used up to store a sparse graph