Name ___________________

CPTR246 Spring '04 (100 total points) Exam 3

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

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

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

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

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

push 9

push 5

pop

push 3

push 12

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

enqueue 9

enqueue 5

dequeue

enqueue 3

enqueue 12

7. Answer the following questions regarding this tree:

Is this a binary search tree? (yes or no) (2 points)

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

Name the parent of node 16: (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 IntegerNode.h and IntegerLinkedList2.h as a reference. Write the following two new member functions:

Largest has no parameters and returns the largest integer in the linked list. Assume the nodes in the linked list are in no particular order. If the linked list is empty, return a 0. Therefore, it will have no parameters and return an integer. (12 points)

SendToEnd will take the first node in the linked list and move it to the end of the list. It will return false if the list is empty, true otherwise. Therefore, it will have no parameters and return a boolean. Be sure to handle all possible cases. (12 points)

(a) Begin by indicating the changes that need to be made to the class declaration: (6 points)

class IntegerLinkedList{

public:

IntegerLinkedList();

bool Load(char * filename);

void Display();

bool IsThere(int whichOne);

bool InsertNode(int newValue);

bool RemoveNode(int whichOne);

private:

IntegerNode * first;

IntegerNode * last;

};

Use the following two pages to code the functions.

(b) Write the member function definition for Largest: (12 points)

(repeated for your convenience)

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

IncrementBy (recursive) will take an integer as a parameter and add that value to every node in the tree. Therefore, it will have one parameter and return nothing.

DepthOfNode (non-recursive) will (assuming that the tree is a binary search tree) take an integer as a parameter, locate it in the tree, and return the value of the depth of that node. (Recall that the depth of the node is the number of edges from the root to the node. E.g., the depth of the root is 0, the depth of the root’s children is 1, etc.) If the node is not in the tree, return -1. Therefore, it will have one parameter and return an integer.

(Code IncrementBy on this page and DepthOfNode on the following page.)

(repeated for your convenience)