1.4.2 Data Structures

Question 1

Array?

Answer 1

A data structure that holds several elements of the same data type

Question 2

How and why are arrays used in computer hardware?

Answer 2

Contents of arrays are stored contiguously on the RAM
Each position is directly accessible
Values are mutable

Question 3

Mutable?

Answer 3

Can be changed while the program is running

Question 4

2D arrays?

Answer 4

Can be visualized as a table
Navigate down the rows then across the columns

Question 5

3D arrays?

Answer 5

Can be visualized as a multipage spreadsheet / multiple 2D arrays

Question 6

Pros of using arrays?

Answer 6

Arrays can be declared via a single identifier

Arrays can be processed efficiently, using iteration techniques

Question 7

Record?

Answer 7

A data structure that consists of a fixed number of variables, called fields.

Question 8

List?

Answer 8

An abstract data structure that describes a linear collection of data items in an order.

Question 9

What are the 4 list operations?

Answer 9

Create
Add
Delete
Traverse

Question 10

How do you implement lists using static arrays?

Answer 10

Create an array where the max number of elements in the list is fixed.

Populate the array sequentially, using a linear search to find gaps

An index pointer is used to point to the next occupied element in the list

Question 11

Cons of static list implementation?

Answer 11

If items are constantly added/removed there will be gaps

Gaps are found using linear search, which’s slow and inefficient, especially with larger lists.

Question 12

What does it mean for a list to be dynamic?

Answer 12

The size of the list can change at any time

Question 13

How do you implement a list dynamically?

Answer 13

Using a linked list

Question 14

What is a linked list?

Answer 14

A dynamic data structure that acts like a chain, consisting of a sequence of nodes, where each node contains data and a pointer to the next node in the sequence

Question 15

Node?

Answer 15

An element in a linked list that stores:

Data relating to the element
A pointer to the next node

Question 16

The head pointer?

Answer 16

Indicates the first element in the linked list

This has a null value when the list is empty

Question 17

Tail pointer?

Answer 17

Indicates the last element in the linked list

Always points to a null value- marking end of list

Question 18

Tuple?

Answer 18

An immutable, ordered sequence of elements

Question 19

Use of tuples?

Answer 19

To group together a set of disparate items, that are to be passed into a method.

Results from SQL queries are received as tuples

Question 20

Stack?

Answer 20

An abstract LIFO data structure that holds an ordered, linear sequence of items

Question 21

Main stack operations?

Answer 21

push(data) = adds element to the top of the stack

pop() = removes element from the top of the stack

peek() = returns a copy of the element on the top of the stack

is_empty() = checks if stack is empty

is_full() = checks if stack is full, if it’s in a static structure

Question 22

Queue?

Answer 22

First in first out data structure that holds an ordered linear sequence of items

Meaning items are added to the end and removed from the front

Question 23

What’s a pointer?

Answer 23

An object that stores a memory address

Question 24

Queue overflow?

Answer 24

Enqueuing to a full queue

Question 25

queue underflow?

Answer 25

dequeuing from an empty queue

Question 26

Main queue operations?

Answer 26

enqueue(data) = adds element to the back of the queue dequeue() = removes element from the front of the queue peek() = returns a copy of the element at the front of the queue without removing it from the queue is_empty() = checks if queue is empty is_full() = checks if queue is full

Question 27

Static queues?

Answer 27

Queues with a fixed size and contents that cannot change at run time

Question 28

Types of static queues?

Answer 28

Linear queue Circular queue

Question 29

Linear queues?

Answer 29

Consists of an array Items are added to the next available space starting from the front of the queue, where the rear pointer begins and then the rear pointer moves to the next index As items are removed from the front, the front pointer moves to the next item

Question 30

Circular queues?

Answer 30

Freed spaces from dequeued items are reused- efficient memory usage The last index connects to the first forming a circle When an item is enqueued the REAR pointer moves to its position When an item is dequeued the FRONT pointer moves to the position of the next item at the front

Question 31

Dynamic Queues?

Answer 31

Queues that can automatically resize their memory allocation based on the number of elements they hold The queue has no fixed size

Question 32

Type of dynamic queue?

Answer 32

Priority queue

Question 33

Priority queue?

Answer 33

Each item has a priority associated with it The queue has no fixed size

Question 34

Hash table?

Answer 34

An associative array, which's used with a hash function

Question 35

Hash function?

Answer 35

Maps the hash key to an index in the hash table- taking in data and releasing an output

Question 36

Collision / synonym?

Answer 36

When 2 inputs produce the same hashed value These are impossible to avoid ,but a good hashing algorithm should have a low probability of collisions occurring

Question 37

Linear probing?

Answer 37

A collision resolution, where the data that has caused a collision is typically placed in the next available index/ location Probing can either occur sequentially or via use of an interval, until and empty bucket is found

