Name ___________________

CPTR246 Spring '13 (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 31 (b) Add integer 61

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


(c) Add integer 11

 

 



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 9

push 8

pop

push 2

push 4

push 7

pop

 

 

 

 

 

 

 

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 9

enqueue 8

dequeue

enqueue 2

enqueue 4

enqueue 7

dequeue

 

 

 

 

 


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

 

 

 

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

 

HowManyBelow takes an integer as a parameter and is to return the number of integers in the linked list that are strictly less than (meaning less than but not equal to) the number passed as a parameter. 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. (10 points)

 

MoveToTheEnd will move the first node in the linked list to the end of the linked list. It will return false if the linked list is empty, true otherwise. Therefore, it will have no parameters 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 HowManyBelow:

 

(repeated for your convenience)

HowManyBelow takes an integer as a parameter and is to return the number of integers in the linked list that are strictly less than (meaning less than but not equal to) the number passed as a parameter. 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. (10 points)


(c) Write the member function definition for MoveToTheEnd:

 

(repeated for your convenience)

MoveToTheEnd will move the first node in the linked list to the end of the linked list. It will return false if the linked list is empty, true otherwise. Therefore, it will have no parameters and return a boolean. (10 points)


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

 

NumberOfNodes (recursive) will return the number of nodes in the tree. 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.

 

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 and attempt to locate it in the tree, computing its depth as it does so. (Recall that the depth of a node is the number of edges between it and the root.) It will return the depth of the node if it finds the value and -1 otherwise. Therefore, it will have one parameter and return an integer.

 

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


(repeated for your convenience)

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 and attempt to locate it in the tree, computing its depth as it does so. (Recall that the depth of a node is the number of edges between it and the root.) It will return the depth of the node if it finds the value and -1 otherwise. Therefore, it will have one parameter and return an integer.