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:

 

  1. all nodes that are leafs
  2. all pairs of nodes that are siblings
  3. all ancestors of the node with value 60
  4. all descendents of the node with value 25
  5. the height of the tree
  6. the size of the tree

 

6. Draw the binary search tree after each operation. Each insertion and deletion operates on the original tree, and the new tree should again be a binary search tree.

a) Insert 65 b) Insert 35

c) Delete 70 d) Delete 60

d) Delete 50

7) For the Stack class, write the complete code for pop, defined as:

Element pop(void);

You can assume that a node has been defined, as usual, like this:

typedef int Element;
class Node
{
public double data;
public Node *next;
public Node(void);
public Node(Element);
};

 

 

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.

void leftMost(Node *p);

On input, p is a pointer to a node of a tree, on output p points to the left-most node of the subtree.

b) A function that traverses the tree in inOrder and prints out the values of all nodes in the tree.

void inOrder(Node *p);

Recall that a Node and a Binary Search tree are defined as follows:

typedef int Element;
class Node
{
public double data;
public Node *left, *right;
public Node(void);
public Node(Element);
};

class BinSTree

{

private: Node *root;

}

 

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:

Constructor:

provide two constructors, one with no input and the second with two doubles as input, corresponding to the base and the height of the triangle.

Methods:

void setBase(double); sets the base to the input value

void setHeight(double); sets the height to the input value

void computeArea(); computes the area of the triangle

void display(); to display the information in the current object

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.