Data Structure Flashcards
What is an Array
A static collection of items of the same data type called elements
When is an Array used
When the required number of data items is known in advance
What is a Binary Tree
A dynamic structure of nodes
When are binary trees used
Storing and searching a large data sets
How does binary search work
It repeatedly checks the middle item in the data check and discards half the data during each pass until either the item is found. List must be sorted
What is a Hash table search
An attempt to find an item immediately without comparing other items in the data set
How does Hash table search work
Using the hashing function on the key to determine the item index
How does Linear search work
It checks each item from the start of a list one by one until it reaches finds the specified item. List does not need to be sorted
What is the efficiency for Binary search
Time complexity: Space Complexity:
Best: O(1) O(1)
Average: O(log n)
Worst: O(log n)
What is the efficiency for Hash table search
Time complexity: Space Complexity:
Best: O(1) O(1)
Average: O(1)
Worst: O(n)
What is the efficiency for Linear search
Time complexity: Space Complexity:
Best: O(1) O(1)
Average: O(n)
Worst: O(n)
How does Bubble sort work
It works by comparing each item with the next item, swapping them if they are out of order.
What is a pass
Comparing an item with its neighbour until the end of the data set
What is the efficiency Bubble sort
Time complexity: Space Complexity:
Best: O(n) O(1)
Average: O(n^2)
Worst: O(n^2)
What is the insertion sort
Comparing an item with the previously placed items and putting it in the correct position. This is good for small data set
What is the efficiency of insertion sort
Time complexity: Space Complexity:
Best: O(n) O(1)
Average: O(n^2)
Worst: O(n^2)
What is Merge sort
A sort that uses divide and conquer. It repeatedly splits the data set in half until each item is in its own list. Then adjacent lists are merged together with each list being put back in the right order
What is the efficiency of merge sort
Time complexity: Space Complexity:
Best: O(n log n) O(n)
Average: O(n log n)
Worst: O(n log n)
What does ‘Divide and Conquer’ mean
Create two or more sub-problems from the larger problem, then solve individually before combining to solve the bigger problem
What is Quicksort
Quicksort works by using divide and conquer. This happens by using pointers to compare two items then swapping if they are in the wrong place one pointer stays where its is and the other pointer moves one more to the middle. this happens until there is an item of data set in stone (pivot) then the sort repeats simultaneously with the lists either side of the pivot until all items are sorted
What is the efficiency of Quicksort
Time complexity: Space Complexity:
Best: O(n log n) O(log n)
Average: O(n log n)
Worst: O(n^2)
What is an Optimisation Algorithm
Routes that find optimal paths between vertices on a graph
