1.4.2 Data Structures Flashcards
1.4.2 A)
What is an array
And what are the different types of arrays
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
1.4.2 A)
What is a record
A row in a file, made up of values from fields the variable must be declared
1.4.2 A)
What is a list
A data structure consisting of ordered items where items can occur more than once. They can contain multiple data types.
1.4.2 A)
How to access a list
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
1.4.2 A)
Operations of a list
IsEmpty()
Append(value)
Remove(value)
Search(value)
Length()
Index(value)
Insert(pos,value)
Pop()
Pop(pos)
1.4.2 A)
What is a tuple?
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
1.4.2 B)
What is a stack
What is a stack used for
Last in first out (LIFO) data structure.
Used as a undo / reverse action
1.4.2 B)
What are the two types of stacks
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.
1.4.2 B)
How are stacks implemented
Using a pointer which check top of the stack where next piece of data will be inserted
1.4.2 B)
What are the operation of a stack
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()
1.4.2 B)
What is a queue
First in first out (FIFO) data structure
1.4.2 B)
What are queues used for
Printers linear queue consisting of an array
1.4.2 B)
How is data added / removed from a queue
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.
1.4.2 B)
What makes linear queues ineffective
As items are removed address cannot be reused in efficient use of space
1.4.2 B)
How can queues become more efficient
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
1.4.2 B)
Operation for circular queue
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()
1.4.2 B)
What is a linked list
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
1.4.2 B)
How can linked list be demonstrated
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
1.4.2 B)
What other variables do linked list contain
The start or the first item in the list and also next free stores the index of the next available pos
1.4.2 B)
How to add a new value to the end of the linked list
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
1.4.2 B)
Removing a node from a linked list
Update the pointer so previous pointer is not pointing to empty node
1.4.2 B)
Adv of linked list
Values can be easily added or removed by editing pointer
1.4.2 B)
Dadv of linked list
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
1.4.2 B)
What is a graph
What are the types of graphs
What can graphs be used for / their adv
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
1.4.2 B)
How are computers able to process graphs
And there adv
Adjacency matrix ( two way table)
Quicker access time easy to add nodes
Adjacency list
More space eff for large networks
1.4.2 B)
How can you traverse a graph
Breath first search (BFS) & Depth first search ( DFS)
1.4.2 B)
What is BFS and how does it work
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
1.4.2 B)
The steps for BFS
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
1.4.2 B)
How does DSF work
Uses stacks LIFO method
Visited nodes pushed into the stack
When no nodes left to visit nodes are popped off the stack
1.4.2 B)
Steps of BFS
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
1.4.2 B)
BFS v DFS
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
1.4.2 B)
What is a tree
Properties of a tree
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
1.4.2 B)
What common data structure is used with a tree
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
1.4.2 B)
Method of traversing a binary tree
Pre order
In order
Post order
1.4.2 B)
Explain pre order traversal
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 “
1.4.2 B)
Explain in order traversal
Left subtree > root node > right subtree
Useful for traversing in sequential order
1.4.2 B)
Explain post order traversal
Left subtree > right subtree > root node
1.4.2 B)
How to add data to a tree
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
1.4.2 B)
How to remove an node from a tree
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
