1 Name: _________________________________________ USC NetID (e.g., ttrojan): ______________________________ CS 455 Final Exam Fall 2017 [Bono] Dec. 12, 2017 There are 9 problems on the exam, with 80 points total available. There are 12 pages to the exam (6 pages double-sided), including this one; make sure you have all of them. There is also a one-page double-sided code handout that accompanies the exam. If you need additional space to write any answers or for scratch work, pages 10, 11, and 12 of the exam are left blank for that purpose. If you use these pages for answers you just need to direct us to look there. Do not detach any pages from this exam. Note: if you give multiple answers for a problem, we will only grade the first one. Avoid this issue by labeling and circling your final answers and crossing out any other answers you changed your mind about (though it’s fine if you show your work). Put your name and USC username (a.k.a., NetID) at the top of the exam. Also, put your NetID at the top right of the front side of each page of the exam. Please read over the whole test before beginning. Good luck!2 Problem 1 [7 pts] [Java] The following method doesn’t work as desired. The method comment describes what it is supposed to do. // returns true iff the values in vals are in increasing order. // Array may have duplicate values, e.g., [1, 3, 3, 5] is in increasing // order. [3] and [] are in also in increasing order public static boolean isIncrOrder(int[] vals) { for (int i = 0; i < vals.length - 1; i++) { if (vals[i] > vals[i + 1]) { return false; } else { return true; } } return false; } Part A. Give example data for which isIncrOrder returns the wrong value, and what that value is: vals: return value of isIncrOrder(vals): Part B. Fix the code so it does what the comment says it does. Do not rewrite the whole method, but rather make your changes right into the code above, using arrows to show where any new code should be inserted, crossing out code that you would get rid of, etc.USC NetID: ____________________________ 3 Problem 2 [8 pts] [Java] Consider the following two versions of a method to traverse a List: printList1 and printList2. (These methods will work for both LinkedList's and ArrayList's.) public static void printList1(List<Integer> list) { ListIterator<Integer> iter = list.listIterator(); while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println(); } public static void printList2(List<Integer> list) { for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + " "); } System.out.println(); } Next to each of the four calls to printList1 or printList2 below give the big-O worst case time to run the code as a function of n, the length of the list: (the calls are labeled A - D) ArrayList<Integer> anArrayList = new ArrayList<>(); . . . // code to populate the array list LinkedList<Integer> aLinkedList = new LinkedList<>(); . . . // code to populate the linked list printList1(anArrayList); // A: printList2(anArrayList); // B: printList1(aLinkedList); // C: printList2(aLinkedList); // D:4 Problem 3 [7 points] Consider the following function that uses the Java Stack class: public static void stackProb() { Stack<Integer> s = new Stack<Integer>(); s.push(1); for (int i = 2; i <= 4; i++) { int val = s.peek(); s.push(i * 2); s.push(val + 1); System.out.print(s.pop() + " "); } System.out.println(); // * } Part A. What is the output of the function? Part B. Show the contents of the stack when the execution gets to the point labeled with an asterisk (i.e., contents after the loop exits). Put the contents of the stack in the box below, showing the top of the stack on the right: Problem 4 [6 pts. total] Assume you have an array of names with the following contents (numbers above the line are indices): For each of the targets given below, next to it list the names that the target would be compared with in a binary search on the array. List them in the order that the comparisons would be done. 1. target = Mike 2. target = Lydia 3. target = Walter ß top 0 1 2 3 4 5 6 7 8 Flynn Gus Hank Jesse Marie Mike Saul Skyler WalterUSC NetID: ____________________________ 5 Problem 5 [8 pts.] [Java] Consider a Java Map to store student data. For each student it maps their name to their total score: (Note: the exact kind of map used doesn't matter for this problem.) Map<String, Integer> grades = . . . ; Read over the whole problem before answering. More information about Maps on the code handout. Part A. Suppose you put the following entry in the map: grades.put("Sam", 82); Write code to correctly update this map entry so it has the value 99 instead: Part B. Suppose you then put the following entry in the map: grades.put("Joe", 88); Write code to correctly update this map entry so it has the key "Zhou" instead: After your code runs, the map will have the contents: Sam 99 Zhou 886 Problem 6 [15 pts. total] Part A [14]. [Java] Implement the static method getKeysWithValue that gets all keys that have a particular value in a Java Map. We don’t care what order the keys are in in the resulting arraylist. More information about Maps on the code handout. For example, if map has the entries: Yan 25 Song 34 Andy 25 Lin 92 Aarti 86 getKeysWithValue(25, map) would return [Yan, Andy] getKeysWithValue(92, map) would return [Lin] getKeysWithValue(100, map) would return [] public static ArrayList<String> getKeysWithValue(int val, Map<String, Integer> map) { Part B [1]. For this code assume we're running the code on TreeMap. Give the big-O worst case running time for your code as a function of n, the number of entries in the map:USC NetID: ____________________________ 7 Problem 7 [6 pts. total] Assume we are trying to compile the C++ grades program we did for assignment 5. Here's a reminder of the file organization: Table.h Header file for the Table class (contains Table class definition) Table.cpp Implementation file for the Table class (contains Table method definitions) listFuncs.h Header file for the Node struct and some list functions listFuncs.cpp Implementation file for the Node struct and some list functions grades.cpp A program that uses the Table class (contains