4.2 Types of Data Structures Flashcards
What is a composite data type?
A data type that can group together multiple values of different types under a single name.
What are the two composite data types?
String, Array
What are abstract data types?
A logical description of how we view the data and possible operations.
3 Abstract data types
List, stack, queue
What are elementary data types
basic building blocks for representing data and used to define variables and specify the kind of values they can store
3 Elementary data types
Integer, real, boolean, char
Do arrays exist in python?
No, have to be imported by a library
Key differences between arrays and lists
Arrays: defined size, data is stored contiguously in memory
Lists: list is free to grow, values are stored in various locations in memory
What are Contiguos elements?
contiguous elements are positioned in a continuous, uninterrupted sequence
What type of data structure is a queue
FIFO (first in first out)
Functions needed for a linear queue
enqueue
dequeue
peek
Check if the queue is empty
Check if the queue is full
What is enqueue and how is it acheived (4)
Adding items to a queue
Check that queue is not full
Add to the value of the rear pointer
Then add the new item to the position indicated by the rear pointer.
What is dequeing and how is it achieved (4)
Removing an item
Return value at the front of the queue and deleter or pop
Move remaining items up the queue one by one
Decrement the rear pointer.
Difference between circular and linear queues
Circular queues do not move items up when an item is dequeued.
What is different with the items in a priority queue
All items have a level of priority
What are static data structures and what is a example
Static data structures are fixed in size
Memory cant be reallocated once the program is running.
Array
What are abstract data structures
can grow or shrink.
Allocates and deallocates memory from the heap
What problem may come with abstract data structures
may cause overflow(exceeding maximum memory limit).
What is a stack
A stack is a last in, first out abstract data type
What is a matrix
An array of tables or values
What are the six methods required in a stack
push(item) - adds item to the top of the stack.
pop() - removes and returns the item on top of the stack.
isFull() - checks if the stack is full
isEmpty() - checks if the stack is empty
peek() - returns the top item without removing it from the stack.
size() - return the number of items on the stack.
What is stack overflow
attempting to push an item onto a stack that is full
what is stack underflow
attempting to pop from a stack that is empty
What is the call stack
data structure that provides the mechanism for passing parameters and return addresses to subroutines.
What is a stack frame
A stack frame contains all the parameters, the return address and the local variables for a single call to a subroutine which has not yet completed.
What is a dictionary
A dictionary is an abstract data type made up of associated pairs each pair has a key and a value.
Why are hash tables used
a hash table will find any record in a dataset almost instantly, no matter how large the data set.
What is a hash table
a data structure that creates a mapping between the keys and values.
What causes a collision in a hash table
when an algorithm generates the same address for different primary keys.
What is the fix for a collision in hash tables
linear probing happens, this is where the item is put in the next free slot in the table following a collision
What is rehashing (3)
process of resizing and reorganizing a hash table when it becomes too full or inefficient.
It involves creating a new, larger hash table
reinserting all existing elements using a new hash function or the same one with a larger table size.
What features must a circular queue have
They must have a front and rear pointer. They must have a size attribute.
the front pointer is simply adjusted when an item is removed from the queue - the data is not deleted.
6 functions/features of a dictionary
Add
Delete
Amend
Return the value associated with a key
Return True or False depending on whether the key is in the dictionary,
Return the length of the dictionary.
Python function to get a list of the key:value pairs of a dictionary named thisdict
x = thisdict.items()
Python function to return the keys of a dictionary
x = thisdict.keys()
How is a new record added to a hash table (3)
Hash table has an algorithm applied to the key value,
the result is the location in the table where the record should be stored.
If location is not empty the use next free location.
What are graphs
Graphs are abstract data structures representing complex relationships between the items of data.
a set of nodes connected by edges
What is a weighted graph
a type of graph where each edge (connection between nodes) has a numerical value associated with it
What is a vertex/node
vertices/nodes can represent any discrete object or entity on a graph
what is a edge/arc
a relationship or connection between two nodes in a graph.
What is the difference between directed and undirected graph
In an undirected graph, edges do not have a direction associated with them.
In a directed graph, each edge has a direction associated with it.
How do adjacency matricies represent a graph
For an undirected graph with
n nodes, the adjacency matrix is a
n×n matrix.
compare the use of adjacency matrices and adjacency lists to represent graphs
Adjacency list appropriate when there are few edges between nodes
when edges rarely change
What is a tree
a connected, undirected graph with no cycles.
What is a rooted tree
a tree in which one nopde/vertex has been designated as the root.
A rooted tree has parent-child relationships between nodes.
How do we create a dictionary in python
my_dict = {key: value, key: value etc}
How do we check for a value in a dictionary
Use the in keyword
if 2 in mydict.values():
print(True)
what are tuples
are lists that cant be changed once created, they are an immutable and static.
what are dynamic data structures
organisations or collections of data in memory that have the flexibility to grow or shrink in size.
what are the advantages and disadvantages of dynamic data structures
P:
makes efficient use of memory because the data structure only uses as much as it needs.
N:
Risk of overflow
if it exceeds its limit.
Harder to program because it needs to keep track of the data structures size and the location of items inside.
What are the advantages and disadvantages of static structures
P:
Memory allocation is fixed, which means there will be no issues with adding and removing items from the data structure.
Easier to program
N:
Data set aside at the start may not be utilised.
Memory can’t be reallocated once the program is running
A data structures is immutable if
The structure/ data cannot be changed during run time
what are the applications of stack
performing depth first searches on graph data structures
keep track of user inputs
used in RPN
What is queue overflow
attempting to enqueue an item to a full queue
whit queue underflow
attempting to dequeuean item from a empty queue
describe the steps involved in adding an item to a stack(3)
check stack full
increment stack pointer
insert data item at new pointer
describe the steps in removing an item from a stack (3)
check for stack underflow
copy output data item indicated by back pointer
decrement the rear pointer
How do we represent a graph using an adjacency list
List all nodes,
Each node points to a list of all the adjacent to nodes to which it is linked
this can be implemented using dictionaries,
graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
}
dictionary keys represent the nodes, values represent connected nodes
What are the advantages and disadvantages of representing a graph using an adjacency matrix
Checking for presence or absence of an edge only requires checking the corresponding element in the matrix O(1)
A sparse graph with nodes but few edges will mean much of the matrix is empty wasting memory
What are the advantages and disadvantages of representing a graph using an adjacency list
(3)
Disadvantages:
Checking for presence or absence of an edge requires traversing the linked list of all corresponding nodes O(k)
Advantages:
more space efficient than a matrix for a sparsely connected graph
uses less memory
What are the applications of graphs
map networks
What is an adjacency matrix
For a graph with
n vertices, the adjacency matrix
A is an n×n matrix where:
A[i][j]=1 if there is an edge from vertex
A[i][j]=0 if there is no edge between them.
What is an adjacency list
n adjacency list is another way to represent a graph, using a collection of lists (or dictionaries) where each node stores a list of its adjacent (connected) nodes.
What is meant by connected in the definition for a tree, which is a connected undirected graph with no cycles
It is always possible to find a path from one node to another
What is meant by undirected in the definition for a tree, which is a connected undirected graph with no cycles
The edges between nodes are bi-directional there is no arrow pointing in one direction
What is meant by no cycles in the definition for a tree, which is a connected undirected graph with no cycles
there is no path in the tree that returns to the start node
What is a binary tree
a rooted tree where each node can only have one, zero or two pointers/edges
each node can have at most two children
What are operations that can be performed on a tree
add node
delete node
binary search return data in node
traversals
searches
What is the difference between a rooted tree and a binary tree
a binary tree is a rooted tree where each node can have at most two child nodes,
rooted tree can have more
what are the characteristics of a good hashing algorithim
be calculated quickly
result in as few collisions as possible
use as little memory as possible
What problems may linear probing cause
prevents other items from being stored in their correct location
can result in clustering
What is meant by clustering in the context of hash tables
when linear probing results in several positions being filled around common collision values
What is an alternative to having to deal with collisions when using hash tables (2 ways)
By using a 2d hash table
allows for more than one item to be placed at the same position known as chaining
OR
Create an second table for collisions known as an overflow table
What are the applications for hash tables
file systems linking a file name to the file path
What are the three opeartions that can be performed on a hash table
Add new item to hash table
Delete
Retrieve
Describe the process of adding an item to a hash table
Calculate position of item using hash function
If empty insert item
if full, either linear probe or check overflow table
Describe the process of removing an item from the hash table
calculate position of item using hashing function
if position contains item, delete
if no check overflow table, increment position until item is discovered or end of overflow table is reached
Uses of dictionaries
Storing and retrieving data efficiently
Implementing other data structures
what is a vector
a series of numbers that represent information such as position or force
what is vector addition known as
translation
what is the convex combination of two vectors defined as
the shaded area between two vectors
What is the formula for the convex combination of vectors
(a*u) + ( Beta * v)
au + betav
where u and v are vectors
a + beta = 1
a and beta must be larger than 0
What is meant by the dot product of two vectors
number formed when multiplying each component of the first vector by the matching component of the second vector
then adding those two numbers together
What are the applications of dot product.
Graphical applications
finding the angle between two vectors
Describe how to find the angle between two vectors uding dot product (4 steps)
- calculate dot product
- calculate length of vectors using pythagoras
- Multiply the lengths
- use formula.
(dot product of vectors a and b) / (lengtha * lengthb) = cosx
What is the formula for cos x of two vectors
(dot product of vectors a and b) / (lengtha * lengthb) = cosx
What is meant by static allocation
Memory is assigned at compile-time and does not change at runtime.
What is meant by Dynamic allocation
Memory is assigned at runtime and can grow or shrink.
