PART I

$1)$ Given:$9-2*(6-4/(31))+2$

a$)$ Trace the infix evaluation algorithm algorithm.

b$)$ What is the equivalent postfix expression?

$$

$2)$ Write the code for the enqueue and dequeue methods of a Queue class implemented with a linked structure.

$$ Include any supporting variable declarations from the Queue class.

$$ After many enqueue, dequeue operations would your queue lose access to the front or back of the queue?$$ Why or why not?

$$

$3)$ Making use of both Stacks and Queues, write a function that will determine whether or not a String is a palindrome.

$$

PART II

$4)$ What is the reason that we used a dummy node at the head and tail of many of our linked list implementations?

Why didn't we do this for the linked list implementation of the Stack or Queue?

$$

$5)$ Write a method to search for and remove an element from a linked list, thereby returning the data portion of the node.

$$

$6)$ a$)$ When devising an algorithm for linked lists, why must you be careful about the order in which you change the references?

$$ b$)$ What code would be needed to change the references in a linked list when moving up one node?

$$ c$)$ Why did we have a previous reference in our linked list implementation?

$$ d$)$ Write a class for a linked list node with just one constructor that allows the initialization of all instance variables.

$$

PART III

$7)$ Given the following list of values: $45,54,89,32,23,58,65,76,88,55,42,12,38,34,57,79,90,66$

a$)$ Draw the binary search tree that would evolve by inserting the values into the tree in the order in which they are presented.

b$)$ Draw the array representation of this binary search tree.$$ You may use $...$ notation as long as you label the array cells.

c$)$ In what order would you insert the values so as to get a complete binary search tree?

d$)$ In what order would you insert the values so as to get a linked list that uses left references only?$$ Right references only?

e$)$ How many elements would be needed for each of the binary trees described in part d if implemented as arrays?

f$)$ Why are binary search tree more often implemented using linked structures rather than arrays?

$$

$8)$ a$)$ Define binary search tree.

$$ b$)$ Why were we able to implement the binary search trees entirely by developing a class to represent binary search tree nodes?

$$ c$)$ What was the one problem we encountered with this implementation?

$$ d$)$ How can this problem be overcome?

$$

$9)$ Write two search methods for binary search trees, one implemented using linked nodes and the other an array.$$

$$

PART IV

$10)$ Given the following list of inputs: $45,54,89,32,23,58,65,76,88,55,42,12,38,34,57,79,90,66$

a$)$ Trace the development of the heap in abstract form that would evolve by inserting the inputs in the order that they are presented.

b$)$ Draw the final version of the array representation of this heap, i$.$e$.$ you need not show the array develop.

c$)$ What property of a heap led to the array being smaller than that of the binary search tree in problem $7$b$.$

d$)$ Why are heaps generally implemented with an array and not a linked structure?

$$

$11)$ Write an insert function for a heap class as well as all support functions that are called by your insert function.

$$

$12)$ Given the following list of values: $32,56,25,28,44,54,89$

Trace the steps of applying heapsort using both an array and a linked structure representation for the trace.

$$

PART V $-$ Refer to the graphs represented on the blackboard.

$13)$ Determine both the graph drawing and adjacency matrix for the edge list given and trace a Breadth First Traversal starting from v$0.$

$$

$14)$ Determine both the graph drawing and edge list for the adjacency matrix given and trace a Depth First Traversal starting from v$0.$

$$

$15)$ Determine both the adjacency matrix and edge list for the graph drawing given and trace Dijktra's algorithm starting from v$0.$

Explain how you would determine the shortest path from v$0$ to v$5.$