CSE 12
Winter 2024
Midterm Exam
To achieve 100% for the exam: 30 out of 32
This exam is closed book, closed notes. You can use any empty spaces on this paper as scratch and you should
mark your answers on the answer sheet clearly. You should tear off the answer sheet on the last page. All
pages in this exam book must be turned in, including all the scratch papers we have provided. We only grade
work on the answer sheet. Work written on other parts of the exam papers won’t be graded.
By signing your name below, you agree that you will not discuss any part of this exam with anyone who is not
currently taking the exam in this room until after the exam grades have been returned. This includes posting
any information about this exam on piazza or any other social media. Discussing any aspect of this exam with
anyone outside of this room constitutes a violation of the academic integrity agreement for CSE 12.
Signature: ______________________________________________
Name (please print clearly):________________________________________
PID:___________________________________________
DO NOT OPEN THIS EXAM UNTIL YOU ARE INSTRUCTED TO DO SO.
PLEASE STOP WRITING ON THE EXAM ONCE THE TIME IS UP. FAILURE TO DO SO WILL
RESULT IN A 0 FOR THIS EXAM.
1
Concept 1: Java Generics
Please look at the following generic class and answer the questions
public class GenericProblem<T extends Comparable<T>> {
private T elements[];
public GenericProblem(){
elements = _____________________________ //problem 1
}
public GenericProblem(T[] arr) {
elements = arr;
}
public T findMax(){
T result = null;
for(int i = 0; i < elements.length; ++i){
if(________________________________){//problem 2
result = elements[i];
}
}
return result;
}
public static void main(String[] args) {
String[] arr = new String[]{"cse12", "cse15L", "CSE8A"};
GenericProblem<String> ref = new GenericProblem<>(arr);
Integer[] arr2 = new Integer[]{1, 5, 4, 2, 10};
________________________ = new GenericProblem<>(arr2);//problem 3
}
}
1. What should be the correct statement to create an array object of size 12 in this blank?
A. new T[12]; B. new Object[12]; C. (T[]) new Object[12]; D. More than one choices are correct
2. What is the correct statement to allow this code to find the max element in the instance array? You can
assume that null reference is treated as the smallest of all possible data and elements array don’t have null
data.
A. elements[i].compareTo(result) < 0 B. elements[i].compareTo(result) > 0
C. elements[i].compareTo(result) == 0
3. True or false: we can fill the blank using the reference variable ref without causing an error.
A. True B. False
Concept 2: JUnit and Testing
Suppose we need to write a tester for size() method in the MyArrayList class we write for PA2. Answer the
questions about the following tester.
//other codes omitted
MyArrayList<Integer> ref;//an instance variable of the tester class
@Before
public void setup(){
Integer arr[] = new Integer[]{1, 4, 3, 2};
ref = new MyArrayList<>(arr);
}
@Test
public void testSize(){
assertEquals(4, ref.size());
}
2
4. True or False: the setup method will be called automatically before the testSize method is excuted when
the tester runs.
A. True B. False
5. True or False: the testSize method in its current form is sufficient to test if the size() method works
correctly.
A. True B. False
Concept 3: LinkedList Iterator
Problems 6 - 9 are about the following iterator and we use dummy nodes in our linked list. None of the
questions are sequential to each other.
6. True or False: Given the current state of the iterator, the most recent call to move the iterator must be
it.previous() instead of it.next()
A. True B. False
7. What should be the correct value for idx given the
current state of the iterator?
A. 0 B. 1 C. 2 D. 3 E. It can't be determined.
8. True or False: Given the current state of the iterator,
if we call it.remove() which node will be removed?
A. 45 B. 12 C. 88 D. Exception will happen
9. True or False: Given the current state of the iterator, if we call it.previous(), value 45 will be returned.
A. True B. False
Concept 4: Linked List
Given the following constructor and function calls, please answer the following questions.
class Node<E> {
E data;
Node next;
Node prev;
public Node() {
data = null;
next = null; 10. True or False: n0.next == n1
prev = null; A. True B. False
}
public Node(E theData, Node other) { 11. True or False: n2.prev == n1
this.data = theData;
if(other==null){ A. True B. False
prev = null;
next = null; 12. True or False: n1.prev==n2
} A. True B. False
next = other;
prev = other.prev;
other.prev = this;
}
public static void main(String[] args) {
Node<Integer> n0 = new Node<Integer>();
Node<Integer> n1 = new Node<Integer>(5, n0);
Node<Integer> n2 = new Node<Integer>(6, n1);
3
}
}
Concept 5: Runtime analysis.
13. True or False: If we don’t consider tight bound, If 𝑓(𝑛) ∈ 𝑂(𝑛2 ) , then 𝑓(𝑛) ∉ 𝑂(𝑛)
A. True B. False
14. What is the runtime of the following code overall with respect to n? We are looking for the tightest bound
for the worst-case scenario.
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
arr[i] = arr[j]%2;
}
}
A. O(n) B. O(n2) C. O(nlogn) D. O((log(n))2) E. None of the answers is correct
15. What is the runtime of the following code overall with respect to n? We are looking for the tightest bound
for the worst-case scenario.
for (int i = n; i > 0; i/=2){
for (int j = 1; j < n; j++){
cnt++;
}
}
A. O(n) B. O(n2) C. O(nlogn) D. O( (log(n))2) E. None of the answers is correct
16. What is the runtime (tight bound) of traversing an array list of size n using the get method?
A. O(n) B. O(n2) C. O(nlogn) D. O( (log(n))2) E. None of the answers is correct
4
Concept 6: ArrayList (Coding question 1, 6 pts)
In PA2, we wrote the generic MyArrayList class. A part of the generic class is shown below. Please complete the
remove method. You can assume that all other functions are already implemented correctly.
public class MyArrayList<E> implements MyList<E>{
Object[] arr;
int size;
//assume other functions are correctly implemented.
public E remove(int index){
//implement this method on the provided space on the answer sheet
}
}
Description of the remove method
5
Concept 7: LinkedList (Coding question 2, 10 pts)
In PA3, we wrote a LinkedList class. In this problem, please implement the method to add a node with data at the
given index. We assume we have dummy nodes. You can assume that you can access the next, prev and data
instance variables of a Node object in this method.
public class LinkedList<E>{
protected class Node {
E data;
Node next;
Node prev;
public Node(E element) {
// Initialize the instance variables
this.data = element;
this.next = null;
this.prev = null;
}
//other methods omitted
}
int size;
Node head;
Node tail;
public void add (int index, E data){……}
write your codes on the answer sheet
}
Description of the add method
6
Concept 6: ArrayList coding question
public E remove(int index){
}
7
Concept 7: LinkedList coding question
public void add (int index, E data){
