Name ___________________

CPTR246 Spring '99 (100 total points) Exam 3

  1. Trees: Answer the following questions based on the tree given.

 

 (picture won't display - substitute any old tree with integers labeling the nodes.)

 

  

  1. What is the value located at the root of the tree? (5 points)

    2.  

  2. How many leaves does the tree have? (5 points)

    3.  

  3. Give the breadth-first listing of the nodes. (5 points)

    4.  

     

  4. Give the preorder listing of the nodes. (5 points)

    5.  

     

  5. Give the postorder listing of the nodes. (5 points)

    6.  

     

  6. Give the inorder listing of the nodes. (5 points)

 

 

  1. Template functions: (10 points)

    2. Write a template function called displayArray that displays arrays of objects. It should take two parameters: the array of objects and the number of objects in the array. Examples of its use would be as follows:

     

    int testScores[100];

    int numberOfScores;

    double monthlyAverages[12];

    printArray(testScores, numberOfScores);

    printArray(monthlyAverages, 12);

  2. Operator overloading: (10 points)

Below is the definition for the employee structure along with the definitions for two employee objects. We want to be able to "compare" two employee objects to see which is "less" using the '<' operator. You are to give the necessary C++ code to overload the '<' operator - but YOU define what is means for one employee to be less than another.

struct employee { // defines employee "type"

int ID; // employee id number

double hourlyRate; // pay rate

char name[30]; // employee's first name

double hoursThisWeek; // hours this week

};

employee emp1;

employee emp2;

. . .

if (emp1 < emp2){ . . . .

  1. In English, what do you mean when you say one employee is "less than" another? (NOTE: There are many, many correct answers here!)

    2.  

     

     

     

     

  2. Give the C++ code to overload the '<' operator for employees.

  1. Recursion: There is an interesting series of integers known as the Fibonacci numbers. The first Fibonacci number is 0; the second is 1. As for the rest of the numbers in the series, each is equal to the sum of the previous two numbers. That is,

    2. Fib(0) = 0

    Fib(1) = 1

    Fib(2) = 1 (It is 0 + 1)

    Fib(3) = 2 (It is 1 + 1)

    Fib(4) = 3 (It is 1 + 2)

    Fib(5) = 5 (It is 2 + 3)

    Fib(6) = 8 (It is 3 + 5)

    Fib(7) = 13 (It is 5 + 8)

    Fib(8) = 21 (It is 8 + 13)

    and so on ....

    If you don't see that the next two Fibonacci numbers are 34 and 55, ASK!!! In order to answer this question correctly, you must understand the series.

    Write a recursive function called Fib that takes one integer parameter n and returns Fib(n). For example, Fib(8) should return 21. (HINT: There are two base cases.) (15 points)

  2. Recursion: (20 points)

    3. You have been given a copy of the code that defines the BinaryTree class. What modifications would be necessary to the code for the BinaryTree class to include a recursive member function SumOfEvenNodes that returns the sum of all nodes in the tree whose integer value is an even number. (NOTE: An integer object x is even if the following condition is true: (x % 2 == 0))

    Changes to the public section:

     

     

     

    Changes to the private section:

     

     

     

    Code for the function definitions:

  3. Referring again to the class definition for the BinaryTree class, rewrite the InTree member function as a non-recursive function. Because of the special tree structure (that is, all nodes in the left subtree have values less than this node and all nodes in the right subtree have values greater than this node), we can determine if a value is in the tree directly, that is without using recursion. (15 points)

 

int BinaryTree::InTree(int x){

// pre: none

// post: return true if x is in the tree, false if not

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

}