Data Structures Flashcards
What is a 1 dimensional array defined as?
a finite set of elements of the same data type
What is a tuple?
A set of values which can be of any data type, but can not be changed.
What makes up a record?
several fields that each contain one item of data
What is an abstract data type?
A data type that has been created by the programmer.
How does a queue work?
Data can only be added to the end and Data can only be retrieved from the front.
Give some common examples of abstract data types? (4 things)
Queues, stacks, graphs and lists
What is a dynamic data structure?
A data structure that is able to increase or decrease the amount of space in memory it takes up.
What is the heap?
A portion of memory of which space is automatically allocated or de-allocated as required. This allows for dynamic data structures.
What is the main drawback of using dynamic data structures?
They can cause an overflow if they exceed the maximum memory limit which will cause data to be lost and the program to crash.
What are examples of dynamic data structures? (2 things)
queues, stacks
What is a static data structure?
A data structure that is fixed in size
What is an example of a static data structure?
array
What is the difference between a priority queue and a normal queue
In a priority queue the items are removed from the queue based on their priority, with the item with the highest priority being removed first, rather than being removed in the order they were added to the queue.
What is a list?
An abstract data type made up of items, in which the same item may occur more than once.
What does each node in a linked list contain?
The data field and a pointer field that points to the next item in the list
How does a stack work?
If you want to remove an item, you have to remove the item that was added most recently.
How does a hash table work?
The data being stored is passed into a hashing algorithm that generates an address, the data is then stored at that address in the hash table.
What is a graph?
A graph is a set of nodes connected by edges. An edge can have a weight to show the cost to traverse it and a direction in which it must be traversed.
What is a depth first traversal of a graph?
You go as far down one route as you can before backtracking until you can take a new route.
What is a breadth first traversal of a graph?
We visit all the neighbours of the root node, and then all the neighbours of the first node visited, and then all the neighbours of the second node and so on.
What is a binary tree?
A graph where each node, apart from the root node, has one parent and a maximum of two children.
What is a pre-order traversal of a binary tree?
Draw an outline around the tree starting with at the root node and moving left. Output the data in each node as you pass to the left of it.
What is an in-order traversal of a binary tree?
Draw an outline around the tree starting with at the root node and moving left. Output the data in each node as you pass under it.
What is a post-order traversal of a binary tree?
Draw an outline around the tree starting with at the root node and moving left. Output the data in each node as you pass to the right of it.
