1.4.2 Data Structures

Question 1

Array

Answer 1

• a static data structure in which data is stored in continuous, Adjacent memory locations [1]
• can only store one data type [1]
• provides direct access to elements
• are usually zero indexed

Question 2

Record

Answer 2

• is a row in a file and is made up of fields
• is widely used in databases
• can be implemented using OOP in python

Question 3

Tuple

Answer 3

• a static data structure
• An ordered collection of elements that can contain multiple data types
• is immutable - so elements can’t be added or removed once it has been created [1]
• are initialised using regular brackets instead of square ones

Question 4

Static Datastrcute

Answer 4

Size can’t change during processing [1]

Question 5

Dynamic data structure

Answer 5

• size can change during processing [1]
• disadvantage : storage requirements are unknown initially [1]

Question 6

Linked lists

Answer 6

• a dynamic data structure used to hold an ordered sequence [1]
• each item/node consist of a data field and a pointer field [1]
• data field contains the actual data
• pointer field gives the location of the next node/item in the list [1]
• linked list needs to be traversed until desired element is found [1]
• takes longer to search (as more nodes are added) [1]

Question 7

Linked lists + array comparison

Answer 7

• array provides direct access to all elements [1] whereas a linked list needs to be traversed until desired element is found [1]
• contents of an array are stored continuously in memory [1]
• whereas contents of linked list do not have to be in continuous data locations [1]

Question 8

Linked list operations

Answer 8

• adding node
• deleting node
• traversing linked list

Question 9

Linked list traversal

Answer 9

• is used to access each element of the linked list
• first position is indicated by the start pointer [1]
• linked list can be traversed by following each items next pointer until the end of the list is located (null)
• pointer = null means end of list has been reached

Question 10

Linked list : adding node

Answer 10

• advantage: nodes can be added or removed easily by editing the pointers
  1. Allocate memory and create new node containing the data [1]
  2. Change the new node to point to the previous nodes next node [1]
  3. Change the previous nodes next node to point to the new node [1]
• if the new node is added to the start change its pointer to point to the head node
• if added at the end let it point to null

Question 11

Linked list: Removing node

Answer 11

• involves updating nodes to bypass the deleted node
• node is not truly removed but ignored instead which wastes memory
• so to delete a node, change the next pointer of the previous node to bypass the node being deleted and instead point to the next node
• linked list requires more memory than arrays due to storing pointers

Question 12

Stack

Answer 12

• is a LIFO data structure [1]
• items can only be added or removed from the top of the stack
• stacks are used to reverse actions eg back buttons and undo buttons use stacks
• stacks use a pointer which points to the top of the stack
• when initialising stack we set TOP pointer = -1
• thus is stack is empty TOP = -1

Question 13

Stack operations

Answer 13

• push(value)
• pop()
• isEmpty()
• isfull()
• Size()

Question 14

Push(value)

Answer 14

• adds an element to the top of the stack (checks if stack is full first)
• once value is pushed, the top pointer is incremented by 1
• attempting to push an item onto a full stack is called stack overflow

Question 15

Pop()

Answer 15

• removes and returns value at the top of the stack (checks if stack is empty first)
• once popped, the pointer is decremented by 1
• attempting to pop an item from an empty stack is called stack underflow

Question 16

IsEmpty()

Answer 16

• checks if stack is empty
• eg if Top == -1 return true
• or return len(stack) == 0

Question 17

Isfull()

Answer 17

• Checks jf stack is full
• compares stack size to the top pointer
• if len(stack) == Top return true

Question 18

Size()

Answer 18

Returns size of the stack

Question 19

Queues

Answer 19

• a FIFO data structure
• in which items are added at the end of the queue
• and items are removed from the front of the queue
• Consist of a head and tail pointer
• similar to stacks there is also queue overflow and queue underflow

Question 20

Types of queue

Answer 20

• linear queue
• circular queue
• priority queue

Question 21

Queue operations

Answer 21

• Enqueue(value)
• dequeue()
• peek()
• isfull()
• isempty()

Question 22

Enqueue

(initially set value of head and tail pointer = -1 )
(for the first element increment both head and tail pointer to 0)

Answer 22

• adds element to the back of the queue
  1. Check if queue is full
  2. Increment tail pointer and add the new element in the position pointed by the tail
  3. Head pointer stays the same

Question 23

Dequeue
( for dequeuing the last element, reset the values of the head and tail to -1 )

Answer 23

• returns an elements from the front of a queue
  1. Check that queue is not empty
  2. Return item at the front of the queue and then increment the head pointer by 1

Question 24

PeeK()

Answer 24

