CS 455留学生辅导、讲解NetID、辅导Java编程、讲解Java语言
- 首页 >> Java编程Name: _________________________________________
USC NetID (e.g., ttrojan): ______________________________
CS 455 Final Exam
Spring 2018 [Bono]
May 8, 2018
There are 9 problems on the exam, with 74 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 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 [4 points]
Divide-and-conquer algorithms are ones where part of the solution to a larger version of a problem involves
dividing the problem in half (roughly) and solving that smaller version. Which of the following algorithms
listed below are divide-and-conquer algorithms (circle the letter to the left of all that apply):
a. linear search
b. mergesort
c. recursive isPalindrome (reminder: the method tells you whether its string argument is a word that
reads the same forward and backward)
d. binary seach
e. insertion sort
f. the merge algorithm (reminder: an efficient algorithm we discussed that takes two ordered lists, and
combines them to create one ordered list)
g. maze search (as done in assignment 3)
Problem 2 [8 points]
Consider a Map class to store a collection of key-value pairs (no duplicate keys) with operations
insert(key), remove(key), lookup(key), and printInOrder (the last is to print all entries in order
by key). For A-D assume a Map with n entries, and give worst case time, unless average case is better.
A. How long would printInOrder take in big-O terms if if the Map used an unordered array
representation?
B. How long would remove take if it used a balanced search tree representation?
C. How long would lookup take if it used an ordered array representation (i.e., ordered by keys)?
D. How long would insert take if it used an unordered linked list representation?
USC NetID: ____________________________
3
Problem 3 [6 points]
[Java] Consider the following incorrect Java program that does not compile: it produces an error related to
exceptions. Note: it uses another class called DataObject – you do not need to understand anything
about how DataObject works to solve this problem. (Note: see code handout for more information about
the Scanner class.)
Fix the program and enhance it as follows: if the user gives a file name for a non-existent file, for
example, flkjm, print the following message:
ERROR: File does not exist: flkjm
Exiting program.
and exit the program immediately (without crashing). If the file does exist, the program will operate
normally. Space is given below to make your modifications / additions right in the code below.
public class MyProg {
public static DataObject readFile(String fileName) {
DataObject data = new DataObject(); // create an empty data object
File inFile = new File(fileName);
Scanner fileScanner = new Scanner(inFile);
while (fileScanner.hasNext()) {
// . . . [ reads and puts stuff in “data” ]
}
fileScanner.close();
return data;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print ("Please enter a file name: ");
String fileName = in.next ();
DataObject data = readfile(fileName);
data.process();
data.printResults(System.out);
}
}
4
Problem 4 [15 points]
A different way to represent the maze data for the Maze class of assignment 3 is to store only the set of wall
locations in the maze. In this problem you are going to write part of the implementation of the Maze class
using this representation as a Java HashSet (the instance variable walls is already defined for you below).
Implement (1) the initWalls private method (called from the constructor below) and (2) the
hasWallAt public method. For the purposes of this problem, assume MazeCoord has been defined
appropriately to be able to use it as the element type in a HashSet. See code handout for more about the
MazeCoord class and the Set interface.
Hint: the number of rows in a 2D array, arr, is a.length; the number of columns is a[0].length
public class Maze {
private Set<MazeCoord> walls; // the set of coords that are walls
public static final boolean FREE = false;
public static final boolean WALL = true;
. . . // other constants and instance variables not shown
/**
Constructs a maze.
@param mazeData the maze data. A 2D array of values Maze.FREE and
Maze.WALL (see public FREE / WALL constants above) where the
first index indicates the row. e.g., mazeData[row][col]
. . .
*/
public Maze(boolean[][] mazeData, . . .) {
initWalls(mazeData);
. . . [code to initialize the other instance variables not shown]
}
/**
Initializes the walls variable from mazeData.
@param mazeData the maze data. A 2D array of values FREE and
WALL (see public FREE / WALL constants above) where the
first index indicates the row. e.g., mazeData[row][col]
*/
private void initWalls(boolean[][] mazeData) { . . . }
/**
Returns true iff there is a wall at this location
@param loc the location in maze coordinates
@return whether there is a wall here
PRE: 0 <= loc.getRow() < numRows() and 0 <= loc.getCol() < numCols()
*/
public boolean hasWallAt(MazeCoord loc) { . . . }
. . . [other parts of the class not shown]
}
[space for your answer on the next page]
USC NetID: ____________________________
5
Problem 4 (cont.)
public class Maze {
private Set<MazeCoord> walls; // the set of coords that are walls
public static final boolean FREE = false;
public static final boolean WALL = true;
. . . // [other parts of the class not shown]
/**
Initializes the walls in the maze.
@param mazeData the maze data. A 2D array of values FREE and
WALL (see public FREE / WALL constants above) where the
first index indicates the row. e.g., mazeData[row][col]
*/
private void initWalls(boolean[][] mazeData) {
/**
Returns true iff there is a wall at this location
@param loc the location in maze coordinates
@return whether there is a wall here
PRE: 0 <= loc.getRow() < numRows() and 0 <= loc.getCol() < numCols()
*/
public boolean hasWallAt(MazeCoord loc) {
6
Problem 5 [8 pts total]
Some of the answers in the answer bank below are for one of the four questions given. Match the question
with the correct answer(s) by filling in the space to the left of an answer with with one of A, B, C, D,
or leave it blank if it is not an answer to any of the four questions. That is, there can be more than
one answer for a particular question, but each answer goes with at most one question.
A. What are some of the ways a designer of a class and its implementation could fail to use information
hiding?
B. What are some bad effects of lack of information hiding?
C. What are some of the benefits of test-driven design?
D. What are some possible benefits of helper functions?
Answer bank:
________ 1. using magic numbers
________ 2. making instance variables public
________ 3. shorter methods
________ 4. makes the program less efficient
________ 5. makes the program more efficient
________ 6. unexpected side-effects
________ 7. testing is not an afterthought
________ 8. can focus on getting rid of all of your compile errors for your complete program before you
run it the first time
________ 9. methods may not work as advertised
________ 10. returning a reference to private data
________ 11. forces you to think hard about the expected behavior of a class or method before you
implement it
________ 12. any changes to the representation could involve changing all of the code that uses the class
________ 13. more readable code
________ 14. two classes will be less tightly coupled
________ 15. less code to write
________ 16. can delay testing your program
USC NetID: ____________________________
7
Problem 6 [6 pts]
[C++] Suppose we have read data about one employee from a text file into the character array buffer,
whose definition is shown below. Here is what we know about the structure of the data read:
buffer is one big C-string
We know that the ID number for an employee starts at position START_LOC in buffer (i.e., the
position given is an array index); see constant below.
The ID number for an employee is always ID_LEN characters long (see constant below).
There is other employee data that comes immediately before and after the ID number in buffer
Add to the code below in the following way: Define and initialize a C-string called idNum so that it
contains a copy of the ID number part of buffer. To get full credit idNum must be no larger than
necessary. (Note: for the purposes of this question you may not use the C++ string class or other C++
classes.)
const int START_LOC = 7;
const int ID_LEN = 10;
const int BUFFER_LEN = 1024;
char buffer[BUFFER_LEN];
// . . . <code to read data for an employee into buffer not shown here>
8
Problem 7 [6 points]
[C++] Consider the following working code to remove the last element from a linked list (adapted from a
version of the code we developed in a lecture this semester):
(Note: The Node and ListType definitions are on the code handout.)
// PRE: list is a well-formed linked list
void removeLast1(ListType & list) {
if (list == NULL) { // no elements in list
return;
}
if (list->next == NULL) { // one element in list
delete list;
list = NULL;
return;
}
Node * p = list;
while (p->next->next != NULL) {
p = p->next;
}
delete p->next;
p->next = NULL; // (1)
}
Part A. Does the code still work if we remove the last statement (labelled (1)) above?
Part B. Draw a box-and-pointer diagram illustrating the state of all the variables and objects at the
end of executing the NEW version of the function (i.e., the version with statement (1) eliminated),
when given the list [1, 2, 3, 4]. Show any reclaimed memory with a dotted circle around it. If you
answered no to part A, also give a one-sentence explanation of what's wrong with the new version.
USC NetID: ____________________________
9
Problem 8 [6 points]
[C++] Consider the following different version of working code to remove the last element from a linked
list:
(Note: The Node and ListType definitions are on the code handout.)
// PRE: list is a well-formed linked list
// this version uses two pointers for traversal
void removeLast2(ListType & list) {
if (list == NULL) { // no elements in list
return;
}
if (list->next == NULL) { // one element in list
delete list;
list = NULL;
return;
}
Node * prev = list;
Node *curr = list ->next;
while (curr->next != NULL) {
prev = curr;
curr = curr->next;
}
prev->next = NULL; // (2)
delete curr; // (3)
}
Part A. Does the code still work if we switch the order of the last two statements (labeled(2) and
(3)) above?
Part B. Draw a box-and-pointer diagram illustrating the state of all the variables and objects at the
end of executing the NEW version of the function (i.e., the version with the order of statements (2)
and (3) swapped), when given the list [1, 2, 3, 4]. Show any reclaimed memory with a dotted circle
around it. If you answered no to part A, also give a one-sentence explanation of what's wrong with
the new version.
10
Problem 9 [15 points]
[C++] Write the C++ function numRuns, which returns the number of runs in a linked list. A run is a
sequence of two or more of the same values all adjacent.
The Node and ListType definitions are on the code handout. Some examples:
list return value of numRuns(list)
[2,2,7,3] 1
[2,7,2] 0
[2,2,7,2,2,2,2] 2
[3,3,2,2,2,4,4,4,4] 3
[] 0
// PRE: list is a well-formed linked list
int numRuns(ListType list) {
USC NetID: ____________________________
11
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.
12
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.