Name ____________________________

CPTR246 Spring '07 (100 total points) Exam 3

1. Enter the values and draw the links (arrows) for the linked list of integers of a stack after the following operations are executed. (6 points)

push 34

push 24

push 19

pop

push 30

pop

push 33

2. Enter the values and draw the links (arrows) for the linked list of integers of a queue after the following operations are executed. (6 points)

enqueue 34

enqueue 24

enqueue 19

dequeue

enqueue 30

dequeue

enqueue 33

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:

Is this a binary tree? (2 points)

What is the root? (2 points)

List the leaves in the tree. (2 points)

What is the height of the tree? (2 points)

Name the children of node G: (2 points)

Name the parent of node G: (2 points)

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)

8. Use code stack.h as a reference. Write the following three new member functions:

HowManyEvens has no parameters and returns the number of even integers in the stack. Therefore, it will have no parameters and it is to return an integer. (Hint: An integer is even if you divide it by 2 and there is no remainder – think %, the mod/remainder operator.)

PopTwo 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.

RemoveLast will find the last entry on the stack, put it in the single call-by-reference parameter, and then remove it from the stack. It will return false if the stack is empty, true otherwise. Therefore, it will have one call-by-reference parameter and return a boolean.

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

(repeated for your convenience)

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

(repeated for your convenience)

HowManyEvens will determine the number of even integers in the tree. Therefore, it will have no parameters and returns an integer. (Note: Write both the recursive function and its helper function.)