**CPTR246 Spring '02 (**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.
(5 points)

push 12

push 45

push 33

pop

push 1

pop

push 16

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.
(5 points)

enqueue 12

enqueue 45

enqueue 33

dequeue

enqueue 1

dequeue

enqueue 16

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

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

5. Consider the
following linked list of integers (** sorted from lowest to highest**)
and the changes described. Make the
necessary changes in the drawing to indicate what must change in the linked
list for each change described. (16
points)

(a) Add integer
65
(b) Add integer 30

(c)
Remove integer 25
(d) Remove integer 16

6. Answer the
following questions regarding this tree:

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

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

**List** the ** leaves** in the tree. (2 points)

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

Name the ** parent** of node k: (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 ** depth-first
(preorder) search**: (3 points)

7. ** Recursion**:

·
Write a ** recursive
function** named

Base case: compute(0)
= 3

General case: compute(n)
= (2 * compute(n-1)) – 1

·
What would be returned by the function call compute(3)? (6 points – show your work for partial
credit)

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

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

** TakeTwo** will work like

** MoveToTop** will take an integer as a
parameter, locate the first node in the stack that has that value, and move it
to the top of 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 what changes need to
be made to the class declaration**: (6 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 Count**: (10 points)

(repeated for your convenience)

** Count** takes no parameter and
returns the number of integers in the stack.
Therefore, it will

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

(repeated for your convenience)

** TakeTwo** will work like Pop except
that instead of taking the first entry in the stack, it will take the first two
entries in the stack,

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

(repeated for your convenience)

** MoveToTop** will take an integer as a
parameter, locate the first node in the stack that has that value, and move it
to the top of the stack. It will return
false if the value is not found in the stack, true otherwise. Therefore, it will have