CS 1112 Final Exam
1. Please answer, in your own words, the following questions:
b) What is a Stack, or Queue, or Binary Search Tree, or Binary Search, or Bubble Sort, or Recursion ... ?
2. In the following C++ segment, circle and explain any errors you see. The errors could be due to syntax errors, run-time errors, or invalid references and assignments. If the code calls for a cout statement, list the output (if pos sible).
#include <iostream.h>
#include "Stack.cpp" // as defined in class
#include "Queue.cpp" // as defined in class
#include "Strings.cpp" // as defined in class
class Person
{ public: name: Strings;
public: setName(Strings);
}
class Node
{ public: double data;
public: Node *next;
public: Node(double); // sets next to null, data to input value
}
int main(void)
{ Stack S;
Queue Q;
Person P;
char E;
double *px; double x;
Node *p, *q, *r;
S.push('B'); S.push('W');
Q.enqueue('B'); Q.enqueue('W');
cout << S.pop(); cout << Q.dequeue();
cout << S.pop(); cout << Q.dequeue();
cout << S.pop();
Init(P); P.name = "Bert Wachsmuth"; P.setName;
px = 8.6; x = 9.5;
*px = 10.0; *x = *px;
p = new Node(1.0); q = new Node(2.0); r = new Node(3.0);
p->next = q; q->next = r; r->next = p;
cout << q->next;
cout << p->next->next->next->next->data;
delete q;
cout << p->next->next->next->next->data;
}
3. Which of the following two trees is a binary search tree ?
4. A tree could be represented either as a picture, or by listing the nodes in a specific order.
a) List the nodes in the tree below as they would appear if the tree below is traversed in post-order.
b) If the nodes below are listed from a tree traversed in pre-order, reconstruct the picture of the tree:
Level 0: Node data: 50
Level 1 Node data: 25
Level 2: Node data: 10
Level 1: Node data: 75
Level 2: Node data: 60
Level 2: Node data: 90
Level 3: Node data: 80
5. Consider the binary tree on the left. List each of the following:
|
7) For the Stack class, write the complete code for pop, defined as:
You can assume that a node has been defined, as usual, like this:
8. For a binary search tree, write C++ code that accomplishes the following:
a) A function that finds the left-most node of a tree starting at the input node pointer p.
b) A function that traverses the tree in inOrder and prints out the values of all nodes in the tree.
9. Write a small program that finds the sum and the average of all numbers contained in a data file "test.dat". That file contains an unknown number of doubles, one per line.
10. Create a complete
Triangle class with three fields, one double for the base, one double for the height, and one double for the area. Include the following methods in your class:Then write a test program that uses two triangles, one with base and height 1 and the other with base and height 2, and prints out the complete information about these triangles.