COS30008 Subject Title: Data Structures & Patterns

COS30008 Semester 1, 2020 Dr. Markus Lumpe
Engineering and Technology
FINAL EXAM COVER SHEET
Subject Code: COS30008
Subject Title: Data Structures & Patterns
Due date: June 24, 2020, 20:59
Lecturer: Dr. Markus Lumpe
Your name: Your student id:
Check
Tutorial
Mon
14:30
Tues
08:30
Tues
10:30
Tues
12:30
Tues
14:30
Wed
08:30
Wed
10:30
Wed
12:30
Wed
14:30
Thurs
08:30
Marker’s comments:
Problem Marks Obtained
1 – TTree 104
2 – traversDepthFirst 14
3 – LinearVisitor 16
4 – Knowledge Questions 20
Total 154
This test requires approx. 2 hours and accounts for 50% of your overall mark.
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 2 of 9
Problem 1 (104 marks)
We wish to define a generic 3-ary tree in C++. We shall call this data type TTree. A 3-ary
tree has a key fKey and three nodes fLeft, fMiddle, and fRight. Following the principles
underlying the definition of general trees, a 3-ary tree is a finite set of nodes and it is either
• an empty set, or
• a set that consists of a root and exactly 3 distinct 3-ary subtrees.
Somebody has already started with the implementation and created the header file TTree.h,
but left the project unfinished. Complete the following code fragments. In particular, make
sure that all elements are properly defined and no linker errors occur.
#pragma once
#include
template
class TTree
{
private:

T fKey;
TTree* fLeft;
TTree* fMiddle;
TTree* fRight;

TTree() : fKey() // use default constructor to initialize fKey
{
fLeft = &NIL; // loop-back: The sub-trees of a TTree object with
fMiddle = &NIL; // no children point to NIL.
fRight = &NIL;
}

void addSubTree( TTree** aBranch, const TTree& aTTree )
{
if ( *aBranch != &NIL )
{
delete *aBranch;
}
*aBranch = (TTree*)&aTTree;
}
void removeSubTree( TTree** aBranch ); // 14 marks

public:
static TTree NIL; // sentinel // 5 marks
// TTree constructor (takes one argument) // 8 marks
TTree( const T& aKey );

// destructor (free sub-trees, must not free empty TTree) // 15 marks
~TTree();

// copy constructor, must not copy empty TTree // 20 marks
TTree( const TTree& aOtherTTree );

// assignment operator, must not copy empty TTree // 20 marks
TTree& operator=( const TTree& aOtherTTree );

// clone TTree, must not copy empty TTree // 12 marks
TTree* clone() const;
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 3 of 9
// return key value, may throw domain_error if empty // 6 marks
const T& getKey() const;
// returns true if this TTree is empty // 4 marks
bool isEmpty() const;

// getters for subtrees
const TTree& getLeft() const
{
return *fLeft;
}

const TTree& getMiddle() const
{
return *fMiddle;
}

const TTree& getRight() const
{
return *fRight;
}
// add a subtree
void addLeft( const TTree& aTTree )
{
addSubTree( &fLeft, aTTree );
}

void addMiddle( const TTree& aTTree )
{
addSubTree( &fMiddle, aTTree );
}

void addRight( const TTree& aTTree )
{
addSubTree( &fRight, aTTree );
}

// remove a subtree, may through a domain error
const TTree& removeLeft()
{
return removeSubTree( &fLeft );
}

const TTree& removeMiddle()
{
return removeSubTree( &fMiddle );
}

const TTree& removeRight()
{
return removeSubTree( &fRight );
}
};
The class TTree is rather complex and uses explicit pointers to its three subtrees: fLeft,
fMiddle, and fRight. To facilitate adding and removing subtrees, the class TTree defines
two private methods, addSubTree and removeSubTree, which, in the first argument, take
a pointer to the branch being altered (a pointer to a pointer of TTree). So, the methods
addSubTree and removeSubTree receive the address of the subtree member to be
updated. We have seen this concept previously, while building a singly-linked list in class.
Unfortunately, only addSubTree has been implemented. Use the available information to
implement removeSubTree also. The method removeSubTree has to guarantee that
empty trees are not removed. In this case, removeSubTree has to throw a domain error. If
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 4 of 9
the subtree can be removed, then a constant reference to it must be returned. In addition,
the pointer of the subtree being removed must be set the address of NIL to indicate that this
branch is now empty.
Class TTree has to implement proper copy semantics. For this reason, it must define a
destructor, a copy constructor, and an assignment operator. In addition, we require a clone
method to easily duplicate whole TTrees. The copy semantics and clone must not create
copies of NIL. If NIL is encountered in the copy constructor or assignment operator, then a
domain error must be thrown. The method clone can easily prevent copies of NIL by returning
the this object. You may need to apply suitable casts where necessary to make the
implementation compile.
To create TTree objects, we need to define its constructor. There are two service functions:
getKey and isEmpty that return the payload of the TTree object and test whether the
current TTree object is the empty tree, respectively.
Finally, remember the specific C++ requirements to initialize a static member variable.
You can use the following test driver to verify your implementation:
string s1( “A” );
string s2( “B” );
string s3( “C” );
string s4( “D” );
TTree treeA( s1 );
TTree* treeB = new TTree( s2 );
TTree* treeC = new TTree( s3 );
TTree* treeD = new TTree( s4 );
cout << “The payload of treeA: ” << treeA.getKey() << endl;

