Name ___________________

CPTR246 Spring '11 (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 4

push 8

pop

push 9

pop

push 3

push 7

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 4

enqueue 8

dequeue

enqueue 9

dequeue

enqueue 3

enqueue 7

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

Name the parent of node K: (2 points)

List the nodes as they would be processed in a breadth-first search: (2 points)

List the nodes as they would be processed in a preorder traversal: (2 points)

List the nodes as they would be processed in an inorder traversal: (2 points)

List the nodes as they would be processed in a postorder traversal: (2 points)

8. Use code IntegerNode.h and IntegerLinkedList2.h as a reference. Write the following two new member functions:

HowManyOfThese is to take an integer as a parameter and is to return the number of times that integer appears in the linked list. Therefore, it will have one parameter and return an integer. Assume the nodes in the linked list are in no particular order. If the linked list is empty, return a 0. (12 points)

MoveToTheTop will take an integer as a parameter, locate the first node in the linked list that has that value, and move it to the top of the linked list. It will return false if the value is not found in the linked list, true otherwise. Therefore, it will have one parameter and return a boolean. (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 HowManyOfThese: (12 points)

(repeated for your convenience)

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

HowManyOfThese (recursive) will take an integer as a parameter and return the number of times that the integer appears in the tree. Therefore, it will have one parameter and return an integer. Assume the nodes in the tree are in no particular order. If the tree is empty, return a 0.

DepthOfNode (non-recursive and assuming that the tree is a 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) will 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 HowManyOfThese on this page and DepthOfNode on the following page.)

(repeated for your convenience)