Midterm #2 Spring 1994, 61B
Problem 0 Problem 1 Problem 2 Problem 3
midterm
Problem 0 (1 point, 1 minute)
Put your login name on each page. Also make sure you have provided the information requested on the first page. You will lose this point if any of this information is missing.
Background for problems 1 and 2
Given below is the definition of a class for a tree of integers similar to the tree of strings you used for homework assignment 8.
class Tree { private:
int value; Tree* left; Tree* right;
public: Tree ( );
int Value ( );
Tree* Insert (int); void InitGenerator ( ); Tree* Next ( );
};
Problems 1 and 2 involve a function that acts like a tree destructor function.
Login name: __________________
Midterm #2 Spring 1994, 61B 1
Problem 1 (4 points, 8 minutes)
Write a recursive function that, given a pointer to a Tree object, deletes the object and every object in the tree’s subtrees. You may but need not code this as a destructor for the Tree class.
Also indicate what changes to the Tree class definition are necessary for your function to compile without errors.
Problem 2 (4 points, 8 minutes)
Your lab partner proposes a nonrecursive implementation of the function described in problem 1. It’s called DeleteAll and uses a generator for tree elements along with the Set class from homework assignment *.
Set generatorSaveSet;
void Tree::InitGenerator ( ) { generatorSaveSet.Add (this);
}
Tree* Tree::Next ( ) {
if (generatorSaveSet.Empty ( ) ) { return NULL;
} else {
Tree* t = generatorSaveSet.Remove ( ); if (t->right) {
generatorSaveSet.Add (t->right); }
return t; }
}
void Tree::DeleteAll ( ) {
Tree* tToDelete; InitGenerator ( );
while (tToDelete = Next ( ) ) { delete tToDelete;
} }
midterm
Problem 1 (4 points, 8 minutes) 2
Your labe partner claims that the DeleteAll function will successfully delete
all objects in the teree for either implementation of a Set used in homework assignment 8, i.e. for either a queue or a stack. Evaluate these claims.
Part a
Suppose that generatorSaveSet is maintainded as a queue. Will the DeleteAll function successfully delete the tree object and the tree objects in its subtees? Briefly explain.
Part b
Suppose that generatorSaveSet is maintained as a stack. Will the DeleteAll function successfully delete the tree object and the tree objects in its subtrees? Briefly explain.
Problem 3 (8 minutes, 6 points)
First Cousins are family members with different parents buy the same grandparents. In the portion of the Kennedy family tree shown below, there are four pairs of first cousins:
Kathleen and Caroline Kathleen and John Jr. Robert Jr and Caroline Robert Jr. and John Jr.
Joseph
Kennedy Fitzgerald
|____________________________________| ____________|_____________ ||
Grandparents
Children + spouses
Grandchildren
Jacqueline John Bouvier Kennedy
|___________|
_______|__________ ||||
Caroline John Kathleen Robert Kennedy Kennedy Jr. Kennedy Kennedy Jr.
Part a
Complete the FamilyMember class definition below to produce a data structure for storing (human) family members in which, given p1 and p2 of
type FamilyMember*, you can determine in constant time if p1 and p2 represent family members who are first cousins. It may be the case that the parents or
Problem 2 (4 points, 8 minutes)
3
midterm
Robert Kennedy
Ethel Skakel
Rose
|_____________| ______|______
grandparents of a given family member are not known; indicate via a comment in the class definition what would be stored in the FaimilyMember object in that case.
Assume that each family member has (possibly unkown) parents. Also assume that if two family members represented in the structure have the same mother, they have the same father as well, and vice-versa.
class FamilyMember { private:
public:
Boolean AreCousins (FamilyMember* p1, FamilyMember* p2);
};
What is the maxumum number of comparisons required to determine first-cousinhood using your class definition? (Comparison of pointers to NULL should be included in your count.) Justify your answer.
Posted by HKN (Electrical Engineering and Computer Science Honor Society) University of California at Berkeley
If you have any questions about these online exams please contact examfile@hkn.eecs.berkeley.edu.
Part b
midterm
Problem 3 (8 minutes, 6 points)
4