1. True or false (circle one)
2. A student implementing Stack and Queue classes forgets to include member variables keeping track of the number of elements currently in data structure. Describe the problems this would cause in each case.
3. Describe at least two functional differences between an array-based list implementation and a reference-based list implementation.
4. Write a method to insert an element at a given position in a doubly-linked list. The method should take two parameters, the index to insert at and an Object representing the new data.
5. Suppose you have a circular linked list of integers (so that the link from the last node points back to the start of the list). Write a method that returns the sum of the elements, given a reference to the first node in the linked list.
6. Write a recursive method to find the maximum element of a linked list of integers. Trace your code on an example with 3, 7, 5.
7. Suppose the integers 1, 2, 3, 4, 5, and 6 arrive in that order. The numbers are inserted into either a stack or a queue in that order (using push or enqueue). However, they may be removed and printed at any time. For example, 1 may be removed before 2 is inserted. Mark "yes" in each box below that corresponds to a possible output sequence for either a stack or a queue.
|2 4 3 6 5 1|
|1 5 2 4 3 6|
|1 2 3 4 5 6|
|1 3 5 2 4 6|
8. Consider the following postfix expression: 3 4 2 + * 7 -
9. (Extra Credit) Suppose you have two linked lists of integers, sorted in ascending order. Write a method to merge these two linked lists into a single linked list that is still sorted in ascending order.