**CPTR246
Spring**** '08 Part 1 ****(**40 of 100
total points)**
Exam 3**

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

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

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

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

5. ** Enter the values** and

push 22

push 13

pop

push 16

pop

push 19

push 6

6. ** Enter the values** and

enqueue 22

enqueue 13

dequeue

enqueue 16

dequeue

enqueue 19

enqueue 6

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)

**CPTR246
Spring**** '08 Part 2 **(60 of 100 total points)** Exam 3**

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

** Below** takes one integer parameter
and returns the number of nodes in the

** Change** takes two integer
parameters and is to locate

** PushDownOne** takes one integer
parameter. If that integer is not in the
stack, return

(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 Below**:
(12 points)

(repeated for your convenience)

** Below** takes one integer parameter
and returns the number of nodes in the

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

(repeated for your convenience)

** Change** takes two integer
parameters and is to locate

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

(repeated for your convenience)

** PushDownOne** takes one integer
parameter. If that integer is not in the
stack, return

9.
** Use code tree.h
as a reference. Write the following new
member function:** (15 points)

Using the special structure of the binary search
tree (that is,
all nodes in the left subtree have values less than the current node and all
nodes in the right subtree have values greater than or equal to the current
node), write
the __non-recursive__ member function ** InTreeDirect** that, like
its recursive version