1 Name: _________________________________________ USC NetID (e.g., ttrojan):______________________________ CS 455 Final Exam Fall 2016 [Bono] December 13, 2016 There are 6 problems on the exam, with 67 points total available. There are 10 pages to the exam (5 pages double-sided), including this one; make sure you have all of them. There is also a one-page code handout that accompanies the exam. If you need additional space to write any answers, pages 8, 9, and 10 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 [10 points] [C++] Consider the following two C++ programs that use a Student class and answer the questions below each one (see code handout for documentation of Student class methods): // Program 1 void foo(Student * s) { s->addScore(15); s = NULL; } int main() { Student * joe = new Student(“Joe”); foo(joe); cout << joe->getScore() << endl; } Part A. In the space above, draw a box-and-pointer diagram (a.k.a., memory diagram) showing all object variables, objects, and their state as they have changed during the code sequence. This includes showing foo's parameters. Part B. What is the output of Program 1? // Program 2 void bar(Student * & t) { t->addScore(25); t = NULL; } int main() { Student * sal = new Student(“Sal”); bar(sal); cout << sal->getScore(); } Part C. In the space above, draw a box-and-pointer diagram for Program 2 like you did for Part A. Part D. What is the output of Program 2?USC NetID: ____________________________ 3 Problem 2 [8 points] [Java] Consider the following code to do linear search in an array (written in Java). It doesn’t currently work in all cases that satisfy the precondition. // returns the location of target in nums, or -1 if not found. // PRE: nums is not null and nums has no duplicates public static int lookup(int[] nums, int target) { inti = 0; while (nums[i] != target) { i++; } if (nums[i] == target) { return i; } else { return -1; } } Part A. Provide a test case where the code does not work correctly, and the corresponding result of that test case. (Show your answer under the headings below.) nums target result Part B. Provide a test case where the code does work correctly, and the corresponding result of that test case. (Show your answer under the headings below.) nums target result Part C. Fix the code above. Do not rewrite the whole method, but rather make minimal changes right into the code above, using arrows to show where your new code should be inserted, crossing out code that you would get rid of, etc.4 Problem 3 [10 points] [Java] The binary search algorithm can be implemented recursively. Below is a partially complete recursive binary search implementation (consists of the two functions below). Complete the code below so it does what its comments say. The only missing parts are indicated by the boxes and underlined areas. (i.e., fill in the boxes and underlined areas provided.) // returns the location of target in words array, or -1 if not found. // PRE: words is in alphabetical order and has no duplicates public static int binSearch(String[] words, String target) { return binSearchR(words, target, 0, words.length-1); } // returns the location of target in the part of words with indices [low,high] // or -1 if not found // PRE: words is in alphabetical order and has no duplicates public static int binSearchR(String[] words, String target, int low, int high) { if (low >high) { } int mid = (low + high) / 2; if (target.equals(words[mid])) { } else if (target.compareTo(words[mid]) < 0) { // target < words[mid] return binSearchR(words, target, ______________________,____________________); } else { // words[mid] < target return binSearchR(words, target, ______________________,____________________); } }USC NetID: ____________________________ 5 Problem 4 [4 pts] [Java] Recall that the Concord class computes the number of occurrences of all words from a document. Consider the two variations of our Concord class below. Version A is the one we did in lecture and lab: it takes a Scanner as a parameter to the addData method. Version B’s addData, instead creates a local variable for the Scanner (and initializes it inside the method). To highlight the differences between the two they are shown in bold in the code below. (The other methods (not shown) of both classes are a constructor that creates an empty version of the concordance (i.e., with no words in it), and another method to print out the results.) Describe a scenario that illustrates an advantage of Version A over Version B. Limit your answer to one to two sentences. Version A. // Computes the number of occurrences of all words from a Scanner public class Concord { // . . . [other details of Concord left out] /** Add data from Scanner to concordance. @param in data to scan. "in" will be at the end of its data after this operation. */ public void addData(Scanner in) { while (in.hasNext()) { String word = in.next(); < . . . add this occurrence of word to the number of occurrences . . . > } } } Version B. // Computes the number of occurrences of all words in the input. public class Concord { // . . . [other details of Concord left out] /** Add data from System.in to concordance (reads until end-of-file). */ public void addData() { Scanner in = new Scanner(System.in); while (in.hasNext()) { String word = in.next(); < . . . add this occurrence of word to the number of occurrences . . . > } } }6 Problem 5 [20 pts] Write the Java function printReversedSentences which reverses the order of all the words in each sentence from a Scanner (it does not reverse the order of the sentences