PART I: Short Response

Directions: Answer each of the following questions. Please ensure that your responses are at least 3 to 5 sentences in length.

1. A function int MaxStack (stackclass S); will return the largest value in an ADT stack of integers. Write the code for this function. Note: your function will be a client of the ADT, not a part of it, so you must use the ADT operations to access the stack. You can assume the copy constructor for the stack has been implemented.

2. Suppose you are asked to create a new method for the stack class, PopN, defined as follows:

PopN(S, n)

{ Removes from stack S the n number of items that were
most recently added. It is an error if there are
fewer than n items on S. }

To implement this operation, you could either modify the stack directly or use the existing Pop operation. What would be the advantages and disadvantages of each method?

3. Write a code segment using class queueClass that creates a queue of the integers 1-5.

4. Write a member function called Display that displays the elements of an object of type queueClass. Assume the pointer-based queue is in use, and note that you are writing a member function of the class, so you have access the private data members.

5. What is the difference between a time-driven simulation and an event-driven simulation?

6. Consider class wheel and class automobile. An automobile has-a wheel. Write a class relationship between these classes that reflects this relationship. Details of other members are not important.

7. Why are constructors not inherited?

8. What is a virtual function? What is its purpose?

9. What is the difference between a virtual and a pure virtual function? What is an abstract class, and what is its purpose?

10. The approximate number of iterations of an algorithm with data size N is determined to be:

1 + 2 + 3 + ... + N

a. Write a table that shows N and the number of iterations for the first 10 values of N.
b. What is the O-notation for this algorithm?

11. The best and worst case performances of MergeSort are the same, while for QuickSort the best and worst cases widely differ. Explain why.

12. Given the ADT binary tree operations defined in this chapter, draw the tree or trees produced by the following sequence of statements:

typedef int treeItemType;
binTreeClass R, S;

S.SetRootData(10);
S.AttachLeft(5, Success);
S.AttachRight(6, Success);
S.LeftSubtree().AttachRight(2, Success);
S.LeftSubtree().RightSubtree().AttachLeft(20, Success);
S.LeftSubtree().RightSubtree().AttachRight(15, Success);
S.RightSubtree().AttachRight(13, Success);
R.SetRootData(1);
R.AttachRight(8, Success);

binTreeClass T(9, S, R);

13. Suppose the following values are to be inserted into a binary search tree:

A, B, C, D, E, F, G

Inserting the values in different orders results in different shapes of trees. What ordering results in an optimal (complete) tree? Show the resulting tree.

14. Explain how a stack could be used to completely search a graph without using recursion.