1.4.2 Data Structures

Question 1

1.4.2 A)
What is an array
And what are the different types of arrays

Answer 1

An ordered finite set of elements of a single data type.

A 1D array is an linear array always zero indexed

A 2D array can be like a table or spreadsheet you go up and down the toes then across the columns to find a given position

A 3D array can be a visualised as multiple 2D arrays example : print(array[x,y,z]) where x = the array number , y = row , z= column

Question 2

1.4.2 A)
What is a record

Answer 2

A row in a file, made up of values from fields the variable must be declared

Question 3

1.4.2 A)
What is a list

Answer 3

A data structure consisting of ordered items where items can occur more than once. They can contain multiple data types.

Question 4

1.4.2 A)
How to access a list

Answer 4

Similar to 1D array in his they can be access, however values stored non contagiously meaning they don’t need to be next to eachother In memory

Question 5

1.4.2 A)
Operations of a list

Answer 5

IsEmpty()
Append(value)
Remove(value)
Search(value)
Length()
Index(value)
Insert(pos,value)
Pop()
Pop(pos)

Question 6

1.4.2 A)
What is a tuple?

Answer 6

An ordered set of values of any types. It’s immutable which means cannot be changed elements can’t be added or removed once it’s created.
Attempting to add or remove will cause an error

Question 7

1.4.2 B)
What is a stack
What is a stack used for

Answer 7

Last in first out (LIFO) data structure.
Used as a undo / reverse action

Question 8

1.4.2 B)
What are the two types of stacks

Answer 8

Static or dynamic
If max size required is known in advance use static as it’s easier to implement and make more efficient use of memory.

Question 9

1.4.2 B)
How are stacks implemented

Answer 9

Using a pointer which check top of the stack where next piece of data will be inserted

Question 10

1.4.2 B)
What are the operation of a stack

Answer 10

IsEmpty()
Push(value) - adds a new value to end of list need to check list is not full
Peek() - returns top value make sure stack isn’t empty
Pop() same as peek but removed value
Size()
IsFull()

Question 11

1.4.2 B)
What is a queue

Answer 11

First in first out (FIFO) data structure

Question 12

1.4.2 B)
What are queues used for

Answer 12

Printers linear queue consisting of an array

Question 13

1.4.2 B)
How is data added / removed from a queue

Answer 13

Items added to the next available
Space starting from the front. Items are removed from the front. Used two pointers one at front and one at back.

Question 14

1.4.2 B)
What makes linear queues ineffective

Answer 14

As items are removed address cannot be reused in efficient use of space

Question 15

1.4.2 B)
How can queues become more efficient

Answer 15

Circular queues.
When the rear pointer = max size of the array it can be looped around to the front of the array uses space more efficiently but harder to implement
Only works if front of queue is empty

Question 16

1.4.2 B)
Operation for circular queue

Answer 16

EnQueue() - Adds new item to end of queue. Incriminating back pointer by one
DeQueue() - removes item from front of the queue incrementing front pointer by one
IsEmpty ()
IsFull()

Question 17

1.4.2 B)
What is a linked list

Answer 17

Dynamic data structure uses to hold an ordered Sequence. Don’t have to be in contiguous data location. Each item is a node containing data field along side a link or pointer

Question 18

1.4.2 B)
How can linked list be demonstrated

Answer 18

Table with index data and pointer
Data field contains value of actual data
Pointer field contains the address of the next item in the list

Question 19

1.4.2 B)
What other variables do linked list contain

Answer 19

The start or the first item in the list and also next free stores the index of the next available pos

Question 20

1.4.2 B)
How to add a new value to the end of the linked list

Answer 20

1) add the new value to end of linked list and update “next free “ pointer
2) pointer field of previous last value is updated to point to the new value
3) the pointer field of the new value is updated

Question 21

1.4.2 B)
Removing a node from a linked list

Answer 21

Update the pointer so previous pointer is not pointing to empty node

Question 22

