Cse214 Computer Science Ii

CSE214 COMPUTER SCIENCE II

SAMPLE MIDTERM EXAM

1. For each of the following algorithms performed on a collection of n integers, write down its

worst-case order of complexity as a function of n in simplified Big O notation. Assume that

the most efficient data structure and algorithm are used.

Algorithm / Worst-case order of complexity
Pop an element from a stack, where the stack is implemented using a singly-linked list and the tail node is always top of the stack.
Cloning a doubly-linked list
Finding the first occurrence of a given target in an integer array.
Cloning a LongIntegers with n digits, as implemented in the first programming assignment.
Adding two LongIntegers with n digits, as implemented in the first programming assignment.

2.1 Counting only assignment statements as operations, what is the exact number of operations

executed by the following code fragment in terms of n?

x = n;

while (x > 0) {

z = 0;

while (z <= 6) ______

z = z + 2; number of operations

x = x - 1;

}

2.2 What is the order of complexity of the code fragment in problem 2.1 as a function of n?

(a) O(n) (b) O(n2) (c) O(n3) (d) O(n log n) (e) none of these answers

3.1 Counting only assignment statements as operations, what is the order of complexity of the

following code fragment as a function of n?

x = 1; (a) O(1)

while (x < n) (b) O(n)
x = x + x; (c) O(log n)

(d) O(n2)

(e) none of these answers

3.2 Which of the following postfix expressions is equivalent to the infix expression

A / B + C * (D - E / F) - G

if it is converted using the algorithm that we discussed in class?

(a) ABC+/D-E/*G- (b) ABC+/DEF/-*G- (c) AB/CDEF/-*+G-

(d) AB/CD*EF/-+G- (e) none of these answers

3.3 What is the value of the following prefix expression (assuming single digit numbers and integer

division)? + 5 * + / 6 2 3 + 4 1

(a) 25 (b) 29 (c) 30 (d) 35 (e) none of these answers

4.1 A program P processes n input data values using n2 operations in 3 minutes. How long will P take

to process 5n input data values?

(a) 9 min. (b) 15 min. (c) 25 min. (d) 75 min. (e) none of these answers

4.2 Let A = 6. What is the value of B after the statement B = A + A + (A++) * 2 ; is executed in Java.

(a) 20 (b) 24 (c) 26 (d) 28 (e) none of these answers

4.3 Consider the IntArrayBag class discussed in class, where an array is used for our implementation. The following new IntArrayBag method supposedly determines if the given parameter is equal to this instance of IntArrayBag. What is wrong with this method?

public boolean equals(Object obj) {

if (obj instanceof IntArrayBag) {
IntArrayBag candidate = (IntArrayBag) obj;
return (candidate.data.equals(data));
}

else return false;

}

(a) The given parameter must be passed as an instance of IntArrayBag, not as an Object.

(b) This method does not have direct access to the data variable of the given parameter.

(d) The expression (candidate.data.equals(data))does not correctly compare the contents of

two bags as required in this method.

(e) none of these answers

4.4 Which of the following code fragments correctly inserts newNode after the cursor node in a doubly-linked list. You may assume that list is not empty and cursor is not the tail node, meaning that there is at least one node after the cursor. The usual getData, setData, getNext, setNext, getPrev, setPrev methods are already defined.
(a) newNode.setNext(cursor.getNext()); (e) none of these answers

newNode.setPrev(cursor);

(b) cursor.setNext(NewNode);

newNode.setNext(cursor.getNext());

newNode.getNext().setPrev(newNode);

newNode.setPrev(cursor);

cursor.getNext().setPrev(newNode);

cursor.setNext(newNode);

(d) cursor.getNext().setPrev(newNode);

cursor.setNext(newNode);

newNode.setNext(cursor.getNext());

newNode.setPrev(cursor);

5. USE THE FOLLOWING INFORMATION TO ANSWER PROBLEMS 5.1-5.4:

DoubleStack class implements two stacks of integers named left and right that share the same data array. If the stacks are not empty, bottom of the left stack is stored in data[0],and bottom of the right stack is stored in data[CAPACITY-1]. The variables topLeft and topRight refer to the top elements of left and right stacks respectively. Each stack grows towards the other end, but topLeft and topRight should not pass each other. There is no limit for the number of elements pushed on each stack. However the total number of elements in both stacks should not exceed CAPACITY, so it is possible that one stack is empty and the other stack holds CAPACITY data values. Note that pushRight and popRight handle the operations on the right stack, and similarly pushLeft and popLeft handle the operations on the left stack (not shown here). In the following example, the total CAPACITY is 11, and left stack holds 51,52 and 53 and the right stack holds 61,62,63 and 64.

0 1 2 3 4 5 6 7 8 9 10

51 / 52 / 53 / 64 / 63 / 62 / 61

topLeft topRight

public void DoubleStack(){ /*** constructor for this class ***/

data = new int[CAPACITY];

topLeft = -1; topRight = CAPACITY;

}

public void pushRight(int value) throws StackException {

if ( a ) throw new StackException("OVERFLOW");

b ;

data[topRight] = value;

}

