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

1. Enter the
values that will be in the linked list of integers, and draw the links
(arrows), of a **stack**
after the following operations are executed.
(6 points)

push 15

push 10

pop

push 23

push 6

pop

push 22

2. Enter the
values that will be in the linked list of integers, and draw the links
(arrows), of a **queue**
after the following operations are executed.
(6 points)

enqueue 15

enqueue 10

dequeue

enqueue 23

enqueue 6

dequeue

enqueue 22

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:

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

How many ** nodes** are in the tree? (2
points)

** List** the

Name the ** children** of node X: (2
points)

Name the ** parent** of node X: (2 points)

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

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

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

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

** Sum** (non-recursive) has no
parameters and returns the sum of the integers in the stack. Therefore, it will have

** RecursiveSum** (recursive) will work exactly
like

** TakeMeOut** (non-recursive) will take
an integer as a parameter, locate the first node in the stack that has that
value, and remove it from the stack. It
will return false if the value is not found in the stack, true otherwise. Therefore, it will have

(a)** Begin by indicating the
changes that need to be made to the class declaration**: (8 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 Sum**: (10 points)

(repeated for your convenience)

** Sum** (non-recursive) has no
parameters and returns the sum of the integers in the stack. Therefore, it will have

(c) ** Write the member function
definition for RecursiveSum**: (10 points)

(repeated for your convenience)

** RecursiveSum** (recursive) will work
exactly like

(d) ** Write the member function
definition for TakeMeOut**: (20 points)

(repeated for your convenience)

** TakeMeOut** (non-recursive) will take
an integer as a parameter, locate the first node in the stack that has that
value, and remove it from the stack. It
will return false if the value is not found in the stack, true otherwise. Therefore, it will have

9. ** Use code tree.h
as a reference**.

** NumberOfLeaves** (recursive) will determine the
number of leaves in the tree. Therefore,
it will have