Section 7 - Data Structures Flashcards
Define what is meant by the term ‘array’
Finite
Ordered set of elements of the same type
Types: Integer, real, or char
Define what is meant by a ‘two-dimensional array’
Visualised as table
Elements referred to by row and column number
Define what is meant by an ‘n-dimensional array’
Set of elements of the same type
Indexed by n integers
x represents a particular element
Define what is meant by the term ‘tuple’
Ordered set of values
Elements of any type e.g. strings, integers, or real numbers
Immutable - elements cannot be changed, deleted, or added
Where would you store data permanently so that you can read or update it at a future data?
Stored in a file on a disk
Define what is meant by the term ‘records’
A file consists of a number of records
A record contains a number of fields, each holding one data item
Define what is meant by an ‘Abstract data type’
Logical description of how the data is viewed and the operations that can be performed on it.
Created by the programmer rather than defined within the programming language
What type of data structure is a ‘Queue’
First In First Out (FIFO)
Define what is meant by a ‘Queue’
An ordered collection of items which are added at the rear of the queue, and removed from the front.
Give an example of where a queue may be used in the workplace
Output waiting to be printed is stored in a queue on disk.
Several people may send work to be printed at more or less the same time.
Output is printed on a first come first serve basis as soon as the printer is free.
How would you add a new item to the rear of the queue using a queue operation?
enQueue(item)
How would you remove an item from the front of the queue and return it using a queue operation?
deQueue()
How would you test to see if the queue is empty using a queue operation?
isEmpty()
How would you test to see whether the queue was full using a queue operation?
isFull()
Define what is meant by a ‘dynamic data structure’
Collection of data memory
Able to shrink and grow in size, aided by the heap
Define what is meant by ‘The Heap’
Portion of memory from which space is automatically allocated or de-allocated as required
What is a potential drawback of a ‘dynamic data structure’
May cause an overflow, if it exceeds the maximum memory limit
Program may crash
What data structures benefit from the implementation of dynamic data structures?
Queues and Lists
How do Queues benefit other dynamic data structures?
Queues - maximum size of data is not known in advance. Given some arbitrary maximum to avoid causing memory overflow
How do dynamic data structures such as lists benefit other data structures?
Lists - many methods and functions such as append, remove, length, insert, search, and pop may already be written and can be used in the implementation of other data structures such as queue or stack
Define what is meant by a linear queue
Array with a pointer to the front and back of the queue.
Integer holds the size of the array needed, as a variable giving the number of items currently in the queue.
What is a problem of using a linear queue?
As many items are added and deleted, space is created at the front of the queue which cannot be filled making the size of the array smaller and wait times longer for larger queues.
Name one way of overcoming the limitations of a static data structure such as an array.
Implement the queue as a circular queue, the array fills up and the rear pointer points to the last element of the array.
What are the disadvantages of using a circular queue over a dynamic data structure?
Longer programming times
Less flexible if the maximum number of items is not known in advance
Define what is meant by a priority queue
Dequeued by removing items from the front of the queue.
Determined by priority, highest priority at the front, and lowest priority at the back. New items could join the front rather than the rear of the queue.
How would you initialise a circular queue?
procedure initialise
front = 0
rear = -1
size = 0
maxSize = size of array
endprocedure
How would you test for an empty circular queue?
function isEmpty
if size == 0 then
return True
else
return False
endif
endfunction
How would you test if a circular queue was full?
function isFull
if size == maxSize then
return True
else
return False
endif
endfunction
How would you add an element to a circular queue?
procedure enqueue(newItem)
if isFull then
print (“Queue full”)
else
rear = (rear+1) MOD maxSize
q[rear] = newItem
size = size + 1
endif
endprocedure
How would you remove an item from a circular queue?
function dequeue
if isEmpty then
print (“Queue empty”)
else
item = q[front]
front = (front+1) MOD maxSize
size = size - 1
endif
return item
endfunction
Define what is meant by the term ‘list’
Abstract data type consisting of a number of items in which the same item may occur more than once
How do you add a new item to a list?
append(item)
How do you remove an item from a list?
remove(item)
How do you search for an item in a list?
search(item)
How do you return the number of items in a list?
length()
How do you return the position of an item in a list?
index(item)
How do you insert a new item at a certain position in a list?
insert(pos, item)
How do you remove and return the last item in a list?
pop()
How do you remove and return an item at a certain position in a list?
pop(pos)
When might you use an array over a list?
The programming language does not support the list data type and the maximum number of data items is small, and known in advance
