**CPTR246 Spring '07 (**100 total points)**
Exam 3**

1. ** Enter the values** and

push 34

push 24

push 19

pop

push 30

pop

push 33

2. ** Enter the values** and

enqueue 34

enqueue 24

enqueue 19

dequeue

enqueue 30

dequeue

enqueue 33

3. What does the acronym LIFO
stand for? (2 points)

4. Which data structure is
LIFO, stack or queue? (2 points)

5. What does the acronym FIFO
stand for? (2 points)

6. Which data structure is
FIFO, stack or queue? (2 points)

7. Answer the following questions regarding this
tree:

Is this a ** binary tree**? (2 points)

What is the ** root**? (2 points)

** List** the

What is the ** height** of the tree? (2 points)

** Name** the

** Name** the

List the nodes as they would be visited in a ** breadth-first
search**: (2 points)

List the nodes as they would be visited in a ** preorder
traversal**: (2 points)

List the nodes as they would be visited in an ** inorder
traversal**: (2 points)

List the nodes as they would be visited in a ** postorder
traversal**: (2 points)

8. ** Use code stack.h
as a reference**.

** HowManyEvens** has no parameters and
returns the number of even integers in the stack. Therefore, it will have

** PopTwo** will work like

** RemoveLast** will find the last entry on
the stack, put it in the single call-by-reference parameter, and then remove it
from the stack. It will return false if
the stack is empty, true otherwise.
Therefore, it will have

(a)** Begin by indicating the
changes that need to be made to the class declaration**: (9 points)

class
Stack {

public: //
see function def's for pre and post

Stack() { top = 0;}

~Stack();

bool IsEmpty() {return (top == 0);}

bool IsFull();

bool Peek(int & x);

void Push(int x);

bool Pop(int & x);

void Display();

private:

Node * top; // points to the first Node in the stack

};

*Use the following three
pages to code the functions.*

(b) ** Write
the member function definition for HowManyEvens**: (12 points)

(repeated for your convenience)

** HowManyEvens** has no parameters and
returns the number of even integers in the stack. Therefore, it will have

(c) ** Write the member function
definition for PopTwo**: (12 points)

(repeated for your convenience)

** PopTwo** will work like

(d) ** Write the member function
definition for RemoveLast**: (12 points)

(repeated for your convenience)

** RemoveLast** will find the last entry on
the stack, put it in the single call-by-reference parameter, and then remove it
from the stack. It will return false if
the stack is empty, true otherwise.
Therefore, it will have

9.

** HowManyEvens** will determine the number
of even integers in the tree. Therefore,
it will have