Points off 1 2 3 4 5 6 Total off Net ScoreCS 307 – Midterm 2 – Spring 2002Name____________________________________Last 4 digits of SSN / Student ID ______________Class Unique ID ___________________________Instructions: 1. There are 6 questions on this test. 2. You will have 2 hours to complete the test.3. You may not use a calculator on the test. 4. When code is required, write Java code. 5. The style guide is not in effect.6. Ensure your answers are legible. 7. When writing code you may not use any methods or classes from the Java Standard Library except as noted and the System.out.print, System.out.println, and the equals method.1. (2 points each, 20 points total) Java Mechanics and theory. If an error would occur answer "syntax error" or "runtime error" depending on what type of error it would be. A. What is the average case Big O for inserting N items into an initially empty Linked List that is to be maintained in sorted order?_____________________________________________________________________________B. What is the Big O for deleting a node from the end of a singly linked list that has a head and tail reference?_____________________________________________________________________________CS 307 – Midterm 2 – Spring 2002 1C. Consider the following code from class M2:public static int stone(int n){ if(n <= 0)return 3;elsereturn n + stone( n – 2);}What is printed out by the following code?System.out.println( M2.stone(8) );_____________________________________________________________________________D. Consider the following code from class M2:public static int mav(int m){ if(m <= 0)return 2;elsereturn 2 + mav(m – 1) + mav(m – 2);}What is printed out by the following code?System.out.println( M2.mav(5) );_____________________________________________________________________________E. Given a positive integer N, what is the Big O of M2.mav( N ) from question 1.D?_____________________________________________________________________________CS 307 – Midterm 2 – Spring 2002 2F. Consider a queue of ints that uses a native array of ints, myContainer, to store the elements of the queue. myContainer starts with a capacity of 5. It is resized only when necessary. The queue uses wraparound as discussed in class. Draw myContainer and show its contents after thefollowing code is executed. Be sure to clearly label the front and back elements of the queue.Queue q = new Queue();q.enqueue( 12 );q.enqueue( 9 );q.dequeue();q.enqueue( 73 );q.enqueue( 81 );q.dequeue();q.enqueue( 55 );q.dequeue();q.enqueue( 10 ); _____________________________________________________________________________G. Consider the following code:for( int i = 0; i < N; i++ )for( int j = 1; j < N; j *= 2 )west( i );method west has a Big O of O( N ).What is the Big O of the above code?_____________________________________________________________________________CS 307 – Midterm 2 – Spring 2002 3H. Consider the following code from class M2:public static int warrior(int n){ if(n == 0)return 3;elsereturn n + warrior( n – 2);}What is printed out by the following code?System.out.println( M2.warrior(7) );_____________________________________________________________________________I. Consider a stack that stores integers. What is output by the following code:Stack s = new Stack();s.push( 12 );s.push( 2 );s.push( 8 );s.push( 31 );s.pop();s.push( s.top() );s.push( s.top() );for(int i = 0; i < 3; i++)s.pop();System.out.println( s.top() );_____________________________________________________________________________J. Consider a singly Linked List class. If the class is to be used as the storage container for a Queue what attributes must the Linked List class have so that all queue operations (front, enqueue, dequeue, and size) are all O(1) operations?_____________________________________________________________________________CS 307 – Midterm 2 – Spring 2002 42. (15 points) Complete a removeBack method for a singly linked list class.Use the following ListNode classpublic class ListNode{ // returns next node in list or null if no next nodepublic ListNode getNext( )// set next node to parameterpublic void setNext( ListNode next )// other methods, implementation, and private data members // not shown}This LinkedList class has a reference to the head node and tail node. The list nodes have references to the next node, but not the previous node. The last node of a nonempty list has its next reference set to null. An empty list is signified by the head and tail pointers both being set to null. There is also a private integer to track the number of elements in the list. You may not use any of the other methods in the LinkedList class to complete the removeBackmethod.public class LinkedList{ private ListNode myHead;private ListNode myTail;private int iMySize;// other methods not shown// pre: isEmpty() == false;// post: getSize() = old getSize – 1, last node removed.public void removeBack()// complete this method on the next page.}CS 307 – Midterm 2 – Spring 2002 5// pre: isEmpty() == false;// post: getSize() = old getSize – 1, last node removed.public void removeBack(){CS 307 – Midterm 2 – Spring 2002 63. (20 points) Complete a method to print out all possible subsets of numbers in an array of integers. Given the array of integers:int[] iList = { 2, 5, 6 };one possible form of the output is:[][ 2 ][ 5 ][ 6 ][ 2, 5 ][ 2, 6 ][ 5, 6 ][ 2, 5, 6 ]For this question you may use the ArrayList class. You may only use the following methods from the ArrayList class.ArrayList() Constructs an empty list. boolean add(Object o) Appends the specified element to the end of this list. Object get(int index) Returns the element at the specified position in this list. boolean isEmpty() Tests if this list has no elements. Object remove(int index) Removes the element at the specified position in this list. Object set(int index, Object element) Replaces the element at the specified position in this list with the specified element.String toString() Returns a string representation of this list.You may also use the Integer class, but only the following methods.Integer(int value) Constructs a newly allocated Integer object that represents the primitive int argument. int intValue() Returns the value of this Integer as an int.CS 307 – Midterm 2 – Spring 2002
View Full Document
Unlocking...