CSC 332 - Data
Structures - Spring 2014 |

There will be a midterm exam on Tuesday, February 25, 2014.

To prepare for the exam make sure that you know the following. Keep in mind that given time constraints, the number of questions may be different than below. Further, questions may vary some from what you see below. This is a guide, not a contract.

1. Problem 1.5 on page 25. What would be the Big-Oh of its execution time?

2. Problem 2.1 on page 50.

3. Problem 2.7 on page 51.

4. Using the limit as N approaches infinity, compare the ratio of f(n) to g(n) to determine the relative growth rates. Use L'Hopital's Rule, if necessary. See page 31.

5. Problem 2.11 on page 52.

6. Problem 2.12 on page 52.

7. Problem 2.20 on page 53.

8. Write contains or other method of similar difficulty for MyArrayList.

9. Write contains or other method of similar difficulty for MyLinkedList.

10. Evaluate a postfix expression using a stack. Be able to draw the stack after every necessary push and pop.

11. For a given tree, be able to identify its root, its leaves, its height, whether it is balanced, its preorder, postorder, and inorder traversal.

12. Know how to perform a rotation (single or double) in order to balance an AVL tree.

Remember:
The exam is not open notes and not open book. However, you may bring in **a
single sheet of paper** with some notes on it.