CSci 2101 Data Structures: Takehome exam I.

Due Wednesday, March 2, at 8pm. Absolutely no late submissions are accepted, the deadline is firm. Don't try to submit at the last minute, allow extra time for bounced e-mail and similar things. Double-check to make sure that you are submitting the right files (only .java files need to be submitted).

You may use any printed and online materials and your own problem sets. You are allowed to talk to each other about general approaches to the problems. You may also discuss particular compilation issues, but you may not reproduce any part of another person's code or a solution of a paper-and-pencil problem. If you have questions, please come to see me or send me an e-mail. You may not get any help on the assignment from anyone outside of the class.

Problem 1 (7 points)

Write a program to do the following: Make sure to test your program well and submit all the test cases. The program must work for any array with at least one element.

Problem 2 (8 points)

For this program you will need the class files IntQueue.class, and the Node and LinkedList. Copy/paste the code for Node and LinkedLists into files Nodes.java and LinkedList.java.

You need to write a program to do the following:

Test your program carefully, submit all test cases.

Problem 3 (20 points)

Your boss wants you to implement a priority queue to store integers between 1 and 10 as a linked list. He says that since the range of the elements is known, it would be more efficient to implement the queue as a doubly linked list and insert elements which are greater than 5 from the front of the list, and those smaller or equal to 5 from the back of list. This will cut down on the number of node comparisons when an element is inserted. Your task is:

Extra credit (up to 3 points) Analyze this testing strategy. Can you see any flaws in it? Can you suggest better tests? You don't need to implement them, just describe them in detail.


This is a takehome exam from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.