public int popRight() throws StackException {

if ( c ) throw new StackException("UNDERFLOW");

int answer = data[topRight];

d ;

return answer;

} /*** Note: pushLeft and popLeft are not shown here ***/

5.1 What is the correct expression for a?

(a) topRight == CAPACITY-1 (b) topRight == 0

(e) none of these answers

5.2 What is the correct expression for b

(a) topRight-- (b) topRight++

(e) none of these answers

5.3 What is the correct expression for c?

(a) topLeft == CAPACITY-1 (b) topLeft == -1

(e) none of these answers

5.4 What is the correct expression for d?

(a) topRight++ (b) topRight--

(e) none of these answers

6. USE THE FOLLOWING INFORMATION TO ANSWER PARTS 6.1-6.4:

We wish to add a method to the IntList class to determine whether this list is sorted in an increasing order. The IntList is a singly-linked list of IntNode nodes, where each node has a data and a link field, and the IntNode class contains the usual getData, setData, getLink, and setLink methods. Additionally, the IntList has a head reference to the first node of the list and a tail reference to the last node of the list. You may assume that a list with only one node is sorted. An incomplete implementation is shown below.

public boolean isSorted() throws EmptyListException { IntNode nodePtr = head;

if ( a ) throw new emptyListException("ERROR");

if ( b ) return true;

while ( c ) {

if (nodePtr.getData()>= nodePtr.getLink().getData())

return false;

d ;

}

return true;

}

6.1 What is the correct expression for a?

(a) this == null (b) head == null
(c) nodePtr == head (d) head == tail

(e) none of these answers

6.2 What is the correct expression for b?

(a) nodePtr == tail (b) head != tail
(c) nodePtr.getLink() == tail (d) head.getData() == 0
(e) none of these answers

6.3 What is the correct expression for c?

(a) nodePtr != null (b) nodePtr.getLink().getLink()!= null
(c) nodePtr != tail (d) nodePtr.getLink() != tail
(e) none of these answers

6.4 What is the correct statement for d?

(a) nodePtr = tail;

(b) nodePtr.setLink(nodePtr.getLink());

(d) nodePtr = nodePtr.getLink().getLink();
(e) none of these answers

7. Consider the following infix expression: 8 – (3 * (2 + 5)) / 6 + 9

(a) Convert the expression to prefix notation by hand. ______

(b) Convert the expression to postfix notation by hand. ______

8. Consider a singly-linked list of IntNode nodes where each node has a reference to the next node in the list. There is also a head reference, but no tail reference. The IntNode class contains the usual getData, setData, getLink, and setLink methods.

Complete the following Java method for this list as efficiently as possible in terms of execution time.

public IntNode getNthNode(int n) throws IllegalArgumentException

Returns the reference to the node in nth position of this list if it exists; otherwise, returns null. Make

sure you test for empty list and the precondition. Note that head refers to the node in position one.

Precondition: n is a positive number.

9.1 The expression (int)(Math.random()*12 + 3.0) generates a random integer in what range?

(a) [0,12) (b) [3,12) (c) [0,15) (d) [3,14] (e) none of these answers

9.2 The following code shows the incomplete implementation of the method occurs defined in the

BooleanSource class as described in lecture notes.

public boolean occurs() {

double temp = Math.random();

return ( a );

}

Assuming that the given probability is a fixed number equal to 0.25, what is the correct expression for a?

(a) temp>0.25 (b) temp < 0.75 (c) temp>=0.40&temp<0.65

(d) temp<0.25||temp>=0.75 (e) none of these answers

USE THE FOLLOWING INFORMATION TO ANSWER PROBLEMS 10.1-10.3:

The following code shows the incomplete implementation of two methods of a priority queue class. To dequeue an element with O(1) complexity, the queue is maintained sorted in decreasing order at all times. The elements are removed as usual from the front of the queue, but instead of inserting (enqueueing) to the rear of the queue, a new element is inserted in a sorted array (no sorting algorithm is used). Assume that the size of the data array is unlimited.

public int dequeue() throws Exception {

int answer;

if (front < 0) throw new Exception;

answer = data[front];

if (front == rear){

front = -1; rear = -1;

}else front++;

return(answer);

}

public static void enqueue(int item) {

int i, position;

if (rear == -1) {

front = 0; rear = 0; data[rear] = item;

return;

}

position = front;

for (i=front; i <= rear; i++) {

if ( a )

position++;

else

break;

}

for ( b ; i > position; i--) {

data[i] = data[i-1];

}

c ;

rear++;

}

10.1 What is the correct expression for a?

(a) item > data[i] (b) item < data[i] (c) item <= data[i] (d) item >= data[i] (e) none of these answers

10.2 What is the correct expression for b?

(a) i=front + 1 (b) i=rear + 1 (c) i=rear

(d) i=front (e) none of these answers

10.3 What is the correct expression for c?

(a) data[rear]=item (b) data[front]=item (c) data[rear++]=item

(d) data[position]=item (e) none of these answers