1.1 Data structures Flashcards
What is a data structure
a collection or group of related data items
why are data structures useful
collects together basic data types (e.g. integer, real etc.) and allows data to be organised in a convenient, logical manner related to the program being developed.
can be accessed, searched, sorted etc. more quickly than data held in a file as data structures are held in memory
name 2 types of data structure
arrays, records
give an example of data to be stored in a 2 dimensional array
the sales of different products (downwards column) per month (across column)
give an example of data stored in a 3d array
the test scores of different students, per form group
what is a record data structure and where would it be used?
The record data structure allows items of data relating to something to be grouped together into a single record type.
cam be used in e.g. pseudocode
What is a stack data structure
a stack is a LIFO data structure
is a limited access data structure
is used as e.g.
run time stack mechanism (keep track of where it is up to with procedure calls)
undo feature in an application
explain adding an item to a stack
increment the stackpointer (add 1 to) and place the new item in the position indicated by the stackpointer
explain removing an item from a stack
display the item indicated by stack pointer (e.g. pressing undo in a web browser displays the previous page) and the decrement (take 1 from) stackpointer
how could a stack be implemented using an array and variable
the array stores the items in the stack, the variable (e.g. the stack pointer) always points at the last element added to the stack
pseudocode procedure to add data to a stack
Procedure AddToStack
Get Item
IF Stack pointer = limit
Error message “stack full”
ELSE
Stackpointer := Stackpointer + 1
Stack[Stackpointer] := Item
END IF
End Procedure
pseudocode procedure to remove data from stack
Procedure RemoveFromStack
IF Stack pointer = 0
Error “Stack empty”
ELSE
Output stack[Stackpointer]
Stack pointer := Stackpointer –1
END IF
END Proc
what is a queue data structure and how is it implemented
a FIFO data structure (First In First Out)
e.g. queuing up in a shop, processes in a ‘round-robin scheduling policy’
often implemented using an array and two pointers to indicate the start and the end of a queue
explain removing an item from a queue data structure
involves displaying the data in position indicated by start pointer (front of queue) and then incrementing (+1) the start pointer
explain adding an item to a queue data structure
involves incrementing (+1) the end pointer (back of queue) and putting data into that position
what happens when the end pointer goes beyond the end
the queue is circular so if the end pointer goes beyond the end of the queue, it starts again at 1.
draw a diagram to represent the stack data structure, add an item to it, and remove an item
draw a diagram to represent the queue data structure, add an item to it, and remove an item
pseudocode algorithm to add an item to a queue data structure
Procedure AddtoQueue
If Endpointer < MaxSize then
Queue[Endpointer]= newitem
Endpointer = Endpointer + 1
Else
Output “queue is full”
End if
End Procedure
pseudocode algorithm to remove item from queue data structure
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 is a linked list and what does it consist of
a linked list is a dynamic data structure (its size can be increased and decreased as required, unlike an array)
items can be added to a linked list without having to move the existing items to make space
items can be removed from a linked list without having to shift the other items to fill the gap left
consists of:
start pointer which points to the first item in the list, which will have a pointer to the next item and so on.
there is also another linked list of free locations, items that are deleted from the normal linked list are added onto the front of this free list. Items added to the linked list are obtained from the front of the free list.
advantages of a linked list
A linked list is 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.
Items can be removed from a linked list without having to shift the other items to fill in the gap left
disadvantages 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
what is a binary tree data structure and what could it be used for
a type of tree where all nodes can either have 0, 1 or 2 children, each node having a left pointer and right pointer to their children (which could be empty/null)
we could use binary trees 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
-anything ‘greater than’ or after the data is to the right
