CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009,PROF. LOFTINNAMEAll your work should be done on the pages provided. Scratch paperis available, but you should present everything which is to be gradedon the pages of the test. The test is a total of 137 points. Good luck!Problem Grade12345678910111213141516Total1CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 2(1) (6 pts) Let fkbe defined byf0= 3, fk= 1 + 2fk−1for k ≥ 1.Write a recursive methodpublic static int f(int k)whose return value is fk.(2) (5 pts) Assume that LStack is an implementation of the Stackinterface containing a stack of integers. What is the output tothe screen of the following program?public class StackProblem{public static void main(String[] args){Stack s = new LStack();s.push(5);s.push(7);s.push(s.pop() + s.pop());s.push(10);s.push(15);System.out.println(s.pop());int x = s.pop(), y = s.pop();System.out.println(y-x);}}Output:CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 3(3) (15 pts) Consider the following methodpublic static int p(int n){if (n==0)return 1;elsereturn 3*p(n-1);}(a) What is the return value p(4)?(b) Give an explicit mathematical non-recursive formula forthe return value p(n) for n a positive integer.(c) What happens if -1 is passed into the method p as theparameter n?(d) Rewrite the method p so that it avoids the problem in part(c). In other words, it should behave well for every integervalue of the parameter n.CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 4(4) (6 pts) What is the output of the following program?public class Problem{public static void main (String[] args){int[] a = {3,4,7,10,2,1};int[] b = {3,6,9,8,0};printOut(a);changeB(b);printOut(b);changeA(a);printOut(a);}public static void changeA (int[] ar){ar = new int[10];for (int i=0; i<10; i++)ar[i] = i*i;}public static void changeB (int[] ar){for (int i=0; i<ar.length; i++)ar[i] += i;}public static void printOut (int[] ar){for (int i=0; i<ar.length; i++)System.out.print(ar[i] + " ");System.out.println();}}Output:CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 5(5) (5 pts) What is the return value r(43)? Justify your answer.public static String r (int n){if (n<5)return n + "";elsereturn r(n/5) + n%5 + "";}(6) (6 pts) Trace through the insertion sort on the array of integers3 7 0 2 13 -1 6In particular, write out the elements of the array after each passof the algorithm.(7) (10 pts) Write a class hierarchy containing the following classes:Airplane, Vehicle, Boat, Canoe, Automobile, Truck, Convertible,Warship, Pickup, Sportscar.CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 6(8) (6 pts) What is the output to the screen?public class Driver{public static void main (String[] args){Speak sp = new Speak();sp.message();sp = new SpeakChild();sp.message();}}public class Speak{public void message(){System.out.println("Speak only when spoken to.");}}public class SpeakChild extends Speak{public void message(){System.out.println("Children should be seen and not heard.");super.message();}}Output:(9) (8 pts) Write a methodpublic static Comparable max (Comparable[] ar)which returns the maximum value of an array ar of objectswhich implement the Comparable interface.CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 7(10) (18 pts) Consider the interfacepublic interface Shape{public double area();public double perimeter();}(a) Write a classpublic class Rectangle implements Shapewhose constructor stores the height and width of the rec-tangle. Implement the Shape interface. Recall the area ofa rectangle is hw for h the height and w the width, whilethe perimeter is 2h + 2w.(b) Write a classpublic class Square extends Rectanglewhose constructor stores the side-length of the square. Useinheritance to ensure the area and perimeter are correctlycalculated.CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 8(c) Write a classpublic class Triangle implements Shapewhose constructor stores the three sides of a triangle a, b, c.The perimeter of a triangle is given by a + b + c, while thearea is given by the formulaps(s − a)(s − b)(s − c),where s = (a + b + c)/2. Recall the Math.sqrt methodcomputes the square root in Java.(11) (5 pts) Let q represent an initially empty queue of integers. List,in order, the elements of q after the following code executes.Justify your answer.q.enqueue(5);q.enqueue(10);for (int i=0; i<2; i++){int x = q.dequeue();if (x%2 == 0)q.enqueue(x);else{q.enqueue(i);q.enqueue(x-1);}}CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 9(12) (8 pts) A string is said to be a palindrome if it is the same stringwhen all the characters are written in the reverse order. Forexample, “a”, “eve”, “star rats”, and “toot” are palindromes,while “evaluate” is not. Write a recursive methodpublic static boolean palindrome(String s)which returns true if s is a palindrome and false otherwise.Recall some methods of the String class:char charAt (int index) // character at indexint length() // length of the stringString substring (int offset, int endIndex)// returns substring from index offset to endIndex-1Hint: Test whether the first and last characters of s are equal,and if so, recursively call the method with a smaller substring.What should the base case be?CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 10(13) (20 pts) Consider the class MyList (as discussed in class):public class MyList{private MyListNode head;public MyList(){ head = null; }public void addAtHead (int value){MyListNode temp = head;head = new MyListNode(value);head.next = temp;}public void add (int index, int value){if (index==0)addAtHead(value);else{MyListNode prev = head, curr = head.next;for (int i=1; i<index; i++){prev = curr;curr = curr.next;}MyListNode newNode = new MyListNode(value);prev.next = newNode;newNode.next = curr;}}public String toString(){ // fill in}private class MyListNode{public int num;public MyListNode next;public MyListNode(int n){num = n;next = null;}}}CS102, FINAL EXAM, MONDAY, DECEMBER 21, 2009, PROF. LOFTIN 11(a) Write the toString method of the MyList class (given onthe previous page), whose return value should return allthe elements of the list, in order, separated by spaces.(b) What is the output of the following driver class?public class MyListDriver{public static void main (String[] args){MyList a = new MyList();a.addAtHead(5);a.addAtHead(3);System.out.println(a);a.add(2,4);a.add(1,6);System.out.println(a);}}Output:CS102, FINAL EXAM, MONDAY, DECEMBER