Data Structures Flashcards
What are the 4 basic data types
Integer
Real
String
Boolean
Define a data structure
A collection or group of related data items
Collects together the basic data types and allows data to be organised in a convenient and logical manner related to the program being developed
Where are data structures held
They are held in memory and therefore the data item is lost when the computer is turned off.
Usually not a problem as it is easy to write a procedure to copy a data structure into a file and then load it back in again when a program starts
Advantage of data structures
Data structures are held in memory it means the data can be accessed, searched, sorted etc. much more quickly than data held in a file
Can relate to specific problems
What is a 1d array
A 1d array is used to represent a list of data
Allows for the efficient processing of the data e.g. sorting, searching as it is a data structure
What is a 2d array
Used to represent a table of data
E.g. record sales figures for 4 sales people for each month of the year
What is a 3d array?
Used to represent tables of data
If a company wanted to record sales figures over a 10 year period a 3d array could be used
Advantage of array
Access elements in an array without any search being required
E.g. print sales(3,5 8) would immediately print the contents of that cell without needing to search through other elements
Disadvantages of array
Static data structures - the size is set and can’t be changed dynamically as the program runs
E.g. an array that might have 1000 names needs to be set to have 1000 elements, even if 800 are currently blank
If a new item of data needs to be inserted into an element in an array, all the elements after it need to be shifted up to make space for it
And vice versa if an element needs to be removed (items shifted down to fill the gap)
All elements in an array need to be of the same type
What does the record data structure allow
Allows items of data relating to something to be grouped together into a single record type
What is a stack
A last in first out data structure (LIFO)
E.g. like a stack of plates, last one that goes in comes out first
Limited access data structure, only the top item can be removed (popped)
Items are added (pushed) on to the top of the stack
A stack pointer always points at the last element added to the stack
A stack can be used as a recursive data structure
Underflow occurs when an attempt is made to pop an empty stack
Overflow occurs when an attempt is made to add to a full stack
Define popped
Removing an item from a stack
Display item indicated by stackpointer and then decrement from stackpointer
Define pushed
Item is added to the top of the stack
Increment the stack pointer and place the value in position indicated by stackpointer
Where is a stack (LIFO) Data structure used
Run time stack mechanism - an OS uses when running a program to keep track or where it is up to when making procedure calls
Back button in a Web browser
Undo feature
How is a stack implemented
Using an array and a variable known as a stack pointer which always points to the last element added to the stack
To add:
Increment stack pointer and place the value in position indicated by stackpointer
To remove:
Decrement stack pointer and place the value in the position indicated by the stack pointer
Why can a stack be considered a recursive data structure
A stack is either empty
Or has a top item and a pointer to a stack (e.g. a stack with an item c points to another stack with an item b which points to another stack and etc.)
What type of data structure is a queue
A first in first out data structure (FIFO)
E.g. queueing in a shop
A queue data structure is circular so if the end pointer goes beyond the last bit, it starts at the beginning again at e.g. 1
How are queues implemented
Using an array and two pointers to indicate the start and the end of the queue
End is the end of the queue where the new item will be added
How do you add data in a queue (FIFO)
Putting data into the end pointer position and incrementing(+1) the End Pointer
How do you remove data in a queue (FIFO)
Removing data involves displaying the data in a position indicated by start pointer and then incrementing(+1) the start pointer
Define linked list
A dynamic data structure, its size can be increased and decreased as required. An array is static and therefore its size is fixed
Items can be added into a linked list without having to move the existing items to make space
When being compared to an array:
Items can be removed from a linked list without having to shift the other items to fill in the gap left
How is a linked list represented
Using 2 arrays for the data and the pointer to the next item in the list, that item will point to the next and so on
There is also another linked list of free locations
Removing an item from a linked list
..
What type of data structures are trees and why is it useful
Non-linear
Useful for storing data that could he hierarchical e.g. car parts, organisation structure
What is a binary tree
A binary tree is a type of tree where all nodes can either have 0,1 or 2 children
I.e. a node with data and pointers left and right or either
What can binary trees be used for
To keep an ordered list for searching using the rule that anything ‘less than’ or before the data in the alphabet is to the left and everything ‘greater than’ or after the data to the right
How to add to a binary tree
Starting at the root node of the tree
Compare the data you want to add to the current node
If the new data is less than the node then follow the left pointer else follow the right pointer
Repeat this until you reach the end of the tree
Update the pointers of the last node to point to the new one
Removing data from a binary tree
Removing data from a binary tree is a little trickier compared to adding an item. The steps you will follow will depend on the type of node being added
These are:
A node with no children
A node with one child
A node with 2 children
What is tree traversal
Traversal is a process to visit all the nodes of a tree and may print their values too. We always start from the root node
We traverse a tree to search or locate a given item or key
There are three ways:
Pre order traversal
In-order traversal
Post-order traversal
Why is tree traversal used
To search or locate given item or key in the tree or to print all the values it contains
Pre order traversal
In this traversal method, the root node is visited first, then left subtree and finally right subtree
In order traversal
In this traversal method, left-subtree is visited first, then the root node and then the right sub-tree
An example of this is searching for a file in the file system
Postorder traversal
In this method, the root node is visited last, hence the name. First we traverse the left subtree, then right subtree then finally root
What is a hash table
Has 2 components
A table where the actual data is stored and a mapping function (hash function/hash algorithm).
The hash function uses the data that is going to be stored to generate the location in the table where it will be stored.
They are a quick way to store, organise and search for data (allowing us to jump to the location of the stored data if we were performing a search)
Used for database indexing, caches, sets
Hash tables - separate chaining
…
How do you get over the issue of not being able to have mixed data types in an array?
Create an array of records
Where is a stack data structure used
Run time stack mechanism-
An Operating system uses it when running a program to keep track of where it is upto when making procedure calls
The back button in a Web browser/undo function in an application
Recursion values
Describe the FIFO data structure
Often implemented using an array and two pointers to indicate the start and end of a queue
What is good about a binary tree if it is balanced
Very quick to find data
This is because the number of items being searched is effectively halved as the search moves down each level of the tree
Describe the term record
A set of data items all related to a single entity
Can include data of different types
A drawback of a 3 dimensional array
More complex to program compared to the others
algorithm to add an item to a stack
If stackPointer < stackMaximum then
stackPointer = stackPointer + 1
stackArray(stackPointer) = dataItem
Else
Display ”Stack is full – your data has not been saved”
algorithm to remove an item from a stack
If stackPointer > 0 then
dataItem = stackArray(stackPointer)
stackPointer = stackPointer – 1
Else
Display ”Stack is empty – no data can be retrieved”
algorithm to remove a person from the queue or identify if the queue is empty
Procedure RemoveFromQueue
If startpointer <> EndPointer then
Output Queue[startpointer]
Queue[startpointer] = null
Startpointer = startpointer + 1
Else
Output “queue is empty”
End if
End procedure
what should happen when an attempt is made to add an item to a full queue
If the queue is full, any attempt to add to it should return an appropriate message or condition
describe a situation where a queue would be used in a computer system
Printer queue, keyboard buffer
why:
In each case, because the natural / desirable processing order is first in first out so the job waiting longest should be printed next
define the term linked list
a set (accept list) of data elements, where each element contains
• the data itself
• a pointer to the next element
Benefits of a linked list
New items can be inserted without rearranging all the other elements
If programmed dynamically uses memory more efficiently
Drawbacks of a linked list
More complex to program than an array
Extra programming required to access the data in the opposite direction
Can only be accessed in a linear manner
Why are data structures useful in computing
They are the best way of organising data related to a real problem
What are the advantages of data structures
Allows for the efficient processing of the data
E.g. sorting and searching
Add item to a queue pseudocode
Procedure AddtoQueue(NewItem)
If EndPointer < MaxSize then
Queue[EndPointer] = NewItem
Endpointer = endpointer + 1
Else
Output “queue is full”
Compare linked lists to 1d arrays
They are both used to hold a list of data but linked list has a few advantages over 1d array:
-linked list is a dynamic data structure (size can be increased/decreased as required. An array is static and therefore its size fixed)
-items can be added to the list without having to remove existing items to make space
-items can be removed from a linked list without having to shift other items to fill the gap left
Linked list uses more memory than an array as it needs to store the address/reference of the next node in addition to the data
How is the free list used in linked lists
Items that are removed from the linked list are added to the front of the free list
Items that are added to the linked list are obtained from the front of the free list
Pseudocode procedure to display all the items in a linked list
Procedure DisplayAll
p = start
While p <> -1
Display data(p)
p = next(p)
End while
End procedure
Pseudocode to search for an item in a linked list
P = start
Found = false
While p <> -1 and found = false
If searchitem = data(p) then
Found = true
Display “Found it”
Else
P = next(p)
End if
End while
If Found = false then
Display “Item not found”
What are nodes with no children called
Leaf nodes
How do you represent data in a binary tree in a table
Using a 3d array
Horizontal column arrays = left, data, right
Vertical column: 1,2,3,4,5 etc.
Pseudocode to search a binary tree
P = root
Found = false
While found= false and p <>-1
If searchitem = data(p) then
Found=true
Display “Found item”
Else if searchitem < data(p) then
P = left(p)
Else
P = right(p)
End if
End while
Why is a binary tree recursive
The traversal algorithm uses itself to traverse the child nodes
Algorithm for pre order traversal
Procedure PreOrderTraverse(root)
Visit the root node
If there is a left subtree then
PreOrdeTraverse(left sub-tree)
If there is a right subtree then
PreOrderTraverse(right sub-tree)
End procedure
Algorithm for in order traversal
Procedure InOrderTraverse(root)
If there is a left sub-tree then
InOrderTraverse(left sub-tree)
Visit the root node (e.g. display it)
If there is a right sub-tree then
InOrderTraverse(right sub-tree)
End Procedure
Algorithm for in order traversal
Procedure InOrderTraverse(root)
If there is a left sub-tree then
InOrderTraverse(left sub-tree)
Visit the root node (
Algorithm for post order traversal
Procedure PostOrderTraversal(root)
if there is a left sub-tree then
PostOrderTraverse(Left sub-tree)
If there is a right sub-tree then
PostOrderTraverse(right sub-tree)
Visit the root node
End procedure
Describe the characteristics of a linked list
Dynamic data structure - can grow or shrink in size after declaration
Each element in the list is known as a node, first element being the head node
Each node consisted of the data itself and the address/reference to the next node
