CS 2401 Test #2

Date: Thursday, October 28, 2010.

Name: ___________________________________________________________________

1. True or false (circle one)

  1. A queue is often used to convert a recursive method into an iterative method. TRUE or FALSE
  2. You cannot create a new instance of an interface using the "new" operator. TRUE or FALSE
  3. An abstract data type is the same thing as a class. TRUE or FALSE
  4. Suppose you know that you need to store exactly 100 integers. An array uses more space to store them than a linked list. TRUE or FALSE
  5. It is faster to access the 5th element of a list using an array-based implementation instead of a linked-list implemenation. TRUE or FALSE
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 remove an element at a given position in a doubly-linked list. The method should take one parameter, the index of the object to remove.
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 maximum of the elements, given a reference to the first node in the linked list.
6. Write a recursive method to sum the elements of a linked list of integers.
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.

Output Sequence Stack Queue
1 5 2 4 3 6
2 4 3 6 5 1
1 3 5 2 4 6
1 2 3 4 5 6
8. Consider the following postfix expression: 6 8 4 - * 3 *

  1. Rewrite the expression above using infix notation.
  2. Write psuedocode showing how a stack can be used to evaluate the postfix expression.
  3. Diagram the execution of your algorithm on the example above.
9. (Extra Credit) Suppose you have two linked lists of integers, sorted in descending order. Write a method to merge these two linked lists into a single linked list that is still sorted in ascending order.