Study guide for the examination on March 13. 1. Just so you don't think you are free to forget it, I will ask a small number of questions about material from the earlier portion of the course. 2. Review all assigned homework. 3. I will expect you to know everything about binary trees, including: a) Preorder, inorder, and postorder traversal. (Section 5.2.) b) Theorems relating the number of items (size) of a binary tree to its height. (See Exercises 5.1 and 5.2, but I will definitely not ask you to prove anything on the test.) c) What a binary search tree looks like if a given list of items is inserted in a given order. (See Figure 1.3 on page 160.) d) I may ask you to write from memory a portion of the code you turned in for Assignment 5. e) Exercises 5.7 or 5.8 on page 187 would make a good test question. 4. I will expect you to know about the array implementation of a heap. You should be able to show, using a picture, what happens to an array representing a heap if an item is inserted or deleted, such as Exercise 5.18 on page 188. a) If the array for a maxheap is 9 5 8 4 3 6 7 2 1, what will the array look like after deleting the maximum item? b) Suppose that that same item is reinserted. What will the array look like now? 5. Definitions of various terms. a) leaf b) height c) AVL balancing condition d) heapsort (explain it in detail) 6. Heapsort, page 244-247 of your textbook.