Java程序辅导

0/22 Questions Answered
S21 MT 2 Exam
Q1 Rules for the exam
1 Point
you may use blank paper and a pencil for your scratch work (this will not 
be submitted)
the exam is closed book, closed note
besides gradescope you may not use any other software, devices or web 
pages while working on the exam (headphones to block noise ok)
except you may refer to the pdf code handout that was distributed before 
the exam
you may not communicate with any one else while working on the exam
one exception to the previous items: you may use this number to 
communicate with Claire for emergencies only: xxx-xxx-xxxx (e.g., if you 
get disconnected from internet for more than a few minutes)
you may not communicate with any one else in the class about the exam 
until the day after the exam
you must in general abide by the USC student conduct code
Student statement:
I have read and agree to these rules and I understand that violation of any 
of these rules may result in failing the course.
Additional directions and information
STUDENT NAME
Search students by name or email… !
I agree"
I do not agree"
Additional directions and information
if you give multiple answers to a problem we will only grade the first one
the quality of your code will be considered in the answer, e.g, answers 
that take more big-O space or time than necessary may not receive full 
credit.
for any big-O questions:
you should consider, for example, constant time and amortized constant 
time to be the same computational complexity (and you can call these 
O(1))
you should give the worst case time unless the average case time is 
better
if you need to write, for example, O( ), write it as O(n^2)
there are 74 points total on this exam.
Save Answer
Q2 Stacks
6 Points
Consider the following function that uses the Java Stack  class:
public static void stackFunc() {
   Stack s = new Stack<>(); 
   for (int i = 1; i <= 6; i++) {
      s.push(i);
      s.push(i/2);
      System.out.print(s.pop() + " ");
   }
   System.out.println(); 
   // ****
}
Q2.1
3 Points
What is the output of the function?
n2
Enter your answer here
Save Answer
Q2.2
3 Points
Show the contents of the stack at the point labeled **** in the code.  
To get full credit you must show where the top of the stack is.  E.g., here is 
an example showing a stack of four letters, where A is the top letter:
M D F A <--top
If the stack is empty just say  .
Enter your answer here
Save Answer
Q3 hashCode/equals
5 Points
Suppose we have a Student  class that stores a student name and total 
score.  Furthermore, assume that this class overrides neither hashCode  nor
 equals .  We can still make a HashSet  or HashMap  using Student  objects, 
because hashCode  and equals  are inherited from Object .  Assume we 
have just executed the following code using this Student  class:
Set mySet = new HashSet<>();
Student s = new Student("Chen", 98);
mySet.add(s);
Student t = new Student("Chen", 98);
Given the assumptions and code above, which of the following boolean 
expressions using the variables above are true  (select all that apply or 
the none of the above option):
Save Answer
Q4 big-O
7 Points
In a lecture earlier in the semester we discussed the big-O of methods of 
the following Sequence  class that stores a sequence of integers.  In lecture 
we assumed we were using an array or ArrayList as the internal 
representation when answering the question; we're using a different 
representation here.  
Give the big-O worst case time for each of the following methods as a 
function of n, the size of the sequence, assuming the class instead uses a 
Java LinkedList  object as its internal representation.  
A.
   // creates an empty sequence
   public Sequence() { . . . } 
Enter your answer here
s.hashCode() == t.hashCode()
s.equals(t)
s == t
mySet.contains(s)
mySet.contains(t)
none of the above expressions are true
B.
   // gets the value at the specified position in the sequence
   // PRE: 0 <= loc < numVals()
   public int getValAt(int loc) {  . . . }
Enter your answer here
C.
   // returns true iff this sequence contains the specified value
   public boolean contains(int val) {  . . . }
Enter your answer here
D.
   // removes the value at the specified position 
   // PRE: 0 <= loc < numVals()
   public void removeValAt(int loc) {  . . . }
Enter your answer here
E.
   // inserts val at the end of this sequence
   public void insertAtEnd(int val) {  . . . }
Enter your answer here
F.
   // inserts val at the beginning of this sequence
   public void insertInFront(int val) {  . . . }
Enter your answer here
G.
   // number of values in this sequence
   public int numVals() {  . . . }
Enter your answer here
Save Answer
Q5 encapsulation
11 Points
Consider the BookshelfKeeperProg  you wrote in a recent assignment.  
Here is a reminder of the program organization: 
BookshelfKeeperProg  has the main method plus some static methods.  
It has a terminal-based interface and it stores its data in a local
 BookshelfKeeper  object.
BookshelfKeeper  uses a Bookshelf  internally and also has a
 Bookshelf  as the parameter to one of its constructors.
