CS 61B Midterm 1 Problem 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS 61B Midterm 1
Problem 2
a) countChar (16 points). Fill in the countChar method below so that it counts the number of instances of the given character. For example, countChar("exxon", !x !) should return 2, and countChar("zebraZzz", !Z !) should return 1. You may use a maximum of 10 blank lines for this problem. Note: These 10 lines do not include the method signature nor the closing brace, i.e. these lines are not initially blank.
/** Counts the number of occurrences of c in a .
For example countChar(" moo ", ! o !) would return 2.
You may assume the String is not null .
*/
public static int countChar(String a, char c) {
}
// Reminder: s . charAt(0) gets the 0th character of s
// Our solution uses the 7 blank lines provided .
// Yours may use more or less (up to the maximum of 10) .
b) XComparator (18 points). Suppose we want to build a comparator XComparator that compares two strings based on the number of times lowercase ‘x’ appears in the string. For example an XComparator would consider “exxon” to be greater than “some axons”. Below, implement the XComparator. For this and the remaining questions, assume the countChar(String a, char c) method from part a has been imported and works correctly, i.e. you can call countChar("exxon", !x !) and expect to get back 2.
Recall from lecture that the compare method of the Comparator interface in Java returns a negative number if the first argument is less than the second,
0 if they are equal, and a positive number if the first argument is greater, e.g. compare("exxon", "some axons") would return a positive number. You may assume none of the parameters to compare are null.
public class XComparator implements Comparator<_________> {
/** Compares two strings based on the number of xs in
the strings . For example exxon > axon , because 2
occurrences of x is more than 1 occurrence of x . */ public int compare (____________ , _____________) {
} // Our solution uses 1 line . Yours may use more .
}
c) CharCountComparator (22 points) Now suppose we want to build a more general character counting comparator whose constructor takes a character as an argument, and whose compare method compares two strings based on the count of that character. For example, if we create CharCountComparator c = new CharCountComparator( !z !), then c .compare("mazzy", "lazer") would consider mazzy larger since it has two ‘z’s vs. lazer’s single ’z’. You may assume none of the parameters to compare are null.
public class CharCountComparator implements Comparator<_________> {
// our solution has one instance variable, yours doesn ! t have to .
public CharCountComparator(char givenC) {
// our constructor has one line, yours doesn ! t have to .
}
/** Compares two strings based on the number of occurrences of the given character . */
public int compare (____________ , ____________) {
} // our compare method is 1 line long . yours may use more . }
d) WordFinder (36 points). Now complete the following code that will read in all the words from a words.txt file and return the word with the most ’z’s.
You may use a maximum of 11 blank lines for this problem.
public class WordFinder {
public static void main(String[] args) {
In in = new In ("words .txt");
String[] words = in .readAllStrings();
String wordWithMostZs = findMax (words, ________________________); System .out .println (wordWithMostZs);
}
/** Finds the maximum string in the array of strings using the
given comparator . You may assume the array is of length at least 1, and that none of the strings are null . If there is a tie , then break the tie arbitrarily . For example , if all the
strings are equal according to the comparator , you can return any of the strings . */
private static String findMax(String[] strings, Comparator<_____________> cmp) {
} // our solution uses 8 blank lines . yours may use up to 11 . } // findMax must work for any provided comparator! That is,
// it cannot be hard coded to look for strings with the most zs .
Problem 3
a) (50 points) Suppose we define the following strange class. Note that the equals method has the signature equals(Student other) . Recall from lecture
11 that the Object class’s equals method has the signature equals(Object other). That is, this class is not overriding the equals method!
public class Student {
public String name;
public int SID;
public Student(String n, int id) {
name = n;
SID = id;
}
public boolean equals (Student other) {
if (name .equals(other .name) &&
SID == other .SID) {
return true ;
}
return false ;
}
}
Suppose we define five Java variables as shown:
Student sB = new Student ( "Borf" , 123);
Student sG = new Student ( "Gorf" , 123);
Student sB2 = new Student ( "Borf" , 123);
Object oG = sG;
Object oB2 = sB2;
For each of the lines below, fill in the bubble for the return of the expression. Or if the line has a compile or runtime error, fill in the “runtime error” (RE) or “compile error” (CE) bubble instead. Not all answers may be used.
1. sB .equals(sG)
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
2. sB .equals(sB2)
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
3. sB == sB2
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
4. sG .equals(oG)
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
5. sG == oG
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
6. sG .equals((Student) oG)
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
7. sB .equals(oB2)
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
8. sB == oB2
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
9. sB .equals((Student) oB2)
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
10. ((Object) sB2) .equals((Student) oB2)
● [ ] true
● [ ] false
● [ ] compile error
● [ ] runtime error
b) (8 points) Suppose we fix the equals method so that it takes an Object as an argument instead of a Student. Once we’ve done that, we are now properly overriding the equals method.
@Override
public boolean equals(Object o) {
Student other = (Student) o;
if (name .equals(other .name) && SID == other .SID) {
return true ;
}
return false ;
}
After making this change, which of the following returns true that did not return true before? Only one is correct.
● [ ] sB .equals(sG)
● [ ] sB .equals(sB2)
● [ ] sB == sB2
● [ ] sG .equals(oG)
● [ ] sG == oG
● [ ] sG .equals((Student) oG)
● [ ] sB .equals(oB2)
● [ ] sB == oB2
● [ ] sB .equals((Student) oB2)
● [ ] ((Object) sB2) .equals((Student) oB2)
c) (8 points) The equals method above does not do all of the things that we said that an equals method should do in lecture. Describe at least one improvement we could make below:
Problem 4
DMSDogs (28 points) Suppose we define the classes below:
public class Dog {
public void bark() {
System .out .println("bark");
}
}
public class Puppy extends Dog {
public void bark() {
System .out .println("lil bark");
}
}
public class DogLover {
public void pet(Dog d) {
System .out .print("pet dog");
d .bark();
}
public void pet(Puppy p) {
System .out .print("pet puppy");
p .bark();
}
}
public class PuppyLover extends DogLover {
public void pet(Puppy p) {
System .out .print("pup love");
p .bark();
}
}
What will be the output of the lines of code below?
public static void main(String[] args) {
PuppyLover pl = new PuppyLover();
Puppy p = new Puppy();
pl.pet(p);
((DogLover) pl) .pet(p);
pl.pet((Dog) p);
((DogLover) pl) .pet((Dog) p);
}
For each call to pet above, notice that multiple things can be printed. Check the boxes for all that is printed. The order in which you check the checkboxes doesn’t matter.
1. pl .pet(p)
● [ ] bark
● [ ] lil bark
● [ ] pet dog
● [ ] pet puppy
● [ ] pup love
2. ((DogLover) pl) .pet(p)
● [ ] bark
● [ ] lil bark
● [ ] pet dog
● [ ] pet puppy
● [ ] pup love
3. pl .pet((Dog) p)
● [ ] bark
● [ ] lil bark
● [ ] pet dog
● [ ] pet puppy
● [ ] pup love
4. ((DogLover) pl) .pet((Dog) p)
● [ ] bark
● [ ] lil bark
● [ ] pet dog
● [ ] pet puppy
● [ ] pup love
Problem 5
AddOnlyList (118 points). Before starting this problem, be aware that for all parts of this problem, you may assume the earlier parts were done correctly and can be used, e.g. feel free to use indexOfI in part b, even if you didn’t get part a correct. You may not need earlier methods for later problems, e.g. get(int i) (part b) may not be useful for addLast (part c).
Suppose we define a new AddOnlyList class as follows:
public class AddOnlyList
private T[] items;
private int size;
public AddOnlyList() {
items = (T[]) new Object[8];
size = 0 ;
}
private int indexOfI (int i, int M) { /* you ! ll write this */ } public T get(int index) { /* you ! ll write this */ }
public void addLast(T item) { /* you ! ll write this */ } private void resize(int newlen) { /* you ! ll write this */ }
}
Instead of treating the array like a circle like you did in ArrayDeque, the AddOnlyList uses an outward-in pattern to store its items, as shown in the figure below:
Figure 1: MidtermArrayDeque Visualization
For an items array of size 8, item 0 in the list goes in index 0, item 1 goes in
index 7, item 2 goes in index 1, item 3 goes in index 6, item 4 goes in index 2,
and so forth. The figure above corresponds to a list whose items are [a, b, c, d] in that order. If we were to add e to the end of the list, it would go in index 2. If we were to add f after that, it would go in index 5.
Fill in the functions indexOfI, get, addLast, and resize.
indexOfI gives the position of the ith element if the size array is of length M. For example if i = 3, and M = 8, then indexOfI(3, 8) is 6. Note that item 3 (‘d’) is in position 6 in the figure above. You may assume that M is a power of 2 that is greater than or equal to 8.
These functions are worth 40, 32, 32, and 14 points, respectively. For indexOfI and get, your solution must fit in the skeleton provided. For addLast and resize you
may usea maximum of 5 and 8 lines respectively. The lines we provide
in addLast and resizedo not add to your line count.
public class AddOnlyList
private T[] items;
private int size;
public AddOnlyList() {
items = (T[]) new Object[8];
size = 0 ;
}
/* DO NOT CHANGE ANYTHING ABOVE THIS LINE . */
private int indexOfI (int i, int M) {
if (______________) {
return ___________ ;
} else {
return ___________________ ;
}
}
public T get(int i) {
return __________________________ ;
}
public void addLast(T x) {
if (size _________________) {
resize(_________ * 2);
}
} // Our addLast code uses 3 blank lines .
// Yours may use less or more up to a max of 5 .
private void resize(int newlen) {
T[] newItems = (T[]) new Object[_______];
items = newItems;
} // Our addLast code uses 5 blank lines .
// Yours may use less or more up to a max of 8 .
}
Problem 6
a) Testing contains (20 points). Suppose we add a method contains to our List61Binterface with the signature below. This method returns true if the given List61B contains the given item. The midterm 1 reference page might be useful for this problem.
default public boolean contains (T x)
Write a JUnit test that verifies that this method works correctly for a list of
length 3. Your test should verify that it works for all three items in the list, and that it works correctly for an input which is not in the list. Assume all JUnit classes needed have been imported.You may use a maximum of 8 lines for this problem.
@Test
public void testContains () {
AList
} // Our test uses the 7 lines provided above,
b) contains (30 points) Write the method contains. It should work for all possible inputs, not just your JUnit test above. Your method must be non-destructive. You may not need all lines. You may use a maximum of 8 lines for this problem.
public interface List61B
public void addLast(T x);
public T getLast();
public T get(int i);
public int size();
public T removeLast ();
public void insert (T x, int position);
public void addFirst(T x);
public T getFirst();
default boolean contains (T x) {
} // Our code uses 6 lines .
}
c) Testing itemsNotIn (35 points). Suppose we add a method itemsNotIn to our List61B interface with the signature below. This method returns a list containing only the items that are in the current list, but not in the List61B pro- vided as an argument. The items in the returned list should be in the same order. Your midterm 1 reference sheet might be useful for this problem. This method should be non-destructive.
default List61B
For example, if you have a list x that contains the numbers 1 through 100 and a list ywhich contains the numbers 80 through 120, then x .itemsNotIn(y) would create a new list that contains the numbers 1 through 79, in that order. After this function call, x and yshould remain unchanged.
Write a JUnit test that verifies that this method works correctly on the lists given in the starter code. You do not need to test that L1 and L2 are unchanged. You
may use a maximum of 8 lines for this problem.
@Test
/** Your test does not need to verify that itemsNotIn is
non- destructive ! In real life , you would , probably as
a separate JUnit test . */
public void testItemsNotIn () {
AList
L1 .addLast (0);
L1 .addLast (1);
L1 .addLast (2);
AList
L2 .addLast (1);
L2 .addLast (4);
L2 .addLast (5);
} // Our test uses 4 lines above
d) itemsNotIn (35 points) Write the method itemsNotIn. It should work for all possible inputs, not just your JUnit test above. Your method must be non-destructive. You may not need all lines. You may assume the contains method from part b is available and works correctly, even if you did not complete part b. You may use a maximum of 10 lines for this problem.
public interface List61B
public void addLast(T x);
public T getLast();
public T get(int i);
public int size();
public T removeLast ();
public void insert (T x, int position);
public void addFirst(T x);
public T getFirst();
default boolean contains (T x) { /* not shown */ }
default List61B
} // Our code uses 8 lines .
}
Problem 7
a) removeNode (25 points). Suppose we have a version of the LinkedListDeque class from project 1, but hard-coded to use integers instead of a generic type. This new version is called IntLinkedListDeque. Its instance variable and Node class are as shown:
public class IntLinkedListDeque {
private Node sentinel;
private class Node {
private int value; // Note: Value for a node is an integer, not a generic type! private Node next, prev;
// constructor not shown
}
... // constructor and methods not shown
}
Suppose we add a private removeNode method to IntLinkedListDeque that
removes the specified node and keeps the list contiguous. The signature for this
method is:
private void removeNode(Node t)
Assume that we’re using the circular sentinel topology described in lecture and
recommended for project 1A. Write the removeNode method below. You may
assume that t is not null and that t is a valid node in the list. There’s no need
to update the size, because IntLinkedListDeque does not have a size variable.
As an example, suppose we have a IntLinkedListDeque containing three Nodes with values 1, 2, and 3. Now suppose we call removeNode(sentinel .next), the front item of the list would be removed, and the list would have two Nodes with values 2 and 3. You may use a maximum of 4 lines for this problem.
/** Removes the specified node from the list .
You may assume that t is not null .
You may assume that the node is a valid node in the list . */
private void removeNode(Node t) {
} // Our solution is 2 lines .
// Yours may use less or more, up to the maximum of 4 .
b) removeOneIterative (40 points). Suppose we want to provide a public facing removemethod with the signature shown below:
public boolean removeOneIterative (int x)
This method should return true if the item was located and removed, and false
if the item was not in the list. Fill in the removeOneIterative move method below. Your method should only delete the first instance of x. For example, if the list contains
3 , 4 , 5 , 6 , 4 , 5 , 6
and you call
removeOneIterative(4)
on that list, the list would now contain
3 , 5 , 6 , 4 , 5 , 6
You may use the removeNode method from part a, even if you did not complete part a correctly.
You may use a max
2023-02-13