Returns the value of the item at the front of the queue without removing it from the queue

Question 25

Linear queue

Answer 25

• same as a normal queue + consists of an array
• uses front and rear pointers
• easier to implement
• however it uses space inefficiently as positions from which data has been removed can’t be reused

Question 26

Circular queue

Answer 26

• have a rear Pointer that can loop back to the front of the queue and utilise the empty space at the front (when the end of the queue is reached )
• circular increment can be performed using modulo division with the queue size
• eg. rear= (rear+1) % len(queue)

Question 27

Graphs

Answer 27

• a set of vertices/nodes connected by edges/arcs [1]
• directed graph: can only be traversed in one direction
• undirected graph: edges can be traversed in both directions
• weighted graphs: each edge has a cost attached to it

Question 28

Adjacency matrix

Answer 28

• a 2D array that records the relationships between each node and all the other nodes in the graph
• each of the rows and columns represent a node
• for unweighted graphs :
  
  • 1 is set when an edge exist between 2 nodes
  • 0 is set when there is no edge between 2 nodes

Question 29

Adjacency matrix advantages

Answer 29

• easy to add nodes
• convenient to work with due to quicker access times

Question 30

Adjacency matrix disadvantages

Answer 30

• in the case of a sparse graph with many nodes but not many edges most of the cells will be empty
• the larger the graph, the more memory space will be wasted

Question 31

Adjacency list

Answer 31

• can be implemented as a list of dictionaries with the key in each dictionary being the node and the value being the edge weight
• the adjacency list is a more space efficient way to implement a sparsely connected graph

Question 32

Traversing a graph

Answer 32

Graphs can be traversed using a DFS traversal or BFS traversal

Question 33

DFS (depth first) traversal

Answer 33

• in this traversal we go as far down one route as we can before backtracking and taking the next route.
• is implemented using a stack
• can be pre order, in order, post order

Question 34

Pre order

Answer 34

Root , left , right

Question 35

In order

Answer 35

Left , root, right

Question 36

Post order

Answer 36

Left, right, root

Question 37

BFS (breadth first traversal)

Answer 37

• systematically explores all the neighbour vertices at the current depth before moving onto vertices at the next depth level and so on

Question 38

Graphs applications

Answer 38

• computer networks => nodes = computers, weighted edges = bandwidth between them
• roads between towns with edge weights representing distances
• webpages and linked

Question 39

Tree

Answer 39

• a tree is a connected form of a graph
• has a root node which is the top of the tree so is hierarchical
• has leaf nodes

Question 40

Height of a tree

Answer 40

Number of edges that connect the root node to the leaf node that is furthest away from it

Question 41

Node (trees)

Answer 41

An item in a tree

Question 42

Edge

Answer 42

Connects two nodes together also known as branch/arc

Question 43

Child node

Answer 43

A node with incoming edges

Question 44

Parent node

Answer 44

A node with outgoing edges

Question 45

Subtree

Answer 45

A subsection of a tree consisting of a parent node and all the children of a parent

Question 46

Leaf

Answer 46

A node with no children

Question 47

Tree and graph comparison

Answer 47

• both consists of nodes
• both are connected by edges
• both are dynamic data structures
• tree is unidirectional whereas graph can be bidirectional
• tree will not have cycles whereas graphs can have cycles
• tree will not be weighted whereas edges in a graph can be weighted

Question 48

Tree use case

Answer 48

• managing folder structures
• binary trees are stored in routes to store routing tables
• binary search trees can be built to speed up searching

Question 49

Binary tree

Answer 49

• A generic tree structure where each node has at most two children with no specific ordering.
• the most common way to represent a binary tree is by storing each node data along side a left and right pointer

Question 50

Binary search tree

Answer 50

• A specialized binary tree optimised for searching
• where each node follows the ordering property (left child < node < right child).
• So all nodes from the left subtree are less than the root node
• all nodes from the right subtree are greater than the root node

Question 51

Binary search tree (BST) ADDING data

Answer 51

• create a new node and insert data into it [1]
• if the tree is empty, the new value will become the root node
• if the value is less than the current nodes value, move to the left child
• if the value is greater than the current nodes value, move to the right child
• repeat this process until a vacant spot is reached where the new value can be inserted

Question 52

BST removing data

Answer 52

1. Search for the node containing the value that needs to be removed
2. If the node is found :
   - If the node has no children simply remove it from the tree
   - if the node has one child, replace the node with its child + delete the child
   - if it has two replace the node with either the minimum or maximum value in right or left subtree
   - removed values can be implemented by setting left or right pointers of parent nodes to null

Question 53

Hash tables