4.2 Data structures Flashcards
1
Q
What is an array?
How are items accessed in an array?
A
- A collection of items with a fixed size
- Arrays use index numbers to access individuals elements of the array
2
Q
What is an abstract data type?
A
A theoretical description of a way of organising a collection of data, with particular features and access restrictions, that is independent of any particular data structure.
3
Q
What is a data structure?
A
The concrete realisation of an abstract data type in code.
4
Q
What is a static data structure?
A
A data structure that reserves a fixed amount of memory, specified by the programmer in advance of its use
5
Q
What is a dynamic data structure?
A
Data structures that have no fixed size. The memory used grows and shrinks as items are added/removed
6
Q
2 advantages of static data structures over dynamic data structures
A
- Data is quicker to access directly, with minimal overhead
- No additional memory is needed to store all of the pointers
7
Q
2 advantages of dynamic data structures
A
- There is no wasted memory
- There is no theoretical limit on the number of items that can be added
8
Q
Queue: FIFO or LIFO?
A
FIFO (First in first out)
9
Q
Queue: Four key operations
A
- Enqueue - adds item to rear of the queue
- Dequeue - removes item and returns item from the front of the queue
- IsEmpty - checks if the queue is empty
- IsFull - checks is the queue is full
10
Q
Describe briefly the data structures and pointers used by a linear queue
A
- Linear queues are implemented with arrays (or lists)
- They use a front and rear pointers to point to:
- front → the next item to dequeue
- rear → last item enqueued
11
Q
Disadvantages of linear queues if you
1. Don’t shuffle down the items
2. If you do
A
- There is a limit on the number of items that can be added and removed (maxSize)
- Implementing a linear queue where you “shuffle” the items down each time an item is dequeued is very processing intensive
12
Q
Key difference of circular queue from linear queue?
A
- Circular queues virtually connect the end to the start of the array
- This overcomes the problem of reusing spaces in the array
13
Q
What happens to the rear pointer when enqueuing an item to a circular queue?
A
rear ← (rear + 1) % maxSize
14
Q
What is a priority queue? How does enqueuing work?
A
- A queue where each element in the queue has a priority
- When new elements are enqueued, they are inserted ahead of those of lower priority and behind elements of equal or greater priority
15
Q
Name an algorithm that can be implemented with a priority queue
A
Dijkstra’s Algorithm
16
Q
Stack: FIFO or LIFO?
A
LIFO (Last in first out)
17
Q
Stack: Five core operations
A
- Push - adding to top of stack
- Pop - removing from top of stack and returning
- Peek - returns top item without removing it
- IsEmpty - checking if stack is empty
- IsFull - checking if stack is full (only relevant when stored in a static structure)
18
Q
Describe implementation of a stack
A
- Using an array or list to store the items
- Initialise a pointer variable that points to the current top item
- The pointer is initialised as -1
- The pointer is incremented if an item is pushed, and vice versa
- The pointer will be -1 if stack is empty.
19
Q
Graph: Static or dynamic?
A
Dynamic, they can grow and shrink in size
20
Q
What is a graph?
A
Graphs are sets of vertices (nodes) and the edges (arcs) that connect them
21
Q
What is a graph with a high ratio of edges to vertices called?
A
Dense
22
Q
What is a graph with a low ratio of edges to vertices called?
A
Sparse
23
Q
What is a weighted graph?
A
A graph that has weights (number values) on each edge
24
Q
What is a connected graph?
A
A graph where there is a path between each pair of vertices
25
Suggest three things that graphs could be used to model
- **Social networking**: the nodes could be individual people. An edge could represent that two people are acquaintances.
- **Transport networks**: the nodes could be towns. An edge could represent that a train line connects two towns.
- **The internet**: the nodes could be routers. An edge could represent that two routers are connected.
26
2 ways to represent graphs
Adjacency matrix and adjacency list
27
How do you represent no edge for a **weighted** graph?
“-” or “∞” (can't use zero)
28
How could an adjacency list be implemented if graph is 1. weighted 2. unweighted?
1. List of dictionaries if weighted
2. List of lists if unweighted
29
Advantage of adjacency matrix
Adding new edges / checking for presence of edges is simple and quick as 2D static arrays can be used
30
2 advantages of adjacency lists
- Adjacency lists are very space efficient, as no memory is needed to store the empty spaces
- It is easy to add / delete nodes
31
Disadvantage of adjacency list
Slow to query *(e.g. to check the presence of an edge)*, as each item in the list must be searched sequentially until the desired edge is found
32
2 disadvantages of adjacency matrices
- If the graph is sparse, then there are lots of empty spaces, which is wasted memory
- It can be hard to add / delete nodes if a 2D static array is used
33
What is a tree?
A connected, undirected graph with no cycles
34
What is a rooted tree? (3*)
- A tree in which one vertex has been designated as the root
- Rooted trees have **parent-child relationships** between adjacent nodes
- The root is the only node with no parent. All other nodes are descendants of the root
35
What is an internal node?
A node in a rooted tree which has a parent and at least one child
36
What is a leaf node?
A node in a rooted tree that has a parent but is not the parent of other nodes (no child nodes)
37
Suggest a use for rooted trees
A game tree, where edges represent moves, and nodes represent all possible positions in the game
38
What is a binary tree?
A **rooted** tree in which each node has at most two child nodes
39
Name a common application of binary trees
Binary search trees
40
What is an ordered binary tree? (3*)
- A type of binary tree where the data items are in a particular order
- Items left of a node have a value less than the node
- Items right of a node have a value greater than the node
41
What is a hash table?
A data structure that creates a mapping between keys and values
42
What is the purpose of a hash table? (2•)
- To provide a way of storing a list of values in which a key is used to locate values in the list **without** searching through all other values
- They are used so that records can be retrieved quickly
43
What does a hash function/algorithm do in a hash table?
Computes the array index for the value to be stored or retrieved
44
What is hashing?
Hashing is the **irreversible** process of converting data of arbitrary length into data of a fixed length.
45
When does a collision occur (hashing)?
When two or more keys hash to the same index
46
When are collisions unavoidable (hashing)?
When the number of possible keys is larger than the number of available spaces
47
What is a dictionary? (2•)
- A collection of key-value pairs in which the value is accessed via the associated key
- There can be no duplicate keys
48
Name an application of dictionaries
Dictionary based compression
49
What is the meaning of the symbol ↦ ?
Maps to
50
What is important about the components of a vector?
That they are all drawn from the same **field** of values, e.g Reals or Rationals
51
4 ways vectors be represented
- A list of values
- A one-dimensional array
- A dictionary (if the vector can be considered to represent a function)
- Visually (using an arrow)
52
How can a vector be represented in code if the vector is viewed as a function?
A dictionary
53
What does vector addition achieve?
Translation
54
What does scalar-vector multiplication achieve?
Scaling
55
What is another name for dot product?
Scalar product
56
What is a convex combination of vectors **u** and **v**?
α**u** + β**v**
such that α , β >= 0
and α + β = 1
57
What is an application of the dot product?
Finding the angle between two vectors
58
In a convex combination of **u** and **v**, what is the significance of α = β = 0.5?
The resultant vector is the **midpoint** of the *position* vectors **u** and **v**
59
Describe the steps involved in adding a record to a hash table
- **Hash algorithm** applied to **key**, which returns the location (often an array index) in table where the record should be stored
- If location is not empty, a **collision** has occurred
-- _Open addressing_ is used (the next free location is used, wrapping round at the end of the array)
-- Or _rehashing_ occurs (starting from scratch with a larger array)
-- Or _chaining_ is used (a pointer to a list is stored at each location a collision has occurred)
60
When might it be appropriate to represent a vector using a dictionary?
If the vector is used to represent a **function**
61
Describe the steps involved in rehashing (2•)
* A larger hash table is created
* Each value in the existing table is inserted into the new table in a position determined by a **new hashing algorithm**
62
Name three methods of collision handling (for a hash table)
* Rehashing
* Chaining
* Open addressing
63
How are collisions resolved with chaining?
A pointer to a list is stored at each location that points to a list of items that have collided at that location
64
How are collisions resolved with open addressing?
The item is stored in the next available location in the hash table (wrapping around at the end)
