Name ___________________

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 leaves in the tree. (3 points)

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

Sum (non-recursive) has no parameters and returns the sum of the integers in the stack. Therefore, it will have no parameters and return an integer. (10 points)

RecursiveSum (recursive) will work exactly like Sum, however it will be implemented recursively. (10 points)

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 one parameter and return a boolean. (20 points)

(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 no parameters and return an integer.

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

(repeated for your convenience)

RecursiveSum (recursive) will work exactly like Sum, however it will be implemented recursively. It has no parameters and returns the sum of the integers in the stack. Therefore, it will have no parameters and return an integer.

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

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

NumberOfLeaves (recursive) will determine the number of leaves in the tree. Therefore, it will have no parameters and returns an integer.