联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2020-10-22 10:50

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<String, Integer> concordMap;

// Creates empty concordance

public Concord() {

concordMap = new HashMap<String, Integer>();

}

// 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<Map.Entry<String, Integer>> iter = concordMap.entrySet().iterator();

boolean found = false;

while (iter.hasNext() && !found) {

Map.Entry<String, Integer> 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.


版权所有:编程辅导网 2018 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。