1.4.2 B)
Adv of linked list

Answer 22

Values can be easily added or removed by editing pointer

Question 23

1.4.2 B)
Dadv of linked list

Answer 23

1) nodes is not truly removed from list but just ignored this is a waste of memory
2) as items stored in sequence cannot be individually access like an array
3) more space then an array as needs to store pointers asw

Question 24

1.4.2 B)
What is a graph
What are the types of graphs
What can graphs be used for / their adv

Answer 24

A set of vertices connected edges / arcs
Directed - can only be traveled in one direction
Undirected
Weighted - cost attached to each edge

Can be used to find the shortest path and are easy way to understand complex data

Question 25

1.4.2 B) How are computers able to process graphs And there adv

Answer 25

Adjacency matrix ( two way table) Quicker access time easy to add nodes Adjacency list More space eff for large networks

Question 26

1.4.2 B) How can you traverse a graph

Answer 26

Breath first search (BFS) & Depth first search ( DFS)

Question 27

1.4.2 B) What is BFS and how does it work

Answer 27

Is a node based method of finding the shortest path though a graph Uses a queue first in first out method One node is selected visited and marked then adjacent node

Question 28

1.4.2 B) The steps for BFS

Answer 28

1) set root vertex as the current vertex 2) add current vertex to the list of the visited vertex if it’s not on the list 3) for every edge connect to try r vertex if not already visited A) enqeue the linked vertex B) add it too visited list 4) dequeue and set the vertex removed as current 5) repeat from step 2 until queue empty 6) output all visited vertices

Question 29

1.4.2 B) How does DSF work

Answer 29

Uses stacks LIFO method Visited nodes pushed into the stack When no nodes left to visit nodes are popped off the stack

Question 30

1.4.2 B) Steps of BFS

Answer 30

1) step the root node as the current node 2) add the current node to the list of visited node if isn’t already in the list 3) for every edge connected to the node if the connected node is not in the visited list 4) pop stack and set the removed item as current node 5) repeated from 2 until no nodes left and output

Question 31

1.4.2 B) BFS v DFS

Answer 31

BFS Queue finds shortest path of an unweighted graph Good for close solutions Not good for puzzles and problems solving DFS Stack May traverse though more edges Suitable for far solutions and problem solving

Question 32

1.4.2 B) What is a tree Properties of a tree

Answer 32

A connected form of a graph have a root node which is the top node in any tree Node - an item in the tree Edge - connect two nodes together aka branch or arc Root - single node without incoming nodes Sub tree - subsection of tree consisting of a parent and all its children Leaf - node without any children

Question 33

1.4.2 B) What common data structure is used with a tree

Answer 33

Binary tree each node has max of two children used to represent info in binary search. Most commonly using left and right pointers implemented using 2D array

Question 34

1.4.2 B) Method of traversing a binary tree

Answer 34

Pre order In order Post order

Question 35

1.4.2 B) Explain pre order traversal

Answer 35

Follow the order root node > left subtree > right subtree Uses in programming languages where operation written before value “A+B” would be written as “+AB “

Question 36

1.4.2 B) Explain in order traversal

Answer 36

Left subtree > root node > right subtree Useful for traversing in sequential order

Question 37

1.4.2 B) Explain post order traversal

Answer 37

Left subtree > right subtree > root node

Question 38

1.4.2 B) How to add data to a tree

Answer 38

1) check there is a free memory space for a new node if not output an error 2) create a new node and inset data into it 3) if tree empty new node becomes first node 4) if not - follow left or right pointer depending on if it’s > or < current node - u till leaf node is teachers if new node > leaf put new node in its right - if leaf > new nodr put new node in the left

Question 39

1.4.2 B) How to remove an node from a tree

Answer 39

1) start at the root node and set it as the current node 2) while the current node is not the one to be deleted set previous node to the same as current node Follow the pointer to where the node to be deleted is set new node to current If node has no children 3) set left or right pointer of previous node to null. Left or right depends on if greater or less then