CMP $338$ Final Final B

Each numbered problem set is worth $20$ points which are evenly divided among the problems in that set.

$1)$ Given: $8-3*(5-2*(1+7/2^2)+1)^2$

a$)$ Trace the integer infix evaluation algorithm.

b$)$ Code the enqueue and dequeue methods of a Queue of integers implemented using a linked list structure.

$2)$ a$)$ In the linked list implementation of a Queue that we did in class there were two distinct structures that we decided would both represent an empty Queue. Draw a diagram of each and explain why we decided both would be considered to be an empty Queue.

b$)$ Given a sorted linked list, write a method that inserts each new value so that the list remains sorted.