Name ____________________________

CPTR246 Spring '08 Part 1 (40 of 100 total points) Exam 3

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

2. Which data structure is FIFO, stack or queue? (2 points)

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

4. Which data structure is LIFO, stack or queue? (2 points)

5. 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 22

push 13

pop

push 16

pop

push 19

push 6

6. 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 22

enqueue 13

dequeue

enqueue 16

dequeue

enqueue 19

enqueue 6

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

Name the parent of node 12: (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)

Name ____________________________

CPTR246 Spring '08 Part 2 (60 of 100 total points) Exam 3

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

Below takes one integer parameter and returns the number of nodes in the stack whose value is less than (that is, strictly less than, not less than or equal to) the parameter. It therefore has one parameter, and it is to return an integer.

Change takes two integer parameters and is to locate every occurrence of the first parameter in the stack and replace its value with that of the second parameter. If the first parameter is not found in the stack, return false; otherwise, return true. Therefore, this function will have two parameters and it is to return a boolean.

PushDownOne takes one integer parameter. If that integer is not in the stack, return false. If it is the last integer in the stack, return false. Otherwise, move this node down one position in the stack. For example, if the stack myStack contains “1 2 3 4” and we call myStack.PushDownOne(2), the stack would be modified to contain “1 3 2 4”. The method will have one 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 Below: (12 points)

(repeated for your convenience)

Change takes two integer parameters and is to locate every occurrence of the first parameter in the stack and replace its value with that of the second parameter. If the first parameter is not found in the stack, return false; otherwise, return true. Therefore, it will have two parameters and it is to return a boolean.

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

(repeated for your convenience)

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

Using the special structure of the binary search tree (that is, all nodes in the left subtree have values less than the current node and all nodes in the right subtree have values greater than or equal to the current node), write the non-recursive member function InTreeDirect that, like its recursive version InTree, will determine whether or not an integer, passed as a parameter, is in the tree. Therefore, the function will have one parameter and return a boolean. HINT: Use the special structure of the binary search tree, as we did for DeleteLeaf, to locate the node.