Name ___________________

CPTR246 Spring '12 (100 total points) Exam 3

1. Linked Lists – Consider the following linked list of integers (sorted from lowest to highest) and the changes described. Make the necessary changes in the drawing to indicate what must change in the linked list for each change described. (9 points)

(a) Add integer 12 (b) Add integer 28

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

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

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

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

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

push 12

push 5

pop

push 9

pop

push 6

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

enqueue 12

enqueue 5

dequeue

enqueue 9

dequeue

enqueue 6

8. 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 N: (2 points)

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

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

HowManyPositives is to return the number of integers in the linked list that are positive (that is, strictly greater than 0). Therefore, it will have no parameters 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. (10 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. (10 points)

(a) Begin by indicating the changes that need to be made to the class declaration: (5 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 HowManyPositives: (10 points)

(repeated for your convenience)

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

HowManyPositives (recursive) will return the number of integers in the tree that are positive (that is, strictly greater than 0). Therefore, it will have no parameters and return an integer. Assume the nodes in the tree are in no particular order. If the tree is empty, return a 0.

InTreeDirect (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 and attempt to locate it in the tree. It will return true if it finds the value and false otherwise. Therefore, it will have one parameter and return a boolean.

(Code HowManyPositives on this page and InTreeDirect on the following page.)

(repeated for your convenience)