Prof. SzenherCSCI 235 Final Exam
Spring, 2003
CSCI 235 Final Exam
Instructions:
- Write your name at the top of every page.
- Answer all questions to the best of your ability. I will not answer any questions during the exam.
- If you finish early, you may leave. Do not talk while others are still taking the exam. I reserve the right to destroy your exam if you are excessively disruptive.
Useful Class Definitions:
You may assume that, unless otherwise noted, these classes have been fully implemented. You may use them in whatever situation you find effective.
class Node;typedef Node * NodePtr;
class Node {
public:
Node ();
Node (int InData);
Node (int InData, NodePtr InNext);
~Node ();
int GetData () const;
bool SetData (int NewData);
NodePtr GetNext () const;
boolSetNext (NodePtr NewNext);
voidPrint () const;
private:
int Data;
NodePtr Next;
}; / #include "Node.h"
class LinkedList {
public:
LinkedList ();
LinkedList (const LinkedList& InListToCopy);
~LinkedList ();
bool ClearList ();
NodePtrGetStart () const;
boolSetStart (NodePtr NewStart);
boolAddNodeToEnd (NodePtr NodeToAdd);
boolAddNodeToEnd (int DataToAdd);
voidPrint () const;
voidClearList ();
private:
NodePtrStart;
};
Useful Class Definitions (continued):
class TreeNode;typedef TreeNode * TreeNodePtr;
class TreeNode
{
public:
TreeNode ();
TreeNode (int);
~TreeNode ();
int GetData () const;
bool SetData (int InNewData);
TreeNodePtr GetLeftChild () const;
TreeNodePtr GetRightChild () const;
TreeNodePtr&GetLeftChildRef ();
TreeNodePtr& GetRightChildRef ();
bool SetLeftChild (TreeNodePtr);
bool SetRightChild (TreeNodePtr);
boolIsLeaf () const;
private:
int data;
TreeNodePtr leftChild;
TreeNodePtr rightChild;
}; / #include "TreeNode.h"
class BinarySearchTree
{
public:
BinarySearchTree ();
~BinarySearchTree ();
boolAddNode (int InDataToAdd);
boolDeleteNode (int InDataToDelete);
voidInOrderPrint () const;
TreeNodePtr Search (int InKey) const;
TreeNodePtr CopyTree () const;
private:
TreeNodePtr root;
voidClearTree (TreeNodePtr);
boolAddNodeRecursively (TreeNodePtr&, TreeNodePtr);
boolDeleteNodeRecursively (TreeNodePtr&, int);
boolDeleteNodeAt (TreeNodePtr&);
boolProcessLeftMost (TreeNodePtr&, int&);
voidInOrderPrintRecursively (TreeNodePtr) const;
TreeNodePtr SearchRecursively (TreeNodePtr, int) const;
TreeNodePtr CopyTreeRecursively (TreeNodePtr) const;
};
- (a) (10 POINTS) According to a famous formula due to Leibniz, is equal to the infinite series . Of course, we cannot in general determine the sum of an infinite series. We can approximateby summing a finite number of terms in the series above; the more terms used, the closer the approximation of .
For example:
etc…
Write a recursive function to approximate using the formula above. Your recursive function should continue to call itself until a term is reached whose denominator is greater than 105.
float CalculatePi (int denom, int n) {
if (denom > 1000) return 4.0/(float)denom;
else {
return pow(-1,n) * 4.0/(float)denom + CalculatePi (denom + 2, n+1);
}
}
void main ()
{
cout < CalculatePi (1, 0);
}
- (a) (10 POINTS) Implement operator= for the LinkedList class given on page 2.
LinkedList&
LinkedList::operator= (const LinkedList& ToCopy) {
ClearList ();
Start = NULL;
NodePtr rover = ToCopy.start;
while (rover != NULL) {
AddNodeToEnd (rover->GetData());
rover = rover ->GetNext();
}
return *this;
}
(b) (10 POINTS) Implement operator+= for the LinkedList class given on page 2.
Example:
LinkedList L;
L += 2; //should enqueue a node containing 2 to the list
L += 10; // should enqueue a node containing 10 to the list
LinkedList&
LinkedList::operator+= (int Data) {
AddNodeToEnd (Data);
return *this;
}
(c) (10 POINTS) Implement operator-- for the LinkedList class given on page 2. operator --should remove and deallocate the last node in the LinkedList.
LinkedList&
LinkedList::operator-- () {
if (start == NULL) {
return *this;
}
else if (start->GetNext() == NULL) {
delete start;
start = NULL;
return *this;
}
else {
NodePtr rover = start;
while (rover->GetNext()->GetNext() != NULL) {
rover = rover ->GetNext();
}
delete rover->GetNext();
rover->SetNext(NULL);
return *this;
}
}
- (a) (10 POINTS) Write a method to count the number of nodes in a binary search tree.
int
BinarySearchTree::CountNodes (NodePtr CurrRoot) const
{
if (CurrRoot == NULL) return 0;
else {
return 1 + CountNodes(CurrRoot->GetLeft()) + CountNodes(CurrRoot->GetRight());
}
}
(b)(10 POINTS) Draw the binary search tree that results from the storage of the following sequence of values: 10, 7, 3, -4, -9, -99
(c)(10 POINTS) The binary search tree that you drew in part (b) is of a type that I will call a left-handed linear binary search tree, for obvious reasons. Implement a method (assume that it is a public member of the BinarySearchTree class defined on page 3) that can detect a left-handed linear binary search tree. The method should return true if and only if the binary search tree is a left-handed linear binary search tree and false otherwise.
bool
BinarySearchTree::TestLHLBST() const {
NodePtr rover = root;
while (rover != NULL) {
if (rover->GetRight() != NULL) return false;
rover = rover->GetLeft();
}
return true;
}
(d) (10 POINTS) As we discussed in class lecture, the left-handed linear binary search tree is the worst-case input to many binary search tree algorithms (e.g. SearchRecursively). We can modify a left-handed linear binary search tree so that its height is approximately halved, as follows:
Write a method (assume that it is a public member of the BinarySearchTree class defined on page 3) that “shortens” a left-handed linear binary search tree of n nodes as illustrated above. You may assume that n is at least 3.
void
BinarySearchTree::HalveChain () {
int numNodes = CountNodes ();
NodePtr prev = root;
NodePtr curr = root->GetLeft();
for (int i = 0; i < numNodes/2; i++) {
curr->SetRight(prev);
prev ->SetLeft(NULL);
prev = curr;
curr = curr->GetLeft();
}
root = curr;
}
(e) (10 POINTS) Give the worst case running time of the algorithm developed in part (d) in Big-O notation for a binary search tree with n nodes.
O(n)
4.(a) (5 POINTS) Give real-life example of an inheritance relationship (naming both the base object and the derived object or objects).
Various answers accepted.
(b) (5 POINTS) State one advantage gained by a programmer who uses an inheritance relationship.
A base class can pass down to its derived classes those methods and data that are common to the derived classes. The derived classes then need not implement these inherited methods and data.
1