Name ___________________

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

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 compute that takes an integer greater than or equal to 0 and returns an integer, given the following base and general cases. (10 points)

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. Write the following three new member functions:

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

TakeTwo will work like Pop except that instead of removing the first entry from the stack and putting it in the single call-by-reference parameter, it will remove the first two entries from the stack, using two call-by-reference parameters. It therefore has two parameters, and it is to return a boolean, false if there are less than two entries on the stack, true otherwise.

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 one parameter and returns a boolean.

(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 take no parameter and returns an integer.

(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, using two call-by-reference parameters. It therefore has two parameters, and it is to return false if there are less than two entries on the stack, true otherwise.

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

(repeated for your convenience)