CS 127 Data Structures Exam #1

For this exam, you may use your notes, textbook, and any code that you have written (on your own or with partners). You may also use the Java API. You may not use the Internet otherwise.

All of your work should be submitted from a directory called exam1. For problems A, B, and E, turn in your answers in a file within that directory called exam1.txt. Feel free to write part or all of any of your answers on paper if you wish. Turn in your exam with hsp when you're done. If you have any paper to turn in, indicate your name at the top of each sheet.

Remember that on the programming problems, minor Java bugs will not count heavily against you if your algorithm is right.

Good luck!

Problem A: Inheritance (16 points)

  1. What is the advantage of specifying an abstract data type as an interface instead of just going ahead and implementing it as a class?
  2. What is the difference between an interface and an abstract class? Describe briefly a scenario where it makes more sense to use an interface, and describe briefly a scenario where it makes more sense to use an abstract class.

Problem B: Algorithm Complexity / Linked Lists (16 points)

For the following big-O questions, give a reasonably tight answer, like the ones that we have done in class: though O(nn) is technically correct for both of these, I'm looking for an answer that indicates that you understand how much work the algorithm takes.

Suppose that you are given a singly linked list for storing data.

  1. How much work (big-O) does it take to insert n items into the linked list, assuming that you use an algorithm to make this as efficient as you can? (The order that you store the data in can be different than how it appeared.) Briefly describe your algorithm, and how you obtain your big-O answer.
  2. If you use the algorithm that you described above, is it possible to retrieve the n items in the same order that they were inserted? If so, indicate how much work (big-O) it takes and briefly explain your answer. If it is not possible, explain why not.

Problem C: Linked List Implementation (24 points)

Copy this CopyList.java program to your exam directory, and take a look at it. This program creates a "rough and ready" linked list pointed to by the variable oldHead. You should add code to the method main that will copy the linked list pointed to by oldHead to a new linked list pointed to by newHead. This should be a "deep copy", i.e. the new list should have its own set of nodes with the same data that is in the old list, but the two lists should not share any actual nodes between them. Your code should be general enough that if I change the list above pointed to by oldHead in a variety of ways (longer, shorter, empty, etc), your code should still work.

Finally, near the end of main, you should write code to print both linked lists to the screen.

You should not use the built-in LinkedList class or other similar classes that would defeat the spirit of this problem, which is to write linked list code.

Problem D: Stacks (24 points)

Copy this StackSmall.java program to your exam directory, and take a look at it. This program uses the built-in Stack class to create a stack of Strings. You should add code to the method main that will move the smallest String (using usual String ordering) to the top of the stack while leaving the rest of the stack ordering the same. You may only use the four traditional methods for a stack: empty, peek, pop, and push (even though the the built-in Stack class has additional methods.) You can, however, use an additional stack if you wish (declared for you in the code) as well as a few extra Strings and ints (also declared for you). Your code should be general enough so that if I change the data (more of it, less of it, none of it, etc.), your code should still work. You should not declare any variables beyond those that I declared for you, though you may change their names if you wish.

You can assume that the stack will have no duplicates on it.

Hint: Keep track of which item is the smallest while moving items from one stack to the other, and then use it appropriately when moving items back.

Here is the API documentation for the built in Stack class. Again, remember that you can only use the methods empty, peek, pop, and push.

Problem E: Queues (20 points)

A priority queue is a data structure that lets you append entries like a queue, but each entry also has a priority associated with it. The peek and remove operations for a priority queue obtain the entry that has the highest priority. If more than one entry has the same highest priority, then the entry with the highest priority that was appended first should be retrieved.

  1. Why does the phrase priority queue have the word "queue" in it, i.e. what part of its behavior is similar to that of a queue?

  2. Describe in words (and with a diagram, if you find it helpful) how you might implement a priority queue using only data structures that we have discussed. (The book has some ideas later on, but I'd like to see what you can do with the tools you have so far.) Your solution does not need to be highly efficient, but it should work correctly.

    Suppose that there are n elements in your priority queue.

  3. In the worst case, how many operations would it take to insert an entry to your priority queue?

  4. In the worst case, how many operations would it take to remove an entry from your priority queue?

  5. How does this compare to an efficient implementation of a traditional queue in an array?