Bookshelf  is a class that maintains information about the heights of 
books on a bookshelf and allows inserting and removing from either end.
For each of the following items, select all classes of the program that 
need to know about that item to complete the program.  To clarify, by a 
"class needs to know", we mean the code in that class needs to use that 
information and/or the programmer of that class needs to know that 
information to complete that class of the program.  The choice none means 
none of the classes need to know about it.
Q5.1
1 Point
Which of the following classes need to know the names of methods of
 BookshelfKeeperProg ?
Save Answer
Q5.2
1 Point
Which of the following classes need to know the types of local variables in
 Bookshelf  methods?
Save Answer
Q5.3
1 Point
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
Which of the following classes need to know whether the user provides 
input from the keyboard, or uses input redirection from a file?
Save Answer
Q5.4
1 Point
Which of the following classes need to know the class name
 BookshelfKeeper ?
Save Answer
Q5.5
1 Point
Which of the following classes need to know names of BookshelfKeeper  
instance variables?
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
Save Answer
Q5.6
1 Point
Which of the following classes need to know the class name
 BookshelfKeeperProg ?
Save Answer
Q5.7
1 Point
Which of the following classes need to know preconditions on
 BookshelfKeeper  methods?
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
BookshelfKeeperProg
BookshelfKeeper
Save Answer
Q5.8
1 Point
Which of the following classes need to know data structure(s) used in a
 BookshelfKeeper  object?
Save Answer
Q5.9
1 Point
Which of the following classes need to know correct format of the user 
input?
BookshelfKeeper
Bookshelf
none
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
Save Answer
Q5.10
1 Point
Which of the following classes need to know the strategy for doing the 
minimum number of operations to put or pick a book?
Save Answer
Q5.11
1 Point
Which of the following classes need to know the contents of the error 
messages?
none
BookshelfKeeper
BookshelfKeeperProg
Bookshelf
none
BookshelfKeeperProg
BookshelfKeeper
Bookshelf
none
Save Answer
Q6 Java sort
8 Points
Implement the Java method sortByArea , which sorts an ArrayList of 
Java Rectangle  objects so they are in decreasing order by area; i.e., 
larger rectangles will appear on the list before smaller ones.  Your 
solution must use the Java sort  utility and include any additional code 
necessary to make it work (this may be outside of the sortByArea 
method). 
See code handout for relevant Java library information.
public static void sortByArea(ArrayList boxes) {
Enter your answer here
Save Answer
Q7 binary search trees
6 Points
Consider the following binary search tree, whose root is shown at the top:
For each of the following lookups from the tree shown above, list the 
sequence of keys that the target would be compared with to do the 
lookup (separate the key names with a space.)
Q7.1
2 Points
lookup Qi
Enter your answer here
Save Answer
Q7.2
2 Points
lookup Kai
Enter your answer here
Save Answer
Q7.3
2 Points
lookup Min
Enter your answer here
Save Answer
Save Answer
Q8 Maps
15 Points
Implement the static method wordsMoreThanOnce  which takes an 
ArrayList of words and returns a Map that maps the words from the 
ArrayList to boolean values: the value will be true for a word if it appeared 
two or more times in the ArrayList, and false otherwise.  For the purpose 
of this problem you can use either kind of Map.
Examples (in the following examples order of Map entries is not significant):
words
return value of 
wordsMoreThanOnce(words)
["the", "big", "dog", "big"] {"the"= false, "big"= true, "dog"= false}
["the", "big", "dog", "of", "the", "big", "big", 
"dog]
{"the"= true, "big"= true, "of"= false, "dog"= 
true}
["alright", "alright", "alright"] {"alright"= true}
["the", "big", "dog"] {"the"= false, "big"= false, "dog"= false}
public static Map wordsMoreThanOnce(ArrayList words)
Enter your answer here
Save Answer
Q9 recursion
15 Points
15 Points
Write the recursive method findLast(nums, target) , which takes an 
array of ints and returns the index of the last instance of target  in the 
array.  If target  is not found in the array it returns -1.  (I.e., same problem 
as on MT 1, but you must solve it recursively).  A solution that uses a loop will 
receive little to no credit.  Examples:
nums target
return value of
 findLast(nums, target)
[10, 100, 10, 13, 7] 10 2
[10, 100, 8, 9] 32 -1
[10, 100, 8, 9] 10 0
[9, 9, 9, 9] 9 3
[] 9 -1
Hints: (1) you will need to create a helper method to do the recursion;  (2) a 
solution that visits the array elements from right to left (last to first) may be 
easier to code and run faster for some cases, but you do not have to solve 
the problem that way to get full credit.  
public static int findLast(int[] nums, int target) {
Enter your answer here
Save Answer
Save All Answers Submit & View Submission #