Data structures Flashcards
Explain differences between static data-structures and dynamic data-structures (2 marks)
static data-structures have storage size determined at compile time, dynamic data-structures can grow/shrink during run-time
static data structures don’t store pointers so typically use less storage space, whereas dynamic data structures do store pointers to the next item so use more storage space
Two differences between static and dynamic data-structures (2 marks)
Static data-structures have a storage size determined at compile time, dynamic can grow/shrink in run-time
Dynamic require memory to store pointers to the next items which static data-structures don’t need
What is a stack?
A Last-In-First-Out (LIFO) abstract data type
Why is a static implementation less efficient at inserting new items into a list than a dynamic implementation? (2 marks)
Not possible to simply insert an item into middle of list
In a dynamic implementation, insertion achieved by adjusting pointers
Explain how a stack can be used to implement a repeat action and an undo action on a stack (5 marks)
- Stack is used to store user actions
- Each time an action is completed it is pushed onto the top of the stack
- unless it’s an undo action
- when repeat action is used then the top item from the stack is used to indicate the action to complete
- when undo action is used the top item is popped from the stack of actions
What is a graph?
A diagram consisting of joining vertices to edges.
What is a directed graph?
A diagram consisting of vertices, joined by directed edges
Explain the circumstances in which it is more appropriate to represent an adjacency list instead of an adjacency matrix (2 marks)
(1 mark) Adjacency list appropriate when the graph is sparse
(1 mark) When edges rarely changed
Describe a tree data structure
No cycles
Has a root node
Each root node has at most 2 child nodes
Explain how a value is stored in a hash table (4 marks)
-Hashing algorithm is applied to the key
-The result is an index of where to store the value in an array
-It is possible that the hashing algorithm might generate the same key for two different values
-in which case a collision handling method is used
Explain the steps of rehashing (3 marks)
A larger hash table is created
Each value in the existing table is inserted into the new table
In a position determined by a new hashing algorithm
Why is hashing used? (1 mark)
So that searching, adding and deleting can be done efficiently
Explain what a hash function is (2 marks)
A function applied to a key which generates a hash value
Explain what a collision is and how to deal with it (2 marks)
When two keys compute the same hash value
Store the record in the next available location in the file
What is a heuristic technique?
A heuristic technique employs a method of finding a solution that might not be the best
