Final Exam Study Guide

You MUST present a picture ID

Exam Dates:

• Sections 0101 - 0104 (Frey) -- Tuesday May 20th, 10:30am - 12:30pm
• Sections 0201 - 0204 (Raouf) - Monday May 19th, 6:00 - 8:00pm

Use the list of questions below as a guide when studying for the final exam. It is by no means a comprehensive list of all material that you are responsible for.

Like many other subjects, computer science is cumulative in nature. We can't discuss each aspect of computer science in isolation. Therefore, our final exam will also be cumulative. The vast majority (80% or more) of the exam will be taken from material presented since the second exam. The remaining 10-20% will be taken from other material we have covered this semester.

I. Material Prior to Exam 2

General C++ topics
1. basic class design and usage
2. const vs non-const methods
3. aggregation
4. function overloading
5. constructors, destructors, copy constructor, assignment operator
6. file I/O using streams
7. passing parameters by value, by reference, by reference to const
8. returning objects by value, by reference, by reference to const
9. strings, vectors

   II. Recursion

   Consider the following recursive mathematical function f(n) = 1 if n = 0 f(n) = 4 if n = 1 f(n) = 2 * f(n - 1) - f( n - 2) for n > 1
10. Write the syntactically correct C++ implementation of this function.
11. What is/are the base case(s)?
12. Classify this function as direct, indirect, linear and/or tree recursion.
13. What is the value of f(5)?
14. Digram the recursive calls which occur when calculating f(5).
15. What is/are the precondition(s) for this function?

    Consider the following code. Recall that adding strings ( operator+ ) results in string concatenation.

    const string a = "0123456789ABCDEF"; string mystery(int n) { if (n <= 0) return (""); else if (n <= 15) return (a[ n ]); else return mystery( n / 16) + (a[ n % 16 ]); }
16. What is the output of cout << mystery( 34 ) << endl; ?
17. What is the output of cout << mystery( 255 ) << endl; ?
18. In general, what does mystery do?

    Consider the following code

    #include <iostream> using namespace std; void mystery (int n) { if (n > 1) { cout << n << endl; if (n % 2 != 0) mystery( 3 * n + 1 ); else mystery( n / 2 ); } } int main() { mystery ( 3 ); return 0; }
19. What is the output from the code?
20. Under what condition(s) will this code cause infinite recursion?
    (Note: you can cut/paste this code into a .C file and compile/link/run it to verify your answer).

21. What is the difference in the behavior of these two recursive functions? Why does this difference occur?

    void write (int n) { if (n >= 1) { cout << n << end; write (n - 1 ); } }

    void write (int n) { if (n >= 1) { write (n - 1 ); cout << n << end; } }

22. List three advantages of iteration over recursion.
23. List three advantages of recursion over iteration.
24. Use recursion to implement the traversals of a binary tree.

    III. Sorting and Searching

25. Given a non-empty unsorted array with 17 elements
    1. What is the minumum number of comparisons performed by a linear search when attempting to find a value in the array? Under what conditions would the number of comparisions be the minimum?
    2. What is the maximum number of comparisons performed by a linear search when attempting to find a value in the array? Under what conditions would the number of comparisions be the maximum?
    3. What is the average number of comparisons performed by a linear search when attempting to find a value in the array?
    4. Generalize your answers for an array of N elements.
26. Given a non-empty sorted array of 17 elements
    1. What is the minumum number of comparisons performed by a linear search when attempting to find a value in the array? Under what conditions would the number of comparisions be the minimum?
    2. What is the maximum number of comparisons performed by a linear search when attempting to find a value in the array? Under what conditions would the number of comparisions be the maximum?
    3. What is the average number of comparisons performed by a linear search when attempting to find a value in the array?
    4. What is the minumum number of comparisons performed by a binary search when attempting to find a value in the array? Under what conditions would the number of comparisions be the minimum?
    5. What is the maximum number of comparisons performed by a binary search when attempting to find a value in the array? Under what conditions would the number of comparisions be the maximum?
    6. What is the average number of comparisons performed by a binary search when attempting to find a value in the array?
    7. Generalize your answers for an array of N elements.
27. Given the sorted array a[ ] = { 1, 3, 5, 7, 9, 12, 18, 22, 23, 30, 35, 39, 41, 44, 46, 50, 51}
    List the values which will be checked when performing a binary search for the value 47.
28. Given the array a[] = { 12, 87, 22, 6, 19, 44, 92, 21}, diagram the execution of mergesort (merge) to sort the array.
29. Given the array a[] = { 12, 87, 22, 6, 19, 44, 92, 21}, diagram the execution of quicksort (partition) to sort the array.
30. The MergeSort code on the web sorted an array of integers, but the algorithm for MergeSort is data-independent. Rewrite MergeSort() as a function template.
31. What are the precondition(s) for mergesort?
32. What are the precondition(s) for quicksort?
33. List one difference between quicksort and mergesort.
34. List one similarity between quicksort and mergesort.

    IV. Trees

    For these questions, the C++ class definition of a General Tree, BinaryTree, BinarySearchTree (BST) and TreeNode will be provided if/when necessary
    

35. Given a general tree's first-child, next sibling representation, draw the tree.
36. Given a general tree, draw its first-child, next sibling representation.
37. For any tree T, define
    1. path in T
    2. length of a path in T
    3. depth of a node in T
    4. height of a node in T
    5. the depth of T
    6. the height of T
38. Define full binary tree, perfect binary tree
39. Define internal node and external node in a rooted tree.
40. Write the syntactically correct recursive C++ code for in-order, pre-order or post-order traversal for a binary tree.
41. Given the array a[ ] = { 50, 30, 20, 66, 42, 77, 70, 2 }
    Draw the tree that results from inserting these values into an initially empty BST.
42. Given the BST
    1. What is the output from an in-order traversal of the BST?
    2. What is the output from an pre-order traversal of the BST?
    3. What is the output from an post-order traversal of the BST?
    4. What is the output from a breadth-first traversal of the BST?
    5. Draw the BST using first-child, next-sibiling representation
    6. Add the value 'V' to the tree
43. Write a syntactically correct function which might be part of a BST class, or use a BST as a parameter. For example
    1. FindMin( ) that finds and returns the minimum value in a BST
       Write both the iterative and recusive versions.
    2. PrintTree( ) that prints the data from each node in the BST in post-order.
    3. BST destructor.
44. Insert the values {2, 4, 5, 7, 12, 15, 19} into an initially empty BST.
    What is the shape of the tree? Why is this so?
45. Explain why the BST destructor must use a post-order traversal of the tree.
46. Explain why an in-order traversal of a BST always results in the data being printed in sorted order.
47. Write the code for a Breadth-First Search of a binary tree.
48. Write the code for a Depth-First Search of a binary tree.