CIS C++ Need done today

• 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.

• 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?

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

• 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.

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

• 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.

• Why are constructors not inherited?

• What is a virtual function? What is its purpose?

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

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

1 + 2 + 3 + ... + N

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

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

• 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);

• 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.

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