Unit 7 - Data Structures Flashcards
define array
a finite, ordered set of elements of the same type.
what is a 2-dimensional array
a collection of data elements arranged in a grid-like structure with rows and columns
define tuple
an ordered set of values, which could be elements of any type (images, sound files, strings,etc) that is immutable, which means that elements cannot be changed, and you cannot dynamically add elements or delete elements form a tuple.
what’s the difference between static and dynamic data types
dynamic data types - change size when required (lists grow when items are added and shrink when items are removed). it does this with the aid of heap (specific area of memory)
static data types - cannot change size (array)
what is an abstract data type
one that is created by a programmer
- a logical description of how the data is viewed and the operations that can be performed on it
what is an elementary data type
defined within the programming language
what are the four operations with a queue
- enQueue(item)
- deQueue
- isEmpty
- isFull
what is a queue
a queue is a first in first out data structure. new elements can only be added to the end of the queue, and elements may only be retrieved from the front of the queue
applications of queues
- printing from computers (print queue)
- typing on a keyboard
- simulations
what does enQueue(item) do
add a new item to the rear of the queue
what does deQueue() do
remove the front item from the queue
what does isEmpty() for queues do
test to see whether the queue is empty
what does isFull() for queues do
test to see whether queue is full
what is a circular queue
one way of overcoming the limitation of a static data structure by reusing the spaces that have been freed by dequeuing from the front of the array. If you see a MOD and a length function when looking at lists you will know that it is a circular queue.
pseudocode to initialise a circular queue
pseudocode to test for an empty queue
pseudocode to test for a full queue
pseudocode to add an element to the queue
pseudocode to remove an item from the queue
what is a priority queue
it acts like a queue in that items are dequeue by removing them from the font of the queue. however, the logical order of items within the queue is determined by their priority, with the highest priority items at the front of the queue and the lowest priority items at the back.
what is a list
an abstract data type consisting of a number of items in which the same item may occur more than once
what are the main operations on lists
- isEmpty()
- append(item)
- remove(item)
- search(item)
- length()
- index(item)
- insert(pos, item)
- pop()
- pop(pos)
what does isEmpty() on lists do
test for empty list
what does append(item) do
add a new item to list to the end of the list
what does remove(item) do
remove the first occurrence of an item from list
what does search(item) do
search for an item in the list
what does length() do
return the number of items
what does index(item) do
return the position of item
what does insert(pos, item) do
insert a new item at position pos
what does pop() do
remove and return the last item in the list
what does pop(pos) do
remove and return the item at position pos
what is a linked list
a linked list is a dynamic data structure used to hold an ordered sequence
- items which form the sequence are not necessarily held in contiguous data locations
- each item in the list is called a node and contains a data field and a next address field called a link or pointer field
- the data field holds the actual data associated with the list item, and the pointer field contains the next item in the sequence
- the link field indicates that there are no further items by the use of a null pointer
pseudocode the enQueue() list
procedure enqueue(item)
if q.isFull() then
print (“queue full”)
else
q.append(item)
endif
endprocedure
pseudocode for deQueue(item) on lists
procedure dequeue(item)
if q.isEmpty() then
print(“queue empty”)
else
q.pop(0)
endif
endprocedure
pseudocode for isFull() on lists
function isFull()
return(len(q) == maxSize))
endfunction
pseudocode for isEmpty() on lists
isEmpty()
return(len(q) == 0)
endfunction
how to add nodes to a linked list
data is put into the node pointed to by the nextfree pointer
how to delete nodes from a linked list
adjust the nextfree pointer to the position of the deleted node
how to peek ahead in linked lists
examine the data and the pointer in the current node p and the next one function
define stack
a stack is a last in, first out data structure. this means that items are added to the top and removed from the top
applications of stacks
- calculations
- return addresses when subroutines are called
- back/undo button
what type of data structure is a stack
static or dynamic
5 main operations on stacks
- push(item)
- pop()
- peek()
- isEmpty()
- isFull()
what does push(item) do on stacks
adds a new item to the top of the stack
what does pop() do on stack
removed and returns the top item from the stack
what does peek() do on stacks
returns the top item from the shack but does not remove jt
what does isEmpty() do on stacks
tests to see whether the stack is empty, and returns a boolean value
what does isFull() do on stacks
test to see whether the stack is fill, and returns a boolean value
pseudocode for isEmpty() stacks
pseudocode for isFull() stacks
pseudocode for push(item) stacks
pseudocode for pop() function stack
define hash tables
- abstract data type
large data sets can be organised so each record is assigned a unique address. this unique address is calculated using a hashing algorithm or hash function. the algorithm uses some part of the record (e.g. the primary key)) to map the record to a unique destination address. the resulting data structure used to store the data is called a hash table.
what is a collision
happens when an algorithm generates the same address for different primary keys
how to search for an item with hash tables
- apply the hashing algorithm to the key field of the item
- examine the resulting cell in the list
- if the item is there, return the item
- if there is another item in that spot, keep moving until either the item is found or blank cell is encountered, when it is apparent that the item is not in the table
what is the address in a hashing table
key MOD (num slots)
what is rehashing
finding an empty slot when a collision has occurred
• an alternative algorithm is to increment the ‘skip’ value by adding 1,3,5,7 etc. instead of repeatedly incrementing by 1 to find a free space – to do this, the size of the skip value must be such that all slots in the table will eventually be reached
uses of hash tables
- efficient lookup
- dictionary
- graphs
what is the mid-square method for hash tables
- square the item (assume it is numeric)
- extract some portion of the resulting digits
- perform the mod (remainder) step to get an address
what is the folding method for hash tables
- divide the item into equal-size pieces (the last piece may not be of equal size)
- add the pieces together
- perform the mod (remainder) step to get an address
define graph
a set of vertices or nodes connected by edges or arcs.
edges in an undirected graph
bidirectional
edges in a directed graph
one-way
what does it mean if an edge is weighted
there is a cost to from one node to another
what is an adjacency matrix
2-D array can be used to site information about a graph. each of the rows and columns represent a node
adjacency matrix of an undirected graph
symmetric
advantage of a matrix
- an adjacency matrix is convenient to work with
- adding an edge is simple
disadvantage of a matrix
- a sparse graph with not many connections (edges) will leave most of the cells empty wasting a lot of empty storage
what is an adjacency list
an alternative way of representing a graph. a list of nodes is created, and each node points to a list of adjacent nodes
advantage of adjacency list
- it uses storage for the connections that exist, so it is more space efficient
- it is a good way of representing a large sparsely connected graph
how can a weighted graph be represented by a dictionary
a weighted graph can be represented as a dictionary of dictionaries, with each key in the dictionary being a node, and the value, a dictionary of adjacent edges and edge weights
what are the two ways of traversing a graph
1.depth-first
2. breadth-first
what is a depth-first traversal
go as far down one route before backtracking and taking the next riute
what is a breadth-first traversal
visit all the neighbours of a node, and then the neighbours of the first node visited, all the neighbours of the second node and so on, before moving further away from the start node
applications of graphs
- computer networks
- roads between towns
- tasks in a project
- web pages and links
define tree
a tree is a connected data structure with no cycles – there is a unique path from each node to any other node.
differences between trees and graphs
- a graph doesn’t have a route node, whereas a tree does not.
- a graph has cycles, where as a tree does not.
what is a rooted tree
in a rooted tree, one node is identified as the root. every node except the root has one unique parent.
applications of rooted trees
- manipulating hierarchical data
- making information easy to search
- manipulating sorted lists of data
what does a node consist of in a binary rooted tree
- the data (primitive or complex)
- a left pointer to a child
- a right pointer to a child.
define leaf node
node that has no children
define edge
an edge connects two nodes. every node expect the root is connected by exactly one edge from another node
what are three types of traversal
- pre-order
- in-order
- post-order
what is a pre-order traversal
visit the root, then traverse the left sub-tree, then the right sub-tree.
what is pre-order traversal normally used for
a pre-order traversal is used to produce pre-fix or Polish Notation for a mathematical expression
what is an in-order traversal
traverse the left sub-tree, then visit the root, then traverse the right sub-tree (sequential order)
what is a post-order traversal
traverse the left sub-tree, then traverse the right sub-tree, then visit the root.
what is a post-order traversal used for
a post-order traversal is used to produce postfix or Reverse Polish Notation for an expression
pseudocode for pre-order traversal
pseudocode for in-order traversal
pseudocode for post-order traversal
what is the main programming feature of tree traversal algorithms
recursion
use of in-order traversal
binary search tree, to perform an efficient search for any item
