# CS2420 PT2

The flashcards below were created by user laonese on FreezingBlue Flashcards.

1. Average case, worst case, and memory usage of merge sort.
• Average: O(nlogn)
• Worst: O(nlogn)
• Best: O(nlogn)
2. Average case, worst case, and memory usage for quick sort.
• Average: O(nlogn)
• Worst: O(n^2)
• Best: O(nlogn)
• Memory usage: O(1)
3. How does a sequential search work?
Start at the first element in the list and continue until either the item is found in the list or the entire list is searched.
4. Average and worst case scenario for sequential(linear) search
O(n)
5. How does a binary search tree work?
List must be ordered.  Uses the divide and conquer approach.  Compare item with middle of list.  If item equals middle, then found, else if the item is less, restrict search to lower half and vice versa if item is higher
6. What is the best and worst case for binary search?
O(log(n))
7. How does hash table search work?
Data is first organized by the hash table which is stored in an array.  To find out if something is stored in the hash table, a hash function used to a key.  This gives the address of the item in the hash table.
8. How does selection sort work?
Divides the data into two sublist of items sorted and remaing items to be sorted.  Finds the smallest element in the unsorted sublist, exchanging it with the leftmost unsorted element and moving the sublist boundaries one element to the right.
9. Average case, worst case, and memory usage of selection sort.
• Average: O(n^2)
• Worst: O(n^2)
• Memory Usage:
10. How does bubble sort work?
Compares each pair of adjacent items and swapping them if they are in the wrong order.  This is repeated until no swaps are needed.
11. Average and worst case for bubble sort
• Average: O(n^2)
• Worst: O(n^2)
• Best: O(n)
12. How does insertion sort work?
Iterate through the list and move one element at a time to the correct location within the sorted list.
13. Average and worst case for insertion sort
• Average: O(n^2)
• Worst: O(n^2)
• Best: O(n)
14. How does quicksort work?
A divide and conquer algorithm.  First divides a large array into two small sub-arrays: lower and higher elements.  Then recursively sort the sub-arrays.  Pick a pivot, reorder array so all elements lower than pivot on left and higher on right.  Apply same steps to sub-array of elements.
15. How does mergesort work?
Divide unsorted list into smallest unit of 1 element, then compare each element with the adjacent list to sort and merge them.
16. How does heapsort work?
First a heap is built out of the data.  Then a sorted array is created by repeatedly removing the largest element from the heap and inserting it into the array.
17. Average and worst case for heap sort
• Average: O(nlogn)
• Worst: O(nlogn)
• Best: O(nlogn)
18. How does bucket sort work?
Set up an array of buckets.  Put objects into buckets.  Sort each bucket.  Gather the results and put all elements back into the original array.
19. Preorder
• Root
• Left
• Right
20. Inorder
• Left
• Root
• Right
21. Postorder
• Left
• Right
• Root
22. What are AVL trees?
A self-balancing binary search tree.
23. What are B-trees?
A tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions.  A node can have more than two children.
24. What are B+trees?
Can be viewed as B-Trees in which each node contains only keys and to which an additional level is added at the bottom with linked leaves.  Primary value is storing data for efficient retrieval in block-oriented storage context.
 Author: laonese ID: 288056 Card Set: CS2420 PT2 Updated: 2014-12-11 01:13:17 Tags: CS2420 Folders: Description: CS2420 Show Answers: