Data Structure Flashcards
4.2
What is an array?
An ordered, static set of elements
Can only store 1 data type
1D array is a linear array
How do we create a 1D array?
array[number]= {“values”}
How do we create a 2D array?
array_2d=new array[rows][columns]
How do we create a 3D array?
array_3d=new array[rows][columns][depth]
What is a record?
A row in a file and is made up of fields
How do we create a record in pseudocode?
(record name)=record
(data type)(field name)
…
end record
e.g(string firstname)
What is a list?
A data structure that consists of a number of items where the items can occur more than once
What are features of a list?
List values are stored non contiguously
Can contain elements of more than one data type
How do you create a list in psuedocode?
list (listname)=[“data”…]
What list operation checks if its empty?
(listname).isEmpty()
What list operation adds a new value to the end of the list?
(listname).append(data)
What list operation returns the length of the list
(listname).length()
What list operation returns the position of an item
(listname).index(data)
What list operation inserts a value at a given position
(listname).insert(position,data)
What list operation returns and removes the last value
(listname).pop()
What is a tuple?
An ordered set of values of any type that cant be changed
How do you create a tuple in pseudocode?
tuple1=(data,data…)
When should an array be used?
For a fixed size collection of elements and need random access to elements inside by index
(e.g list of student grades)
When should a record be used?
When should a list be used?
For a dynamic collection of elements that may change in size. They provide flexibility for adding,removing or modifying elements.
(e.g student record in school system)
What is a linked list?
A dynamic data structure that is used to hold an ordered sequence
What are the features of a linked list?
Data doesn’t have to be held in contiguous data locations
Each item is called a node and contains a data field called a pointer
What does the data field contain?
Value of the actual data apart of the list
What does the pointer contain?
Contains address of the next item in the list
List also stores a pointer identifying the next available space
How do you traverse a linked list?
Check if linked list is empty
Start at the node the pointer is pointing to
Output item at current node
Follow pointer to the next node repeating through each node until the end of the linked list
When pointer is null it signals end of linked list has been reached
How do you add a node to a linked list?
Check if there is free memory to insert data into the node
Add new value to the end of the linked list and update ‘nextfree’ pointer
All other pointers are updated
What is a stack?
A last in first out data structure and is often implemented using an array so maximum size is known in advance
What does an isEmpty() stack operation do?
Checks if stack is empty by checking the value of the top pointer
What does a push(value) stack operation do?
Adds a new value to the end of the list
Need to check stack is not full before pushing
What does a peek() stack operation do?
Returns the top value of the stack
First checks stack is not empty by looking at value of the top pointer
What does an pop() stack operation do?
Removes and returns the top value of the stack
First checks stack is not empty by looking at value of top pointer
What does a size() stack operation do?
Returns size of the stack
What does an isFull() stack operation do?
Checks if the stack is full and returns the boolean value, this compares stack size to the top pointer
What does a stack pointer do?
Points the the top of the stack, where next data will be pushed or popped
What happens when data is pushed onto a stack?
Data is pushed to position of the pointer
Once pushed the pointer will increment by 1 to signify top of the stack
What is stack overflow?
Since a stack is a static data structure an attempt to push item onto a full stack is stack overflow
Size cant change
What happens when data is popped from a stack?
Data is popped from the position of the pointer
Once popped the pointer will decrement by 1 to point at the new top of the stack
What is stack underflow?
Since a stack is a static data structure an attempt to pop item onto an empty stack is stack underflow
Size cant change
What is the pseudocode to check if a stack is empty?
function isEmpty
if top == -1 then
return True
else
return false
endif
endfunction
What is the pseudocode to check if a stack is full?
function isFull
if top ==maxSize then
return True
else
return false
endif
endfunction
What is the pseudocode to push an item onto a stack?
procedure push(item)
if isFull() then
print(“Stack is full”)
else
top = top+1
stack(top)=item
endif
endprocedure
What is the pseudocode to pop an item out of a stack?
procedure push(item)
if isEmpty() then
print(“Stack is empty”)
else
top = top-1
return item
endif
endprocedure
Whats the pseudo code to insert item into a linked list?
LONNNGG WRITE IT
procedure insertItem(newItem)
if nextFree == null then
print(“List is full”)
return
endif
temp = nextFree
nextFree = items[nextFree].pointer
items[temp].item = newItem
if start == null or newItem < items[start].item then
items[temp].pointer = start
start = temp
else
p = start
while items[p].pointer ≠ null and newItem ≥ items[items[p].pointer].item
p = items[p].pointer
endwhile
items[temp].pointer = items[p].pointer
items[p].pointer = temp
endif endprocedure
Whats the pseudo code to delete item in a linked list?
LONNNGG WRITE IT
procedure deleteItem(target)
if start == null then
print(“List is empty”)
return
endif
if items[start].item == target then
temp = start
start = items[start].pointer
else
p = start
while items[p].pointer ≠ null and items[items[p].pointer].item ≠ target
p = items[p].pointer
endwhile
if items[p].pointer == null then
print("Item not found")
return
endif
temp = items[p].pointer
items[p].pointer = items[temp].pointer
endif
# Free up space
items[temp].pointer = nextFree
nextFree = temp endprocedure
What is a queue?
A first in first out data structure
Items are added to end of queue and removed from the front
Can be static or dynamic
What are the queue operations to remove and add to a queue?
To add an element to back of queue its - enQueue(item)
To remove an element from front of queue its - deQueue
What is a linear queue?
Data structure that consists of an array
Items are added to next available space in queue starting from front
Items are then removed from front of queue
What is a circular queue?
A static array that has a fixed capacity so you will eventually reach end of queue
What happens when items are deQueued in a circular queue?
Space is freed up at the start of the array
it would take time to move items up to the start of the array to free up space at the end so a circular queue is implamented
it reuses empty slots at the front of the array
Rear pointer wraps around to point to start of array
What is the pseudocode for initialising a queue?
procedure initialise
front=0
rear=-1
size=0
maxSize=(size of array)
end procedure
What is the pseudocode for checking if queue is empty?
function isEmpty()
if size==0 then
return true
else
return false
endif
endfunction
What is the pseudocode for checking if queue is full?
function isFull
if size==maxSize then
return true
else
return false
endif
endfunction
What is the pseudocode for adding an element to a queue?
procedure enqueue(newitem)
if isFull then
print(“Queue Full”)
else
rear=(rear+1) MOD (maxSize)
queue(rear) = newitem
size=size+1
endif
endprocedure
What is the pseudocode for removing an element to a queue?
function dequeue
if isEmpty then
print(“Queue empty”)
else
item=queue(front)
front=(front+1) MOD (maxSize)
size=size-1
endif
return item
end function
What is a graph?
Set of nodes that are connected by pointers
What are the different types of graphs?
Directed-Pointers can only be traversed in one direction
Undirected-Pointers can be traversed in both directions
Weighted-A value is attached to each pointer
What is the data like in an adjacency matrix?
Its symmetric
How does an adjacency matric work to determine presence or absence of an edge
By inspecting the row that represents a node
You need a method to record which row is used for a specific nodes edge data
The data values of the nodes are not stored in the matrix
How does an adjacency matric store data for undirected un weighted graphs?
1 for a pointer between two nodes
0 for no pointer between to nodes
What is a problem with adjacency matrixes?
The larger the graph the more memory that will be wasted
Using static 2D array its harder to delete or add nodes
What is breadth first search?
Graphical traversal algorithm which visits all neighbors of a node before moving onto its neighbors
What is depth first search?
Graph traversal algorithm that uses a pointer based system
What is a tree and its structure?
A connected undirected form of graph with nodes and pointers
A root node at the top with nodes connecting to it called children nodes
Leaf node at the bottom with no children
What are trees used for?
Managing folders
Storing routing tables
Speed up searching
Represent algebraic and Boolean expressions
What is depth first traversal of a binary tree?
Goes left then right nodes
What is breadth first traversal of a binary tree
Begin with root node and move to left node under root and go left to right down the tree
What is the pseudo code for in order traversal
procedure inorderTraverse (P)
if tree[p].left !=-1 then inorderTraverse (treelp].left)
endif
print (tree(p) .data)
if tree(p). right != -1 then inorderTraverse (tree(p] .right)
endif endprocedure
What is the pseudo code for post order traversal?
procedure postorderTraverse (p)
if treel[p].left 1=-1 then
postorderTraverse (tree(p). left)
endif
if tree[p]. right!= -1 then postorderTraverse (tree(p]. right)
endif
print (tree [p) .data)
endprocedure
What is the pseudo code for pre order traversal?
P r o c e d u r e p r e o r d e r T r a v e r s e (p)
p r i n t ( t r e e [ p ] . d a t a )
i f t r e e l p l . l e f t ! = - 1 then
p r e o r d e r T r a v e r s e ( t r e e [ p ] . l e f t )
e n d i f
i f t r e e l p l . r i g h t ! = - 1 t h e n
p r e o r d e r Tr a v e r s e ( t r e e [ p ] . r i g h t )
e n d i f
e n d p r o c e d u r e
What is a hash table?
An associated array coupled with a hash function that takes in data and releases an output
What is a hash function used for?
To map the key to an index in the hash table
Each piece of data is mapped to a unique value using the hash function
What is a collision in a hash table?
When two inputs have the same hash value
How is a collision in a hash table resolved?
Item is placed in the next available location this is called collision resolution
Why are hash tables used?
They provide fast access to data due to having a unique 1-1 relationship with the address at which they are stored
Very fast efficient data searching
How do you work out hash value?
Convert characters to ASCII value
Add them up
Mod the total by how much the table can store
