Sample Exam
Please answer all questions. Open Book, open notes. Fill in the blanks, answering the questions when asked.
1. (10) Referring to the design of the C++ Heterogeneous Containers Class Library discussed in class, give the best justification for each of the following:
entity class is provided
_____________________________________________________________
_____________________________________________________________
entity::equal is virtual
_____________________________________________________________
_____________________________________________________________
container class is derived from entity class
_____________________________________________________________
_____________________________________________________________
element class is defined
_____________________________________________________________
_____________________________________________________________
pair class is defined
_____________________________________________________________
_____________________________________________________________
2.(10) In each case below circle the best class to use as a base class for the derived class on the left. Give a reason for each choice you make.
table of square roots bag set relation function __________ _____________________________________________________________ ______________________________________________________________________ telephone book bag set relation function _______________________________________________________________________ _______________________________________________________________________ employee records bag set relation function _______________________________________________________________________ _______________________________________________________________________ games played by all college football bag set relation function teams in 1994 (e.g. game = arizona vs asu) _______________________________________________________________________ _______________________________________________________________________3. (45) Recall that a stack object behaves as a stack of trays would: the last tray pushed on the stack is the one on the top and the one that is removed by the pop command. In contrast a queue object behaves like a line in a bank where the front customer is the one that is removed and the customers are added in the order of arrival.
constructor
stack make-stack()
queries
number size?(stack)
entity top?(stack)
commands
stack' pop(stack)
stack' push(stack,entity)
Domain Restrictions
top?(stack) = defined provided that size?(stack) > 0
pop(stack) = defined provided that size?(stack) > 0
a) (5) Fill in in the RHS of each of the following:
Equivalences
size?(make-stack()) = __________________________________
top?(make-stack()) = __________________________________
size?(push(stack,entity)) = __________________________________
top?(push(stack,entity)) =________________________________
size?(pop(stack)) = __________________________________
b) (5) Show that:
top?(push(pop(stack),top?(stack))) = top?(stack)
(where size?(stack)> 0)
by completing the following simulation:
entity = top?(stack)
stack' = pop(stack)
__________________________________
__________________________________
__________________________________
__________________________________
c) (10) We are going to implement the class stack as a derived class of list and class queue as a derived class of stack. These classes should provide direct user access to all public members inherited from list but not to any private or protected ones. Class queue should not provide direct user access to any new methods defined for stack.
class list{
......
public:
list();
void insert(entity * e, int i);
void remove(int i);
entity * list_ref(int i);
int size();
};
Fill in the required code:
class stack:______ list{
//tell why you chose one of (public,private,protected}
_______________________________________
_______________________________________
______ :
//tell why you chose one of (public,private,protected}
_______________________________________
_______________________________________
void pop(){
_______________________________________
_______________________________________
}
void push(entity * e){
_______________________________________
_______________________________________
}
entity * top(){
_______________________________________
_______________________________________
}
d) (5) Write the following test for the stack implementation:
main(){
_____________________________________ //make an entity instance
_____________________________________ //make a stack instance
_____________________________________ // push an entity
_____________________________________ // if top returns
// the same entity the test is satisfied
_____________________________________ // otherwise, the test is not
satisfied
}
e) (5) Use the equivalence derived in b) above to write another test
for the stack implementation:
main(){
_______________________________________
_______________________________________
_______________________________________
_______________________________________
_______________________________________
_______________________________________
_______________________________________
_______________________________________
}
f) (5) FIll in the missing parts in the specification of queue:
constructor
______ make-queue()
queries
number size?(queue)
______ front?(queue)
commands
______ ' remove(queue)
______ ' add(queue,entity)
Domain Restrictions
front?(queue) = defined provided that ______
______(queue) = defined provided that ______
g) (10) Fill in the code required to derive queue from stack:
class queue:______ stack{
//tell why you chose one of (public,private,protected}
_______________________________________
_______________________________________
______ :
//tell why you chose one of (public,private,protected}
_______________________________________
_______________________________________
void remove(){
_______________________________________
_______________________________________
}
void add(entity * e){
_______________________________________
_______________________________________
}
entity * front(){
_______________________________________
_______________________________________
}
5. (17) In the following class hierarchy, a figure is the base class for atomic and composite classes. An atomic figure is a geometrical shape such as a rectangle or circle. A composite figure has container called components whose items are other figures. Every figure has a center which is a point (assume point is an existing class). Rectangles (and other classes not shown) have an outline, which is a list of points which form their outlines when connected. Every figure also has two methods: move and draw. In the following diagram there are enough slots for all the mentioned instance variables and methods. However, many of these may be inherited without modification. Fill in the names of the instance variables and methods in the proper slots only if they cannot be inherited. Also provide the prototypes of these members as they would appear in C++. Be sure to mark any slots that need to be declared virtual in order for the methods of figure to work properly. Provide an explanation for any choices you make that might be controversial.
entity instance variable: instance variable: method: method: figure instance variable: instance variable: method: method: atomic instance variable: instance variable: method: method: rectangle instance variable: instance variable: method: method: circle instance variable: instance variable: method: method: composite instance variable: instance variable: method: method:Extra credit (5): Will be added in to total but does not subtract from total.
Define the move and draw methods for composite figures.
6. An investment company has created the following class hierarchy:
entity investment get_value() set_value() stock bond bank_accountUsing Ensemble methods write the following:
show_all_investments(){
________________________________________________________________
________________________________________________________________
}
show_all_stocks(){
________________________________________________________________
________________________________________________________________
}
Investors purchase individual stocks, bonds or bank accounts, and place these objects in sets called portfolios. In other words, portfolio is derived from set:
Using Ensemble methods, define the following:
set * portfolio::get_investments_greater_than (n){
// returns the subset all investment objects in portfolio with value greater than n
________________________________________________________________
________________________________________________________________
}
void portfolio::deduct_charges(){
// decreases value of each investment object in portfolio by
// calling each investment's method deduct_charges
_________________________________________________________________
_________________________________________________________________
)
Define the investment methods assumed in the above:
boolean investment::greater_than (n){
_________________________________________________________________
_________________________________________________________________
}
void investment::deduct_charges(){
//reduces value by an amount determined differently in each subclass
// default is reduction by %5
_________________________________________________________________
_________________________________________________________________
}
void stock::deduct_charges(){
_________________________________________________________________
_________________________________________________________________
}
void bond::deduct_charges(){
_________________________________________________________________
_________________________________________________________________
}
void bank_account::deduct_charges(){
_________________________________________________________________
_________________________________________________________________
}