Question 38

Retrieving data after probing?

Answer 38

Hash the key to generate the index value Examine the indexed position to see if the key matches that of the data you're looking for If there's no match, check each location that follows at the appropriate interval, until a match or an empty bucket is found If you reach an empty bucket, without finding a matching key, then the data is not in the table

Question 39

Cons of linear probing?

Answer 39

Reduces the efficiency of using a hash table for searching

Question 40

Pros of linear probing?

Answer 40

Resolves collisions generated by hashing algorithms

Question 41

Graph?

Answer 41

A set of nodes that are connected by edges / pointers.

Question 42

Graph characteristics?

Answer 42

Directed- edges can only be traversed in one direction Undirected- edges can be traversed bidirectionally Weighted- A value is attached to each edge (if no edge exists, the infinity symbol becomes its value in an adjacency matrix / list) Unweighted- Each edge has a value of 1, if no edge exists its value becomes 0 in an adjacency matrix / list

Question 43

Adjacency matrix?

Answer 43

A 2d array that records the relationship between each node and all other nodes in the graph

Question 44

Adjacency list?

Answer 44

Records the existence of an edge between a node and each of its neighbours.

Question 45

Dictionary?

Answer 45

An associative array that stores a collection of unique keys, each with a corresponding value Stores the node to be visited and the weight of the connecting edge as key-value pairs (for graphs)

Question 46

Breadth-first search?

Answer 46

Method of graph traversal Systematically visits all neighbours of a given node before moving on to tho neighbours of the next node Goes from left to right

Question 47

Depth- first search?

Answer 47

Use an edge based system, traversing the left most path first Uses a stack to push each visited node on, and then pop them when there are no connected nodes left to visit

Question 48

Tree?

Answer 48

Connect, undirected forms of graphs, containing a root node and connecting nodes in parent-child relationships

Question 49

Tree height?

Answer 49

The number of edges that connect the root node to the FURTHEST leaf node

Question 50

Features of trees?

Answer 50

Branches = edges Root node = top node Leaves = endpoints / nodes with zero children One parent can have multiple children

Question 51

Uses of trees?

Answer 51

Managing folder structures

Question 52

Uses of binary trees?

Answer 52

Used to store routing tables Used to speed up searching for data Can represent algebraic expressions simply

Question 53

Binary trees?

Answer 53

A rooted tree where every node has a maximum of 2 child nodes And the tree is ordered based on whether a node is greater than or less than the parent

Question 54

Recursion?

Answer 54

When a function calls on itself to execute a task

Question 55

Pre-order traversal

Answer 55

Visit the root-traverse the left subtree-traverse the right (Start bottom left, touch the left of the node) Repeat every time a new node is traversed

Question 56

In-order traversal?

Answer 56

Traverse the left subtree-Visit the root node- traverse the right subtree (Start bottom left, touch the bottom of the node) Repeat every time a new node is traversed

Question 57

Post-order traversal?

Answer 57

Traverse the left subtree-traverse the right- visit the root node (Start bottom left, touch the right of the node) Repeat every time a new node is traversed

Question 58

Adding to a binary tree?

Answer 58

If tree is empty, new value becomes the root If value is less than the current node, move to left child If value is greater than the current node, move to the right child Repeat until a vacant spot is reached to insert the new value Make sure the tree maintains its structure

Question 59

How to remove a leaf node from a binary tree?

Answer 59

directly delete it

Question 60

How to remove a node with only one child from a binary tree?

Answer 60

copy the value of the child in place of the parent node and delete the empty node

Question 61

How to remove a node with two children from a binary tree?

Answer 61

replace the node with its minimum child

Question 62

Recursion?

Answer 62

A programming technique where a function calls itself to execute a task Using self reference to breakdown complicated problems until it reaches the base case

Question 63

Base case?

Answer 63

The condition of a recursive method that returns a value without any further recursive calls

Question 64

Stopping base?

Answer 64

A condition that must be reachable after a finite number of times

Question 65

Recursive algorithm features?

Answer 65

the function must call itself It has a base case It has a stopping base

Question 66

How to develop a stopping condition?

Answer 66

Consider the problem being solved Identify the easiest scenario where the function can provide a direct result- define this as the base case

Question 67

Pros of recursion vs iteration

Answer 67

Can be expressed in a more concise way Simple- don’t have to focus on maintainability

Question 68

Cons of recursion vs iteration

Answer 68

Worse performance- repeat method calls are memory intensive, causing slower execution More difficult to track the program state during debugging Limited application

Question 69

Why is a proper base case needed?

Answer 69

To avoid stack overflow errors- which cause program crashes Without a stopping condition, the function will call itself indefinitely- which will use up excessive memory The program may malfunction