The final will have multiple-choice questions, small programming questions and a few other kinds of questions, such as problems on binary search trees. The short-essay questions on this practice exam will prepare you for the final.

1. What is a dangling pointer?

2. What are the consequences of using a dangling pointer in a program?

3. Why is it necessary for a C++ programmer to understand his or her program at a physical level of detail?

4. How do you deallocate a variable or array that is allocated by each of the following statements?
   1. int x;
   2. int* x = new int;
   3. int x[10];
   4. int* x = new int[10];

5. What is a memory leak?

6. Explain the difference between the interface and the implementation of a function. What belongs to the interface? What belongs to the implementation?

7. Same as the preceding question, but for an abstract data type rather than a function.

8. What is the usual consequence to a programmer of violating an abstraction? How does it affect the ease of programming?

9. How do you compare two strings to see if they are equal?

10. How can you copy null-terminated string A into array B?

11. Where is the smallest value in a binary search tree located? The largest value? A value that is close to the middle? How can you find the value that immediately follows the value at the root?

12. What does an object contain?

13. Which objects can make use of a private variable or function in an object?

14. In what parts of a program can a protected variable or function of a class be used?

15. Explain the purpose of a wrapper class.

16. Suppose that s is a stack object of class IntStack. Write a statement to pop s and put the popped value in variable x.

17. What do C++ templates provide? Where would they most likely be used?

18. What is the purpose of a destructor in a class?

19. What does a copy contructor do? When it is called? What is a prototype for the copy constructor for class Widget?

20. To within a constant factor, how long do each of the following take?

    1. Look up a value in a balanced binary search tree that has n values in it.

    2. Insert a value into a binary search tree that has n values in it.

    3. Compute the length of a linked list where the length is n.

    4. Add a value to the front of a linked list with n things in it.

    5. Sort a linked list using Lsort, where the list has n members.

    6. Push a value onto a stack of size n.

21. Write a function called reverse that takes a null-terminated string s and returns null-terminated string that consists of s written backwards. For example, if s is ``foo'' then reverse(s) returns string ``oof''. The result string should be put into newly allocated memory. String s should not be modified.

        char* reverse(char *s)
     

22. Suppose that you insert 20 into the following tree using the algorithm that does rotations to keep the tree height-balanced. What is the resulting tree? Be sure to do the rotations correctly.

                              49
                             /  \
                            /    \
                          26      75
                         /  \       \
                        /    \       \                     
                      16      42      85
                     /  \
                    /    \
                  12      19 
      

23. Types TreeNode and Tree are shown below. They are used in a classical implementation of binary search trees. Write a function called largestEven that takes a binary search tree T and returns the largest even number that occurs in T. If T does not have any even numbers in it, then largestEven(T) should return -1.

    Presume that T contains no negative numbers. (This requirement is part of the contract.)

          struct TreeNode {
            int data;
            TreeNode* left;
            TreeNode* right;
            TreeNode(int x, TreeNode* L, TreeNode *R)
            {
              data = x;
              left = L;
              right = R;
            }
          };   
          typedef TreeNode* Tree;
    
    
          int largestEven(Tree T)
          {
      

24. Write a function called flip that computes a mirror image of a binary tree, using the types of the preceding problem. The mirror image is obtained by flipping the tree over, or by holding it up to a mirror. The mirror image of a binary search tree has values in descending order from left to right, rather than in ascending order.

25. You are using an object-oriented implementation of a queue of integers. (The class is called Queue.) The operations that you can do on a queue are to remove(), insert(x), and test isEmpty(). You are writing outside the queue implementation. Write a function that performs a peek in the queue. That is, it returns what is at the front of the queue, without modifying the queue. It is allowed to modify the queue temporarily, as long as the queue is put back the way it was. Presume that the queue has something in it.

     int peek(Queue q)