class Person {
   String name;
   int age;
}
class ListNode {
   int data
   ListNode next;
}
class MyList {
   private ListNode head;
   public MyList() { head= null; }
   public void add(int elem) { ... /* adds to front of list */ }
   public void remove(int elem) { ... /* removes specified element list */ }
}
class MyStack {
   // internal implementation not specified, but does have these methods
   public void push(int elem) {}
   public int pop() {}
   public int size() {}
}
class IntQueue {
   private int [] data;
   private int front,back,n;
}

1. (4 pts) Expand the acronym LIFO. What data structure is it associated with?

2. (4 pts) Arrays and linked lists can both be used to store a collection of data elements. Give one advantage of using arrays over linked lists and one advantage of using linked lists over arrays.

3. (6 pts) Write a compareTo method for the Person class above such that a typical sorting algorithm using your .compareTo() method would order the items from oldest person down to the youngest.

4. (4 pts) Show how the following array would be processed if it were partitioned one time using the partition algorithm that accompanies quicksort. NOTE: Do not perform the entire quicksort ... just partition this array and mark the dividing line between the partitions.

   

5. (4 pts) Give a brief, recursive description of how to do a binary search. (Use words, not code.)

6. Answer these questions about linked lists and the MyList class given above.
   1. (6 pts) Write a isInOrder() method for the MyList class that will return true if the data elements in the list are in ascending order and false otherwise. If the list is empty or has one element return true.

   2. (6 pts) Write a addToEnd(int elem) method for the MyList class that will add the specified element to the far end of the list. Make sure you solution works in the case the list is empty.

   3. (10 pts) Write a reverse() method for the MyList class that will rearrange the elements in the list to be in reverse order. You can use recursion to solve this or make use of the MyStack class documented above (assume it has been implemented) or make use of Java's built-in stack class or solve the problem without using stacks at all.

7. Answer these questions about stacks and the MyStack class given above.
   1. (4 pts) Suppose that when a letter is encountered we push it on the stack and when an asterisk is encountered we pop the stack. Show the sequence in which letters would be popped for the following string:

         !A*RELL**OIAH***LL***TB*S*****
      

   2. (10 pts) Assume you are given a working MyStack class implemented with only 3 methods (push, pop, size). Write a standalone method called same() that accepts two MyStack objects as parameters and returns true if the stacks contain the same elements (in the same order) as each other (false otherwise). When the method completes the stacks should be unharmed. You may not modify the Mystack class and you may only use the three provided methods when interacting with the stacks. HINT: It will be helpful to first check the sizes of the two stacks. If they are different size there is no need for further checking. Also, you may want to utilize additional stacks for temporary storage.

8. Answer these questions about queues.
   1. (4 pts) Suppose that when a letter is encountered we put it in the queue and when an asterisk is encountered we remove from the queue. Show the sequence in which letters would be removed for the following string:

         !A*RELL**OIAH***LL***TB*S*****
      

   2. (4 pts) On the first page of the exam there is a partial class called IntQueue that gives a start to an array-based queue implementation for storing integer data. Write a constructor for this class that accepts the initial capacity of the queue as a parameter. The constructor should reserve memory for the data and should initialize front, back, and n appropriately.
   3. (6 pts) Write an add method for the IntQueue class that inserts an element at the back of the queue and will wrap around the array if needed. If the array is full do not perform the insert.

9. (4 pts) Which homework assignment in this course was your favorite? Why?

10. (4 pts) Which topic in this course was your favorite?