Data Structures Flashcards
What is a compound or complex data type?
When existing data types are combined to create a new data type
What is a data structure?
An organised collection of data that can be processed more easily
What is a static data structure?
A certain amount of memory is reserved for the data structure when it is created
What is a dynamic data structure?
Memory efficient data structure as memory is used when needed and only limited to the memory allocation of the program (the heap)
What type of data structure is a stack?
A First In Last Out (FILO) data structure
What is used to reference the value at the top of the stack?
A pointer variable holding the index of the value
What type of data structure is a queue?
A First In First Out (FIFO) data structure
How are pointers used in a queue?
There are front and rear pointers that hold the indexes of the front and rear values
What is a priority queue?
Adds values at different priority levels in a queue instead of in the order they are added
What is the heap?
A large chunk of unallocated RAM that can be used by dynamic data structures
What is the purpose of a circular queue?
Solves the problem that occurs when the end of a queue is reached and there empty spaces but data can’t be added
How does a dictionary store data?
As key-value pairs
What is the main advantage of using keys in data structures such as dictionaries?
They allow direct access which is quicker to access than unordered data
How are dictionaries often implemented using?
Hash tables
What are buckets in a hash table?
A position in the hash table array
What is the load factor in a hash table?
The proportion of buckets occupied, the optimal is 0.75
How is the load factor of a hash table calculated?
Number of occupied buckets / total number of buckets
What is a hash function?
An algorithm that converts a hash key to a hash value
What are the two main methods of avoiding collisions in a hash table?
Linear probing and chaining
When is rehashing needed in a hash table?
When performance degrades due to many values being added or deleted
What are rainbow tables?
Tables that store pre-hashed values of possible passwords
What is a random salt?
A random piece of data added to a password before they are hashed that is stored with the user id
What does a graph represent?
Complex, non-linear relationships (edges) between objects (nodes)
What are directed graphs?
Graphs with edges represented with arrows to show which direction the nodes can be visited
What are weighted graphs?
Where values are associated with edges
What is an adjacency matrix (when used to implement a graph)?
A 2D array that has values for whether there is an edge and a weight, it is symetrical if the graph is undirected
What is an adjacency list (when used to implement a graph)?
A list of all neighbours for each node which can include other values such as weight
What is a tree?
A connected, undirected graph with no cycles
What is a rooted tree?
A tree with a specific starting node that is normally represented above all other nodes
What is a binary tree?
A rooted tree where every node can only have up to two child nodes
What is a binary search tree?
A tree used to optimise searching by placing values lower than the root the left and the higher values to the right
What are the three main tree traversals?
Pre-order (root, left, right), in-order (left, root, right), post-order (left, right, root)
What are breath-first and depth-first tree traversals?
Breath-first means visiting all nodes of a certain level before their children and depth-first is where an entire branch is visited before moving onto other branches
What is Dijkstra’s shortest path algorithm?
An algorithm that works out the shortest path between two nodes using a weighted graph
How is the cost of a path calculated in Dijkstra’s shortest path algorithm?
The cost is calculated by adding the weight of all edges along the shortes route