try
{
treeA.getMiddle().getKey();

cout << “You should not see this output.” << endl;
}
catch (domain_error e)
{
cout << “Exception: ” << e.what() << endl;
}

treeA.addLeft( *treeB );
treeA.addMiddle( *treeC );
treeA.addRight( *treeD );
cout << “Trees attached” << endl;
cout << “Use copy constructor.” << endl;
try
{
TTree No = treeA.getLeft().getLeft();

cout << “You should not see this output.” << endl;
}
catch (domain_error e)
{
cout << “Exception: ” << e.what() << endl;
}

TTree tree_copy = treeA;
TTree B( tree_copy );
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 5 of 9
cout << “Copy constructors used.” << endl;
cout << “Use assignment operator.” << endl;
try
{
B = treeA.getLeft().getLeft();

cout << “You should not see this output.” << endl;
}
catch (domain_error e)
{
cout << “Exception: ” << e.what() << endl;
}
const TTree* lRight = &treeA.getRight();
B = treeA;

if ( &B.getRight() != lRight )
{
cout << “You should not see this output.” << endl;
}
cout << “Assignment operator used.” << endl;

const TTree* lLeft = &B.getLeft();
B = B;
if ( &B.getLeft() != lLeft )
{
cout << “You should not see this output.” << endl;
}

cout << “Self assigned used.” << endl;
This code should produce an output similar to the following:
The payload of treeA: A
Exception: Empty TTree encountered.
Trees attached
Use copy constructor.
Exception: Copying NIL.
Copy constructors used.
Use assignment operator.
Exception: Copying NIL.
You should not see this output.
Assignment operator used.
Self assigned used.
No error should occur at the end.
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 6 of 9
Problem 2 (14 marks)
Consider the following visitor class.
#pragma once
#include
template
class TreeVisitor
{
public:
virtual ~TreeVisitor() {} // virtual default destructor
// default behavior
virtual void preVisit( const T& aKey ) const {}
virtual void postVisit( const T& aKey ) const {}
virtual void inVisit( const T& aKey ) const {}
virtual void visit( const T& aKey ) const
{
std::cout << ” ” << aKey;
}

void emitNIL() const
{
std::cout << ” []”;
}
};
Assume that the 3-ary tree TTree is fully functional.
We now wish to add a depth-first traversal facility to TTree. The corresponding method
signature is
void traverseDepthFirst( TreeVisitor& aVisitor ) const;
Depth-first traversal for 3-ary trees first checks that the current tree node is not empty. If this
is the case, then we need to perform three steps:
• Visit the current node using pre-order mode,
• Traverse all sub-tree nodes of the current TTree node, and
• Visit the current node using post-order mode.
On empty tree nodes, just invoke the aVisitor’s emitNIL method.
There is no test yet. To test the implementation, proceed with Problem 3.
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 7 of 9
Problem 3: (16 marks)
Using the TreeVisitor shown in Problem 2 as super class, define a class LinearVisitor
that overrides the methods preVisit and postVisit:
• preVisit has to output string “ [” first and then calls visit with aKey
• postVisit has to output string “ ]”
The following test driver allows you to verify your implementation of both TTree’s
traversDepthFirst method and class LinearVisitor:
string s1( “A” );
string s2( “B” );
string s3( “C” );
string s4( “D” );
string s5( “E” );
string s6( “F” );
TTree treeA( s1 );
TTree* treeB = new TTree( s2 );
TTree* treeC = new TTree( s3 );
TTree* treeD = new TTree( s4 );
TTree* treeE = new TTree( s5 );
TTree* treeF = new TTree( s6 );
treeA.addLeft( *treeB );
treeA.addMiddle( *treeC );
treeA.addRight( *treeD );
((TTree&)treeA.getLeft()).addMiddle( *treeE );
((TTree&)treeA.getRight()).addMiddle( *treeF );

LinearVisitor lVisitor;

cout << “Visitor test:”;

treeA.traverseDepthFirst( lVisitor );

cout << endl;
This code should produce an output similar to the following:
Visitor test: [ A [ B [] [ E [] [] [] ] [] ] [ C [] [] [] ] [ D [] [ F [] [] [] ] [] ] ]
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 8 of 9
Problem 4 (20 marks)
Answer the following questions in one or two sentences:
a. How can we avoid aliases to objects?
4a)
b. What are the elements of proper copy control in C++?
4b)
c. What is the difference between a stack and a queue?
4c)
d. Why can we locate, on average, an element in a binary tree faster than in an array?
4d)
e. Explain briefly the concept of abstract data type.
4e)
COS30008 Semester 1, 2020 Dr. Markus Lumpe
Final Online Exam, Semester 1 2020 Page 9 of 9
f. It is safe to return references to local variables from a function, or not? Elaborate
briefly.
4f)
g. What is the purpose of the Visitor pattern?
4g)
h. Is quick sort always faster than bubble sort? Explain briefly.
4h)
i. What is required to test the equivalence of iterators?
4i)
j. When do we need to implement a state machine?
4j)