CS 2401 Test #3

Date: Wednesday, April 28, 2010.

Name: ___________________________________________________________________

1-2. Show, step by step, what will happen if we add elements 28, 0, 4, 20, 10, and 3 to the binary search tree; do not forget to balance at every step at which balancing is necessary. No code is needed.



















































3. Redraw the binary search tree below showing how it will look like after the elements 75 and 25 are deleted. Assume that no tree balancing takes effect after the elements 75 and 25 are deleted.
                          50
                        /     \
                       /       \
                      /         \
                    25           75
                  /    \       /    \
                15      40    65    90
               /  \    /  \  /  \  /  \
              5   20  30 45 60  70 85  95














































4. Consider a method printBinaryTree() that traverses and prints the contents of binary trees.
                          50
                        /     \
                       /       \
                      /         \
                    25           75
                  /    \       /    \
                15      40    65    90
               /  \    /       \  /  \
              5   20  30       70 85  95









































5. Show, step by step, how binary search will look for an element 3 in the sorted list 0, 3, 4, 10, 20, 28. No code is needed. What is the worst-case and average complexity of binary search?


























































6. Show, step by step, how bubble sort will sort a list 28, 0, 4, 20, 10, 3. No code is needed. What is the worst-case and average complexity of bubble sort?


























































7. Show, step by step, how selection sort will sort a list 28, 0, 4, 20, 10, 3. No code is needed. What is the worst-case and average complexity of selection sort?


























































8. Show, step by step, how insertion sort will sort a list 28, 0, 4, 20, 10, 3. No code is needed. What is the worst-case and average complexity of insertion sort?


























































9. Show, step by step, how quicksort will sort a list 28, 0, 4, 20, 10, 3. No code is needed. What is the worst-case and average complexity of quicksort?


























































10. Show, step by step, how mergesort will sort a list 28, 0, 4, 20, 10, 3. No code is needed. What is the worst-case and average complexity of mergesort?