CS61B: Data Structures Midterm #1, Spring 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS61B: Data Structures
Midterm # 1, Spring 2021
1. Cal Central.
a) (30 points). Let's start with a short helper method that will be useful in later questions. Fill in public static boolean contains(int[] a, int x) so it returns true if and only if the integer array a contains the integer x. Your solution may use at most 9 lines. (Clarification: you can assume a will never be null.)
public class Utils {
public static boolean contains(int[] a, int x) {
}
}
For the remainder of this problem we'll be trying to complete the CalStudent and CourseCatalog classes given below. Quick note: You might observe that these classes are poorly designed (public instance variables and a bad choice of data structure). We'll address this in part d of this problem.
public class CourseCatalog {
public int[] courses;
public CourseCatalog() {
courses = new int[0];
}
public void offerNewCourse(int courseid) {
/* ... */
}
}
public class CalStudent {
public String name;
public int[] courses;
public int numOfCourses;
public CalStudent(String name) {
this.name = name;
this.courses = new int[4];
numOfCourses = 0;
}
public void addCourse(int courseid, CourseCatlog cc) {
/* ... */
}
}
The behavior we are interested in is as follows:
• Courses at Cal are referred to by their integer courseid.
• To add a course for CalStudent x , we call the x.addCourse(int courseid, CourseCatalog
cc) method. If the course obeys the three restrictions below, the course is added to the first available spot in x's length 4 courses array. If it does not obey the restrictions, nothing happens.
1. Students may only take courses that are available in the course catalog.
2. Students may only be in at most 4 courses at the same time.
3. Students cannot add the same class more than once.
• To offer a new course to a CourseCatalog called cc, we call the cc.offerNewCourse(int courseid) method. If the course is not already in the catalog, it is added. If it is already in the catalog, nothing happens.
Here is an example usage of these classes:
CourseCatalog cc = new CourseCatalog(); -> initially empty
CalStudent omar = new CalStudent();
omar .addCourse(22076, cc); // nothing added, invalid course
cc .offerNewCourse(22076); // 22076 added to course catalog
cc .offerNewCourse(22076); // nothing added, 22076 already exists
cc .offerNewCourse(24890); // 24890 added to course catalog
omar.addCourse(22076, cc); // omar.courses: [22076, 0, 0, 0]
omar.addCourse(22076, cc); // omar.courses: [22076, 0, 0, 0] (no change)
omar.addCourse(24890, cc); // omar.courses: [22076, 24890, 0, 0]
cc.offerNewCourse(22078); // 22078 added to course catalog
cc .offerNewCourse(33150); // 33150 added to course catalog
cc.offerNewCourse(28108); // 28108 added to course catalog
omar.addCourse(22078, cc); // omar.courses: [22076, 24890, 22078, 0]
omar.addCourse(33150, cc); // omar.courses: [22076, 24890, 22078, 33150]
omar.addCourse(28108, cc); // [22076, 24890, 22078, 33150] (no change)
b) (120 Points) First, let's implement the void offerNewCourse(int courseid) method. You may use your answer to part a (Utils.contains) as if it is correct. Do not worry about efficiency.
public class CourseCatalog {
public int[] courses;
public CourseCatalog() {
courses = new int[0];
}
public void offerNewCourse(int courseid) {
if (___________________________________________) {
int[] newArr = new int[__________];
for (________________________________________) {
_________________________________________;
_____________________________________________;
_____________________________________________;
}
}
c) (60 Points) Next, lets implement the void addCourse(int courseid) method. You may use your answer to part a (Utils.contains) as if it is correct, and you may assume that the CourseCatalog has been correctly created. Do not worry about efficiency. Recall the && operator is the equivalent of “and” in Python or the equivalent of the & operator in MATLAB.
public class CalStudent {
public String name;
public int[] courses;
public int numOfCourses;
public CalStudent(String name) {
this.name = name;
this.courses = new int[4];
numOfCourses = 0;
}
public void addCourse(int courseid, CourseCatalog cc) {
if (_____________________________________________) {
_____________________________________________;
_____________________________________________;
}
}
d) (30 Points) The design of the classes above is poor. One issue is that the classes expose their instance variables as public. Instead, access to these variables should be private and the classes should provide methods that do semantically useful tasks, e.g. the CourseCatalog might have a boolean courseNumberExists(int i) method.
Another significant issue is the poor choice of data structure, specifically int[] in both classes. The resulting code is awkward and overly verbose. As we said in the first lecture "Good programmers care about the data structures [in their code]." One better choice of data structure would have been a List. Give one reason why a List is better.
List Advantage: _________________________________________________________________
Note that later in 61B, we will learn about the Set, which is an even better data structure for this task than a List.
2. WWJD (120 points). Consider the code below:
1: public class Egg {
2 : public String owner;
3: public static String staticOwner;
4:
5: public Egg(String name) {
6: this.owner = name;
7: staticOwner = name;
8: }
9:
10: public void weirdExchange(String borrower, Egg g2) {
11: String lender = this .owner;
12: this .owner = borrower;
13: g2.owner = lender;
14: g2 = new Egg("Omar");
15: System.out .println("g2 owner: " + g2 .owner);
16: }
17:
18: public static void main(String[] args) {
19: Egg g1 = new Egg("Itai");
20: Egg g2 = new Egg("Connor");
21:
22: String p1 = "Linda";
23: g1.weirdExchange(p1, g2);
24: System.out .println("g1 owner: " + g1 .owner);
25: System .out .println("g2 owner: " + g2 .owner);
26: System .out .println("Egg owner: " + Egg .staticOwner);
27: }
28:}
What will be printed when lines 23, 24, 25, and 26 execute?
For each line, check the bubble for the correct output or for "Error" if the line causes an error of any kind. If a line causes an error, ignore it and still consider the output of lines below it.
Output printed when line 23 executed: |
○ g2 owner: Itai ○ g2 owner: Connor ○ g2 owner: Linda ○ g2 owner: Omar ○ Error |
Output printed when line 24 executed: |
○ g1 owner: Itai ○ g1 owner: Connor ○ g1 owner: Linda ○ g1 owner: Omar ○ Error |
Output printed when line 25 executed: |
○ g2 owner: Itai ○ g2 owner: Connor ○ g2 owner: Linda ○ g2 owner: Omar ○ Error |
Output printed when line 26 executed: |
○ Egg owner: Itai ○ Egg owner: Connor ○ Egg owner: Linda ○ Egg owner: Omar ○ Error |
3. WWJDMS (120 points). Suppose we define the classes below:
public interface Instrument {
default public String getName() {
return "instrument";
}
}
public class Guitar implements Instrument {
public String getName() {
return "guitar";
}
}
public interface Music {
default public void play(Instrument i) {
System .out .println("music on a " + i .getName());
}
}
public class Rock implements Music {
public void play(Instrument i) {
System .out .println("rock on a " + i .getName());
}
public void play(Guitar g) {
System .out .println("RPG");
}
}
public class Jota implements Music {
public void play(Guitar g) {
System .out .println("JPG");
}
}
For each of the problems below, assume we have declared variables i and g as follows:
Instrument i = new Guitar();
Guitar g = new Guitar();
a) (30 Points) What will be the output of the two calls to play below? If the first line causes an error, ignore it and still consider the output of the second line.
Rock r = new Rock();
r.play(i);
r.play(g);
r.play(i); |
○ music on a instrument ○ music on a guitar ○ rock on a guitar ○ RPG ○ Error |
r.play(g); |
○ music on a instrument ○ music on a guitar ○ rock on a guitar ○ RPG ○ Error |
b) (30 Points) What will be the output of the two calls to play below? If the first line causes an error, ignore it and still consider the output of the second line.
Music mr = new Rock();
mr.play(i);
mr.play(g);
mr.play(i); |
○ music on a instrument ○ rock on a instrument ○ RPG ○ Error |
○ music on a guitar ○ rock on a guitar |
mr.play(g); |
○ music on a instrument ○ rock on a instrument ○ RPG ○ Error |
○ music on a guitar ○ rock on a guitar |
c) (30 Points) What will be the output of the two calls to play below? If the first line causes an error, ignore it and still consider the output of the second line.
Jota j = new Jota();
j.play(i);
j.play(g);
j.play(i); |
○ music on a instrument ○ JPG ○ Error |
○ music on a guitar |
j.play(g); |
○ music on a instrument ○ JPG ○ Error |
○ music on a guitar |
d) (30 Points) What will be the output of the two calls to play below? If the first line causes an error, ignore it and still consider the output of the second line.
Music mj = new Jota();
mj.play(i);
mj.play(g);
mj.play(i); |
○ music on a instrument ○ JPG ○ Error |
○ music on a guitar |
mj.play(g); |
○ music on a instrument ○ JPG ○ Error |
○ music on a guitar |
4. BLList. (310 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 later, e.g. feel free to use getNode from part c on remove from part e.
Suppose we have the BLList class defined below as follows. The addLast and get methods behave exactly like you'd expect from a list, i.e. if we call addLast(5) then addLast(10), we'll end up with [5, 10], i.e. get(0) will return 5 and get(1) will return 10.
public class BLList
public void addLast(T item) // adds an item to the end of the list
public T get(int i) // gets the ith item
public void remove (int i) // removes the ith item
public int size() // returns the number of items
}
a)&nb
2023-02-13