CS 455语言讲解、R，Python编程语言辅导、Java程序设计调试
辅导Database|辅导Python程序
CS 455 Midterm Exam 2
Fall 2019 [Bono]
Nov. 12, 2019
There are 7 problems on the exam, with 58 points total available. There are 8 pages to the exam (4
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 or for
scratch work, pages 7 and 8 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, USC ID number, and 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 (even if you wrote nothing else on that
page). Please read over the whole test before beginning. Good luck!
2
Problem 1 [9 pts. total]
Consider the following working implementation of part of the Concord class. Reminder: A Concord object
keeps track of the number of instances of each word from one or more files. See code handout for more
about Map, etc.
public class Concord {
private Map concordMap;
// Creates empty concordance
public Concord() {
concordMap = new HashMap();
}
// 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();
addInstanceOf(word);
}
}
// add an instance of word to the concordance
private void addInstanceOf(String word) {
Iterator> iter = concordMap.entrySet().iterator();
boolean found = false;
while (iter.hasNext() && !found) {
Map.Entry entry = iter.next();
if (entry.getKey().equals(word)) {
entry.setValue(entry.getValue() + 1);
found = true;
}
}
if (!found) {
concordMap.put(word, 1);
}
}
. . . // rest of class not shown
}
(continued on next page)
USC NetID: ____________________________
3
Problem 1 (cont.)
Note: these questions go with the code on the previous page.
Part A [2]. What is the worst-case big-O time for addData as a function of n, the number of vals in the
file we're reading from.
Part B [5]. Modify addData to improve it's big-O complexity. This could, of course, also involve
changes to its helper function. Do not rewrite the whole method, but rather make your changes right into
the code on the previous page, using arrows to show where any new code should be inserted, crossing out
code that you would get rid of, etc. You will get no credit if it's unclear how your new code fits in with the
existing code.
Part A [2]. What is the worst-case big-O time for the version of addData you wrote for part B.
Problem 2 [2 points]
Name the Java Collection class we have discussed this semester that most closely matches the
functionality of the Names class we discussed earlier in the semester. Reminder: the Names class stores a
bunch of Strings with no duplicates and has methods: insert(name), remove(name), lookup(name),
numNames() and printNames() (the last one prints all the names in alphabetical order).
Problem 3 [2 points]
Suppose you want to sort an ArrayList of objects in increasing order using a Java API sort method.
Part A. Sometimes this involves a Comparable (i.e., implementation of Comparable interface).
Comparable is a property of (circle the correct answer)
1. the ArrayList
2. the objects in the ArrayList
3. neither
Part B. Sometimes this involves a Comparator (i.e., implementation of Comparator interface).
Comparator is a property of (circle the correct answer)
1. the ArrayList
2. the objects in the ArrayList
3. neither
4
Problem 4 [8 points]
List the following algorithms in order from fastest running to slowest running in terms of big-O time
complexity. If more than one algorithm has the same time complexity you can list those ones in any
order with respect to each other. In your list just show the letter that identifies each algorithm (don't
rewrite the algorithm name). This question does not ask for big-O times; giving big-O times without
ordering them correctly will be worth little to no credit.
Show ordered list of
letters here:
A. mergesort
B. get kth element in an array
C. linear search
D. insertion sort
E. merge algorithm (combine two ordered lists of length n to make one large ordered list)
F. binary search
G. get kth element in a linked list
H. traverse a balanced search tree
Problem 5 [2 points]
Consider a hash table whose keys are strings, and that uses chaining in an array with 10000 buckets, and
uses the following hash function:
public static int hash(String key) {
return 3297 * 31 % 10000;
}
Suppose we add 500 distinct keys to this hash table (the table starts out empty). Now we are going to
add a new key that is not already present in the hash table. What is the BEST case for the number of
keys the new key will need to be compared to when inserting the new key into the hash table? Your
answer will be a number, not a big-O value.
fastest slowest
USC NetID: ____________________________
5
Problem 6 [15 points]
Below is a partially complete recursive function to find the location of a value in a sorted array of ints (i.e.,
function plus recursive helper function). Complete the code below, so it does what its comments say.
Your solution must be recursive and use the binary search algorithm. A solution that doesn't use
recursion will receive little to no credit.
// returns the location of target in vals array, or -1 if not found.
// PRE: vals is in alphabetical order and has no duplicates
public static int binSearch(int[] vals, int target) {
return binSearchR(vals, target, 0, vals.length-1);
}
// returns the location of target in the part of vals with indices [low,high]
// or -1 if not found
// PRE: vals in range [low,high] is in alphabetical order and has no duplicates
public static int binSearchR(int[] vals, int target, int low, int high) {
if (low > high) {
}
int mid = (low + high) / 2;
6
Problem 7 [20 pts]
Write the Java function printReversedSentence which prints out a version of a sentence read from
a Scanner with the order of the words reversed. Note: the sentence does not necessarily make up the
all of the data from the scanner (i.e., in.hasNext() may still be true after a call to
printReversedSentence(in)). For full credit you must use a Java Stack (see code handout for
more about Stack and String). To make the problem easier, we are not going to worry about proper
capitalization. Note: you will not be using recursion. Here is an example of this function at work (pay
attention to the placement of the periods):
input text read corresponding output text
its fleece was white as snow. snow as white was fleece its.
ahem. ahem.
mary had a little lamb. lamb little a had mary.
the end. end the.
// Prints out a version of a sentence read from the given scanner such that
// the order of words is reversed. A sentence has one or more words and is
// terminated with a period.
// All output will be on one line (i.e., no newlines printed).
// PRE: the next sequence of characters on the scanner is a sentence.
public static void printReversedSentence(Scanner in) {
USC NetID: ____________________________
7
Extra space for answers or scratch work. (DO NOT detach this page.)
If you put any of your answers here, please write a note on the question page directing us to look here. Also
label any such answers here with the question number and part, and circle the answer.
8
Extra space for answers or scratch work (cont.) (DO NOT detach this page.)
If you put any of your answers here, please write a note on the question page directing us to look here. Also
label any such answers here with the question number and part, and circle the answer.