DATA STRUCTURES AND
ALGORITHMS MIDTERM EXAM
QUESTIONS & ANSWERS
Linear Search - Correct Answers -slow --> N/2 comparisons
O(N)
Binary Search - Correct Answers -Fast, but the array must be sorted log2(N)
Drawbacks --> insertion takes longer
O(logN)
Unordered Arrays - Correct Answers -fast insertion O(1)
slow linear search and deletion O(N)
Bubble Sort - Correct Answers -Comparisons: O(N^2)
Swaps: O(N^2) (less than comparisons)
Big O: O(N^2)
Selection Sort - Correct Answers -Comparisons: O(N^2)
Swaps: O(N)
Big O: O(N^2) --> faster than bubble sort
Ordered arrays - Correct Answers -fast binary search O(logN)
slow insertion and deletion O(N)
Insertion Sort - Correct Answers -Comparisons: O(N^2)
--> max is N*(N-1)/2, average is N*(N-1)/4
Shifts (copies): O(N^2) --> shift is not as time consuming as a swap
--> Average: N*(N-1)/4
Big O: O(N^2) --> 1/2 the time than bubble sort
Data that is already sorted it runs in O(N) --> efficient way for arrays that are only
slightly oout of order
Enhanced Insertion sort - Correct Answers -Comparisons: O(NlogN)
Shift: O(N^2)
Big O: O(N^2) --> faster than bubble sort
Stacks - Simple Applications - Correct Answers -Reversing a word
Delimiter matching
ALGORITHMS MIDTERM EXAM
QUESTIONS & ANSWERS
Linear Search - Correct Answers -slow --> N/2 comparisons
O(N)
Binary Search - Correct Answers -Fast, but the array must be sorted log2(N)
Drawbacks --> insertion takes longer
O(logN)
Unordered Arrays - Correct Answers -fast insertion O(1)
slow linear search and deletion O(N)
Bubble Sort - Correct Answers -Comparisons: O(N^2)
Swaps: O(N^2) (less than comparisons)
Big O: O(N^2)
Selection Sort - Correct Answers -Comparisons: O(N^2)
Swaps: O(N)
Big O: O(N^2) --> faster than bubble sort
Ordered arrays - Correct Answers -fast binary search O(logN)
slow insertion and deletion O(N)
Insertion Sort - Correct Answers -Comparisons: O(N^2)
--> max is N*(N-1)/2, average is N*(N-1)/4
Shifts (copies): O(N^2) --> shift is not as time consuming as a swap
--> Average: N*(N-1)/4
Big O: O(N^2) --> 1/2 the time than bubble sort
Data that is already sorted it runs in O(N) --> efficient way for arrays that are only
slightly oout of order
Enhanced Insertion sort - Correct Answers -Comparisons: O(NlogN)
Shift: O(N^2)
Big O: O(N^2) --> faster than bubble sort
Stacks - Simple Applications - Correct Answers -Reversing a word
Delimiter matching
