CS 101 Fall 2006 Final Exam Name: _______________________________ Email ID: ________ 1 You only need to write your name and e-mail ID on the first page. This exam is CLOSED text book, closed-notes, closed-calculator, closed-neighbor, etc. Questions are worth different amounts, so be sure to look over all the questions and plan your time accordingly. Please sign the honor pledge here: Section # ____ / 5 Question 1 ____ / 15 Question 2 ____ / 25 Question 3 ____ / 20 Question 4 ____ / 10 Question 5 ____ / 25 Total ____ / 100 Note: When an integer type is required use int, when a floating-point type is required use double. If we don’t specify an aspect of a problem, you can make any choice consistent with the given constraints. Note: If you are still writing on the exam after “pens down” is called – even if it is just to write your name – then you will receive a zero on this exam. No exceptions! 1. [5 points] What lab section are you in? ____ CS 101-E ____ CS 101-4 (lab 2:00–3:30 p.m. Fri) ____ CS 101-2 (lab 7:00–8:30 p.m. Thu) ____ CS 101-5 (lab 10:00–11:30 a.m. Fri) ____ CS 101-3 (lab noon–1:30 p.m. Fri) ____ CS 101-6 (lab 2:00–3:30 p.m. Thu)CS 101 Fall 2006 Final Exam Name: _______________________________ Email ID: ________ 2 This exam involves the programming of a single class: a simplified version of the Java Vector class. A major benefit of a vector over an array is that the size of a vector is not fixed. Rather, vectors grow and shrink as elements are added and removed. The class you will implement, called MyVector, will support variable-sized lists of Objects using a technique known as a linked list (which we’ll discuss in a moment). The MyVector class provides five public methods, with the following specifications: • MyVector() – construct an empty list, i.e., one with no elements • int count() – return the number of elements in the list • void add(Object o) – add the Object o as an element at the beginning of the list • void clear() – clear the list, i.e., set it back to a list with no elements • Object [] toArray() – return an array whose size is the length of the list and that contains the same elements as the list in the same order that they appear in the list Here then is an outline of the MyVector class: public class MyVector { private ListNode first; // reference to a node storing the first element in the list, if any public MyVector() { // your code here } public int count() { // your code here } public void add(Object o) { // your code here } public void clear() { // your code here } public Object [] toArray() { // your code here } } Class MyVector has a single private data member, first, of type ListNode. The value of this data member represents the list of objects stored by a given MyVector object. Here is some very important information. Read this carefully. (1) An empty list is represented by setting the value of first to null. Recall: in Java, null is the constant representing a null object reference. Here, then, is a picture of the representation of an empty list: MyVector- firstnull+ ... (2) A non-empty list is represented by setting the value of first to be a reference to a ListNode object that in turn represents two things: the value of the first element in the list, and a reference to another ListNode object that represents the beginning of the rest of the list (which, at the end of the list, is the empty list). This approach to chaining together nodes through references is what we mean by the term linked list. To see how this will works, you have to first consider and understand the definition of the ListNode class, itself.CS 101 Fall 2006 Final Exam Name: _______________________________ Email ID: ________ 3 class ListNode { public Object value; // reference to the Object stored by this node public ListNode rest; // reference to the first ListNode in the rest of the list, if any (can be null) } Remember: An object of this class will store just one of the values in a list of values. A MyVector object representing a list of N objects will thus have N ListNode objects, one for each element in the list. As you can see, the ListNode class is simple. It has two public data members. The first, value, will holds a reference to one object in a given list. The second data member, rest, is the slightly tricky part. It stores a reference to the first ListNode in the rest of the list, which we represent as a reference, rest, to another ListNode object. All of this is much clearer if you consider a few simple pictures. In the following pictures, each rectangle represents an object. Its type is given at the top of the rectangle and its data members follow. Reference values are represented by arrows between objects. A null reference is represented by an arrow pointing to null. The picture that follows is of a list with one element, called Object 1. The list as a whole is represented by an object of type MyVector. This object has a data member first, as described above. The value of this data member is a reference to a ListNode that in turn stores a reference to Object 1. The ListNode object also has a reference, rest, to the rest of the list. Because this list has only one element, the rest of the list is empty, and so the value of the rest data member is set to null. If the rest of the list were not empty (as would occur if the list had two or more elements), then the value of the rest data member would be a reference to another ListNode object representing the first element in the rest of the list! Here, then, is a picture for a list with two elements, Object 2 and Object 1. In particular, this is the list that we will get if we add Object 2 to a list initially containing only Object 1. On this exam, we always add new elements at the beginning of a list. A list with two elements, as the picture below illustrates, is represented by having the first data member of class MyVector refer to a ListNode representing the first element in the list, and by having that ListNode refer to a second ListNode object, which in turn represents the second object in the list. Here then is a picture of a list with two elements, Object 2 and Object 1, which, again, is the list we get if we add Object 2 to the one-element list above.CS 101 Fall 2006 Final Exam Name:
View Full Document
Unlocking...