Binary Cipher
175 Multiple-Choice Questions in Java
Below are 175 questions to help you prepare for taking the AP Computer Science A test.2005 2004 2003 2002 2001 2000 1999
2005
1.
What is the size of a double variable in Java?
2 bytes
4 bytes
8 bytes
It depends on the compiler setting
It depends on the operating system
2.
What is displayed by
System.out.println(“1” + new Integer(2) + 3);
The statement has a syntax error and won’t compile
6
15
123
ClassCastException
3.Which of the following best describes the set of all pairs of values
for boolean variables a and b, such that
(!a && b) == !(a || b)
evaluates to true?
Empty set
Only one pair: a == true, b == false
Two pairs in which a == true
Two pairs in which a != b
All four possible combinations of values
4. (AB)
When you try to compile MyClass, the java compiler gives an error message
MyClass is not abstract and does not override abstract method <some method> in java.util.Comparator
Which of the following is <some method> in the error message?
equals(myClass)
compareTo(myClass)
compare(myClass, myClass)
compareTo(java.lang.Object)
compare(java.lang.Object, java.lang.Object)
5.
Consider the following classes:
public class Year2005
{
public String toString() { return “2005”; }
}
public class Test2005 extends Year2005
{
public void print()
{
<missing statement>
}
}
Which of the following could replace <missing statement> so that Test2005 would compile with no errors and
Test2005 test = new Test2005();
test.print();
would display 2005?
I. System.out.println(new Year2005());
II. System.out.println(new Test2005());
III. System.out.println(this);
I only
II only
I and II
II and III
I, II, and III
6.
What is the value of a[1] after the following code is executed?
int[] a = {0, 2, 4, 1, 3};
for (int i = 0; i < a.length; i++)
a[i] = a[(a[i] + 3) % a.length];
0
1
2
3
4
7.
Consider the method
public String mystery(String s)
{
String s1 = s.substring(0,1);
String s2 = s.substring(1, s.length() – 1);
String s3 = s.substring(s.length() – 1);
if (s.length() <= 3)
return s3 + s2 + s1;
else
return s1 + mystery(s2) + s3;
}
What is the output of
System.out.println(mystery(“DELIVER”));
DELIVER
DEVILER
REVILED
RELIVED
DLEIEVR
8. (AB)
Consider the following code segment:
List list = new LinkedList();
list.add(“[“); list.add(“A”); list.add(“]”);
System.out.println(list);
ListIterator it = list.listIterator();
while(it.hasNext()
{
if (“[“.equals(it.next()) || “]”.equals(it.next()))
it.remove();
else
it.add(“*”);
}
System.out.println(list);
The first output line is
[[, A, ]]
What is the second output line?
[A]
[A, B]
[B, A]
ClassCaseException
NoSuchElementException
9.
Which of the following is not a method of java.util.ArrayList?
add(Object x);
remove(Object x);
insert(int i, Object x);
contains(Object x);
set(int i, Object x);
Questions 10-11 refer to
public interface InterfaceA { void methodA(); }
public interface InterfaceB extends InterfaceA { void methodB(); }
public class ClassA implements InterfaceA
{
public void methodA() {}
public void methodB() {}
}
public class ClassB extends ClassA implements InterfaceB
{
public ClassB() {}
… <methods not shown>
}
10.
What is the minimum number of methods that must be defined in classB for it to compile with no errors?
No particular methods are required
methodA
methodB
methodA and methodB
methodA , methodB, and toString
11.
Which of the following statements causes a syntax error?
InterfaceA obj = new ClassA();
InterfaceB obj = new ClassA();
InterfaceA obj = new ClassB();
InterfaceB obj = new ClassB();
ClassA obj = new ClassB();
Questions 12-13 refer to the following method rotate that takes a two-dimensional array a and returns a two-dimensional array b made by rotating a by 90° counterclockwise.
public int[][] rotate(int[][]a)
{
int rows = <expression 1>;
int cols = <expression 2>;
int[][] b = <expression 3>;
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
b[r] = <expression 4>;
return b;
}
For example, if a holds
1 2 3
4 5 6
b = rotate(a) will hold
3 6
2 5
1 4
12. (AB)
Which of the following should replace <expression 1>, <expression 2>, and <expression 3>?
<expression 1> <expression 2> <expression 3>
a.cols a.rows new int(rows, cols)
a.cols a.rows new int[][](rows, cols)
a.cols() a.rows() new int(rows, cols)
a[0].length a.length new int[rows][cols]
a[0].length a.length new int[][](rows, cols)
13. (AB)
Which of the following should replace <statement 4>?
a[r]
a[rows – 1 – r]
a[cols – 1 – c][r]
a[cols – 1 – c][rows – 1 – r]
a[rows – 1 – r][cols – 1 – c]
14.
What is the value of n after the following code is executed?
int n = 2005;
for (int i = 0; i < 50; i++)
n = (n + 3) / 2;
0
1
2
3
65
15.
What is the output of the following code segment?
List cities = new ArrayList();
cities.add(“Atlanta”);
cities.add(“Boston”);
for (int i = 1; i < cities.size(); i++)
cities.add(i, “+”);
System.out.println(cities);
[Atlanta, Boston]
[Atlanta, +, Boston]
[Atlanta, Boston, +]
[Atlanta, +, Boston, +]
No output because the program goes into an infinite loop
16.
Which of the following statements is true?
A static variable cannot be initialized in a constructor
A static variable must be declared final
An instance variable can’t be declared final
A static method can’t access an instance variable
Only a static method can access a static variable
17. (AB)
a and b are arrays of integers and each of them has n elements. a is sorted in ascending order and b is sorted in descending order. What is the big-O, in terms of n, for the number of comparisons in an optimal algorithm that determines whether there exists i, such that a[i] == b[i]?
O(log n)
O( (log n)2 )
O(n)
O(n log n)
O(n2)
18. (AB)
What is the output of the following code?
String key = “”;
Map map = new TreeMap();
for (int k = 0; k < 3; k++)
{
key += k;
String value = “A”;
map.put(key, value);
value += “B”;
map.put9key, value);
}
System.out.println(map.size());
1
2
3
4
6
19. (AB)
Consider the following method:
private TreeNode mysteryProcess(TreeNode root)
{
if (root == null || (root.getLeft() == null && root.getRight() == null))
return null;
else
{
root.setLeft(mysteryProcess(root.getLeft()));
root.setRight(mysteryProcess(root.getRight()));
return root;
}
}
If root refers to the root of the tree
1
/
2 3
/ /
4 5 6
which of the following trees is returned by mysteryProcess(root)?
a. 1 b. 1
3 c. 1
/
2 3 d. 1
/
2 3
/
4 e. 1
3
/
5 6
20. (AB)
What is the output of the following code?
Stack stk = new ArrayStack();
stk.push(“A”);
stk.push(“B”);
stk.push(stk);
while(!stk.isEmpty())
{
Object obj = stk.pop();
if (obj instanceOf Stack)
{
while(!((Stack)obj).isEmpty())
{
System.out.print(((Stack)obj).pop());
}
else
System.out.print(obj);
}
BA
ABBA
BAAB
BABA
ClassCastException
21. (AB)
A priority queue is represented as a minimum heap, stored in an array. When a node is added to the heap, it is first added at the leftmost vacant spot in the current level (or, if the current level is full, at the leftmost spot in the next level), and then the reheap-up procedure is applied. What is the order of the values in the array after “M”, “A”, “N”, “G”, “O”, “E”, “S” are added to the queue?
AEGMNOS
AGEMONS
AEGMNOS
AEGSOMN
AGESNOM
22. (AB)
Suppose an array of n elements is stored in ascending order. Then 5 elements are picked randomly and assigned random values. Which of the following sorting algorithms guarantees to restore the ascending order in than array using no more than O(n) comparisons?
I. Selection Sort II. Insertion Sort III. Mergesort
I only
II only
I and II
II and III
I, II, and III
23.
For any object obj, a call obj.getClass().getName() returns the name of the obj’s class.
Suppose
System.out.println(new A() + “+” + new B());
displays
A+B
Which of the following implementations would produce that result?
I. Class A has a method
public String toString() { return “A”; }
and class B has a method
public String toString() { return “B”; }
II. Both class A and class B extend class X that has a method
public String toString() { return getClass().getname(); }
III. Both class A and class B extend an abstract class X that has methods
public abstract String getName();
public String toString() { return getname(); }
Class A has a method
public String toString() { return “A”; }
and class B has a method
public String toString() { return “B”; }
I only
II only
I and II
II and III
I, II, and III
24. (AB)
Consider the following class:
public class Widget implements Comparable
{
private int nuts, bolts;
public Widget(int nuts, int bolts) { this.nuts = nuts; this.bolts = bolts; }
public int compareTo(Object other) { return nuts – ((Widget)other).nuts; }
public boolean equals(Object other) { return bolts == ((Widget)other).bolts; }
public String toString() { return “” + nuts; }
}
Suppose a non-empty List list holds several Widget objects and the following statements have been executed:
Collections.sort(list);
System.out.println(list);
Set tSet = new TreeSet(list);
Set hSet = new HasSet(list);
Which of the following statements is NOT necessarily true?
tSet.size() <= list.size()
hSet.size() <= list.size()
hSet.size() == tSet.size()
tSet.contains(list.get(list.size() – 1))returns true
The output lists the values of nuts in Widget objects in list in ascending order
25.
A multiple-choice test has 25 questions, each with five answer choices, A – E. On the eve of the test, Casey and other students had learned that the correct answers on the test were not balanced properly: 3 correct answers were C, 7 were D, and 15 were E (A and B were never correct answers). Casey spent the rest of the night devising an optimal strategy for using this information (neglecting to review the test material). In the worst case, how many questions is Casey guaranteed to get right using the optimal strategy?
3
5
7
10
15
2004
26.
twist is defined as follows:
public void twist(String[] w)
{
String temp = w[0].substring(0, 1);
w[0] = w[1].substring(0, 1) + w[0].substring(1);
w[1] = temp + w[1].substring(1);
}
What is the output of the following code segment?
String[] words = {“HOW”, “NEAT”};
twist(words):
System.out.println(words[0] + ” ” + words[1]);
NOW NOW
HOW HOW
NOW HOW
HOW NEAT
NOW HEAT
27.
If Crossword extends Puzzle and implements Solvable, and
Puzzle p = new Puzzle();
Crossword cw = new Crossword(10, 20);
are declared, which of the following statements will cause a syntax error?
p = cw;
cw = new Puzzle();
p = new Crossword(10, 20);
Solvable x = new Crossword(10, 20);
All of the above will compile with no errors.
28.
What is the output of the following code?
List nums = new ArrayList(3);
nums.add(New Integer(1));
nums.add(New Integer(2));
nums.add(0, nums.get(1));
Object x = nums.get(0);
Object y = nums.get(2);
if (x == y)
System.out.println(x + ” is equal to ” + y);
else
System.out.println(x + ” is NOT equal to ” + y);
1 is equal to 2
1 is NOT equal to 2
2 is equal to 2
2 is NOT equal to 2
IndexOutOfBoundsException
29. (AB)
Which of the following best describes the loop invariant in the following code?
double x = 3.0, y = 1.0;
while (x – y > 0.01)
{
x = (x + y) / 2;
y = 3.0 / x;
}
3
x = 3
xy = 3
xy = 3 and x – y > 0.01
x = 1.7321428571428572
30.
What is the output of the following code?
int sum = 0, p = 1;
for (int count = 1; count <= 50; count++)
{
sum += p;
p *= 2;
}
-1
562949953421311 (= 249 – 1)
1125899906842623 (= 250 – 1)
ArithmeticException
IllegalArgumentException
31.
What is the output of the following code?
String barb = “BARBARA”;
scramble(barb);
System.out.println(barb);
The method scramble is defined as follows:
public String scramble(String str)
{
if (str.length() >= 2)
{
int n = str.length() / 2;
str = scramble(str.substring(n)) + str.substring(0, n);
}
return str;
}
BARBARA
ARBABAR
AABAR
ARBABARB
ARABARBARB
32.
What are the values in arr after the following statements are executed?
int[] arr = {1, 1, 0, 0, 0};
for (int i = 2; i < arr.length; i++)
arr[i] = arr[i-1] + arr[i-2];
11011
11210
11222
11235
11248
33.
Given
double x = 5, y = 2;
what is the value of m after the following statement is executed?
int m = (int)(x + y + x / y – x * y – x / (10 * y));
-1
-0.75
-0.5
0
1
34.
What is the value of sum after the following code segment is executed?
int p = 3, q = 1, sum = 0;
while (p <= 10)
{
sum += p % q;
p++;
q++;
}
0
10
12
14
52
35. (AB)
What is the output of the following code segment?
List words = new LinkedList();
int k;
for (k = 1; k <= 9; k++)
words.add(“word”, k);
for (k = 1; k <= words.size(); k++)
if (k % 3 == 0)
words.remove(k);
System.out.println(words);
[word1, word2, word4, word5, word7, word8]
[word2, word3, word5, word6, word7, word8]
[word2, word3, word5, word6, word8, word9]
[word1, word2, word3, word5, word6, word7, word8]
[word1, word2, word3, word5, word6, word8, word9]
36.
A class Particle has a private field double velocity and public methods double getVelocity() and void setVelocity(double v). It also has a method
public void hit(Particle p) { < Missing statements > }
Which of the following could replace < Missing statements > in hit to make it compile with no errors?
I. double v = getVelocity();
setVelocity(p.getVelocity());
p.setVelocity(v);
II. double v = velocity;
velocity = p.getVelocity();
p.setVelocity(v);
III. double v = velocity;
velocity = p.velocity();
p.velocity = v;
I only
II only
I and II
II and III
I, II, and III
37.
Which of the following conditions must always be true after the while loop finishes?
while (hours < hours0 || (hours == hours0 && mins < mins0))
{
mins += 5;
if (mins >= 60)
{
mins -= 60;
hours++;
}
}
hours > hours0 && mins >= mins0
hours >= hours0 && mins >= mins0
hours < hours0 || (hours == hours0 && mins < mins0)
hours >= hours0 && (hours != hours0 && mins >= mins0)
hours >= hours0 && (hours != hours0 || mins >= mins0)
38.
Consider the following class:
public class SaleItem implements Comparable
{
public SaleItem(int p) { prcice = p; }
< Comparison method header > { < Code not shown > }
public String toString() { return String.valueOf(price); }
private int price;
}
Which of the following could replace < Comparison method header > to make this class compile with no errors?
I. public int compare(SatleItem item1, SaleItem item2)
II. public boolean compareTo(SaleItem item1)
III. public int compareTo(Object obj)
I only
II only
III only
I or II
II or III
int money;
public Gambler(int m) { money = m; }
public int currentMoney() { return money; }
public void addMoney(int m) { money += m; }
public void work() { money += 100; }
public void play() { money /= 2; }
public liveAnotherDay() { work(); play(); }
public String toString() { return String.valueOf(money); }
}
public class CompulsiveGambler extends Gambler
{
public CompulsiveGambler(int m)
{
< Missing statements >
}
public void work() { /* do nothing */ }
public void play()
{
while (currentMoney() > 1)
{
super.play();
}
}
}
39.
Given that
System.out.println(new CompulsiveGambler(300));
displays 300, which of the following could replace < Missing statements > in CompulsiveGambler’s constructor?
I. addMoney(m);
II. super(m);
III. super();
addMoney(m);
I only
II only
I or II
II or III
I, II, or III
40.
What is the output of the following code segment?
CompulsiveGambler x = new CompulsiveGambler(300);
x.liveAnotherDay();
System.out.println(x);
200
150
100
1
0
41.
Consider the following method:
public int goFigure(int x)
{
if (x < 100)
x = goFigure(x + 10);
return (x – 1);
}
What does goFigure(60) return?
59
69
95
99
109
42. (AB)
Suppose a List list contains strings “A”, “*”, “B”, “*”, “C” (in this order). What is the output of the following code segment?
ListIterator it = list.listIterator();
while (it.hasNext)
{
if (“*”.equals(it.next()))
it.add(it.next() + “*”);
}
System.out.println(list);
No output: the program goes into an infinite loop
[A, *, **, B, *, **, C]
[A, **, *, B, **, *, C]
[A, *, B, B*, *, C, C*]
[A, *, **, ***, ****, B, *, **, ***, ****, C]
43. (AB)
A linked list pointed to by ListNode head contains Comparable objects. Which sorting algorithm is implemented by the following method sort and its helper method doSomething?
public ListNode sort(ListNode head)
{
if (head != null)
head = doSomething(sort(head.getNext())), head);
return head;
}
private ListNode doSomething(ListNode head, ListNode node)
{
if (head == null || ((Comparable) node.getValue()).CompareTo(head.getValue()) < 0)
{
node.setNext(head);
head = node;
}
else
head.setNext(doSomething(head.getNext(), node));
return head;
}
Selection sort
Insertion sort
Mergesort
Quicksort
Heapsort
44. (AB)
A Map thingsToDo associates a Resort object with a Set of activities available at that resort. The following code segment is intended to remove “Golf” from the activity sets in all resorts:
Iterator iter = thingsToDo.keySet().iterator();
while (inter.hasNext())
< Missing statement >
Which of the following should replace < Missing statement >?
(Set) iter.next().remove(“Golf”);
((Set) iter.next()).remove(“Golf”);
thingsTodo.remove((Set) iter.next(), “Golf”);
thingsTodo.remove((Resort) iter.next(), “Golf”);
((Set) thingsToDo.get(iter.next())).remove(“Golf”);
45. (AB)
What is the output of the following code segment?
TreeNode node6 = new TreeNode(“6”, null, null);
TreeNode node5 = new TreeNode(“5”, null, null);
TreeNode node4 = new TreeNode(“4”, null, null);
TreeNode node3 = new TreeNode(“3”, node5, node6);
TreeNode node2 = new TreeNode(“2”, null, node4);
TreeNode node1 = new TreeNode(“1”, node2, node3);
TreeNode root = node1;
Object[] arr = new Object[8];
toArray(root, 1, arr);
for (int i = 0; i < arr.length; i++)
System.out.println(arr[i] + ” “);
The method toArray is defined as follows:
private void toArray(TreeNode root, itn i, Object[] arr)
{
if (root != null)
{
arr[i] = root.getValue();
toArray(root.getLeft(), 2*i, arr);
toArray(root.getRight(), 2*i + 1, arr);
}
}
null 1 2 null 3 4 5 6
null 1 2 3 null 3 4 5
null 1 2 3 4 null 3 4
null 1 2 3 4 5 null 3
null 1 2 3 4 5 6 null
46. (AB)
Suppose all valid five-digit zip codes are represented as Integer objects and stored in a set containing about 4000 zip codes. Compare two implementations of this set: one is a HashSet with 400 buckets; another is a TreeSet. Assuming that various zip codes are matched against the set with roughly the same frequency, which of the following statements about the average performance of these implementations is true?
HashSet works more than 100 times faster than TreeSet
HashSet works about 20 times faster than TreeSet
HashSet works 2-4 times faster than TreeSet
HashSet works slower than TreeSet
HashSet works roughly as fast as TreeSet, but takes more than twice as much space
47. (AB)
What is the output of the following code segment?
String[] letters = { “A”, “B”, “C” };
Queue qLetters = new ListQueue();
String sLetters = “”;
Stack stk = new ArrayStack();
for (int i = 0; i < letters.length; i++)
{
qLetters.enqueue(letters[i]);
stk.push(qLetters);
sLetters += letters[i];
}
while (!stk.isEmpty())
{
System.out.print(stk.pop() + ” “);
Queue q = (Queue) stk.pop();
System.out.print(“[“);
while (!q.isEmpty())
System.out.print(q.dequeue());
System.out.print(“] “);
}
ABC [ABC] AB [] A []
ABC [] ABC [] ABC []
ABC [ABC] AB [AB] A [A]
A [A] AB [AB] ABC [ABC]
ClassCastException
48. (AB)
An n-by-n two-dimensional array contains Comparable values. The values in each row are increasing. The columns alternate: in the first, third, and other odd columns the values are increasing and in the second, fourth, and other even columns the values are decreasing. What is the average big-O for an optimal algorithm that finds a given value in such an array?
O(log n)
O((log n)2)
O(n)
O(n log n)
O(n2)
49.
Consider the following classes:
public abstract class PointXY
{
private int x, y;
public PointXY(int x, int y) { this.x = x; this.y = y; }
public int getX() { return x; }
public int getY() { return y; }
public String toString() { return “(” + getX + “,” + getY() + “)”; }
public abstract PointXY moveBy(int dx, int dy);
public abstract double distanceFrom(PointXY p);
}
public abstract class CartesianPoint extends PointXY
{
public CartesianPoint(int x, int y) { < Code not shown > }
public double distanceFrom(PointXY p) { < Code not shown > }
}
public class BoardPosition extends CartesianPoint
{
< Code not shown >
}
Which of the following is the minimal set of public constructors and/or methods required in the BoardPosition class, so that the statements
BoardPosition pos = new BoardPosition(0, 0);
System.out.println(pos.moveBy(10, 10).distanceFrom(pos));
compile with no errors?
public PointXY moveBy(int dx, int dy)
public boardPosition(int x, int y) and public PointXY moveBy(int dx, int dy)
public double distanceFrom(PointXY pos)and public PointXY moveBy(int dx, int dy)
public double distanceFrom(BoardPosition pos)and public BoardPosition moveBy(int dx, int dy)
public BoardPosition()and public BoardPosition(int x, int y)and public PointXY moveBy(int dx, int dy)
50.
A multiple-choice question deals with the scores that four students received in a contest. The question offers the following answer choices:
Tim got more points than Jenny.
Tim is the contest winner.
Jenny is in last place.
Tim’s score is above average, and Jenny’s score is below average.
While Nina did better than Phil, the boys’ combined score is higher than the girls’ combined score.
The question assumes that one option is true and all the rest are false. But the question is badly designed, making it possible to guess the correct answer from the given choices without even looking at the question. What is the correct answer?
a
b
c
d
e
2003
51.
fun is defined as follows:
public int fun(int[] v)
{
v[0]–;
return v[0] + 2;
}
What is the value of v[0] after the following code segment is executed?
int [] v = { 3, 4, 5 };
v[0] = fun(v);
1
2
3
4
5
52.
The method xProperty is defined as follows:
public boolean xProperty(int a)
{
return a == 2 * (a / 10 + a % 10);
}
For which of the following values of a does xProperty(a) return true?
2
8
18
28
128
53.
What are the values of m and n after the following code runs?
int m = 20, n = 2, temp;
for (int count = 1; count <= 20; count++)
{
temp = m;
m = n + count;
n = temp – count;
}
m = 230 n = -208
m = 30 n = -8
m = 12 n = -10
m = -12 n = 8
m = -190 n = 212
54.
Consider the method
public int[] copyX(int[] arr)
{
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i++)
{
if (arr[i] <= 0)
break;
if (arr[i] > 10)
break;
result[i] = arr[i];
}
return result;
}
Suppose it is rewritten as follows:
public int[] copyX(int[] arr)
{
int[] result = new int[arr.length];
int i = 0;
while (< condition >)
{
result[i] = arr[i];
i++;
}
return result;
}
Which of the following expressions can replace < condition > so that the second version is equivalent to the first one (i.e., for any int[] parameter arr, it returns the same result as the first version)?
i < arr.length && (arr[i] <= 0 || arr[i] > 10)
(arr[i] <= 0 || arr[i] > 10) || i >= arr.length
(arr[i] <= 0 || arr[i] > 10) && i < arr.length
i < arr.length && !(arr[i] <= 0 || arr[i] > 10)
i < arr.length && arr[i] > 0 && arr[i] <= 10)
55.
Given
double x = < any positive value less than 2003 >;
which of the following code fragments set int y to the smallest integer that is NOT less than three quarters of x?
I. int y = (int)(3 * x / 4);
if (y < 3 * x / 4) y++;
II. int y = 1;
while (y < 3 * x / 4) y++;
III. int y = 2010 – (int)(2010 – x * 3 / 4);
I only
II only
I and II
I and III
I, II, and III
56.
Alicia is five years older than her brother Ben. Three years from now Alicia’s age will be twice Ben’s age. How old are Alicia and Ben now? Ha wrote the following program to solve this puzzle:
public class AliciaAndBen
{
public static void main(String[] args)
{
for (int a = 1; a <= 100; a++)
for (int b = 1; b <= 100; b++)
if (< condition >)
System.out.println(“Alicia is ” + a + ” and Ben is ” + b);
}
}
Which of the following expressions should replace < condition > in Hal’s program so that it displays the correct solution to the puzzle?
(a == b – 5) && (a – 3 == 2 * (b – 3))
a == b + 5 && a + 3 == 2 * b + 6
(a == (b + 5)) && ((a + 3) ++ (2 * b + 3))
a == (b – 5) && (2 * a – 3) == (b – 3)
None of the above works
57. (AB)
Suppose a two-dimensional array of chars m has 4 rows and 5 columns and holds the values represented in the picture below:
x.xxx
xx..x
.x.xx
xx…
What are the values in m after the following code segment is executed?
int r, c;
for (r = 1; r < m.length; r++)
for (c = 1; c < m[0].length – 1; c++)
if (m[r-1][c-1] == ‘x’ && m[r-1] == ‘x’)
m[r] = ‘x’;
a. x.xxx
xx..x
.xxxx
xx… b. xxxxx
xx..x
.xxxx
xx… c. x.xxx
xx.xx
xxxxx
xxx.. d. x.xxx
xx.xx
.xxxx
xxxx. e. x.xxx
xx.xx
.x.xx
xxx..
58.
What is the output of the following code?
String s = “ONION”;
System.out.println(s.substring(1, 5).substring(1, 4).substring(0, 3));
I
IO
ION
ONI
NION
59.
What is the smallest required number of three comparisons in an optimal algorithm (based on comparing values) that puts any THREE distinct values into a list in ascending order? What is the answer for FOUR distinct values?
2 and 3
3 and 4
3 and 5
3 and 6
6 and 12
60.
Given
int counts[] = {7, 2, 9, 0, 1, 5, 5, 3, 9};
What does find3(counts, 9) return? find3 is defined as follows:
public int find3(int a[], int targetsum)
{
int i = 0, sum = 0;
while (i < 3)
{
sum += a[i];
i++;
}
if (sum == targetsum)
return 1;
while (i < a.length)
{
sum += a[i] – a[i-3];
if (sum == targetsum)
return i – 1;
i++;
}
}
-1
1
2
3
8
61. (AB)
Let us call an array “oscillating” if its values alternate going up and down, as follows: a[i-1] < a[i] and a[i] > a[i+1] for any odd i, 0 < i < n-1, where n is the number of elements in a. What is the “big-O” for an optimal algorithm that determines the minimum value for an oscillating array of length n? The median value?
Minimum Median
O(1) O(1)
O(n/2) O(1)
O(n) O(n)
O(n) O(n log n)
O(n) O(n2)
62. (AB)
Suppose an n by n matrix of “black” and “white” pixels (e.g.,1s and 0s) represents a picture of a black blob that fills the southeastern corner of the picture. The blob’s boundary extends in a generally southwest-to-northeast direction. All the pixels below and to the right of any black pixel are black. For example:
0000001
0000001
0000011
0001111
0111111
1111111
1111111
What is the worst case “big-O,” in terms of n, for the total number of integer additions plus pixel comparisons in an optimal algorithm that determines the area of a blob (the number of black pixels in the blob)?
O(log n)
O((log n)2)
O(n)
O(n log n)
O(n2)
Questions 63-67 refer to the following interface and classes, written by Kim, a novice programmer, for modelling a “Caller ID” device:
public interface Call
{
String getSource();
}
public class IncomingCall implements Call
{
private String telephoneNumber;
public IncomingCall() { telephoneNumber = “”; }
public IncomingCall(String tel) { telephoneNumber = tel; }
public void setTelephoneNumber(String tel)
{ telephoneNumber = tel; }
public String getSource() { return telephoneNumber; }
public String toString() { return getSource(); }
}
public class IncomingCallWithName extends IncomingCall
{
private String callerName;
public IncomingCallWithName(String tel, String name)
{
< missing statement >
callerName = name;
}
public String getName() { return callerName; }
public String getSource()
{ return super.getSource() + ” ” + getName(); }
public String toString()
{ return super.getSource() + ” ” + getName(); }
}
63.
Kim’s teacher specified that
System.out.println(new IncomingCallWithName(“800-749-2000”, “Pizza Palace”));
should display
800-749-2000 Pizza Palace
Which of the following statements can replace < missing statement > in the IncomingCallWithName constructor to achieve that?
I. super(tel);
II. setTelephoneNumber(tel);
III. telephoneNumber = tel;
I only
II only
I and II
II and III
I, II, and III
64.
What is the result of the following code segment?
Call[] calls = new Call[3];
calls[0] = new IncomingCall(“888-888-8888”); // Line 1
calls[1] = (IncomingCallWithName) calls[0]; // Line 2
System.out.println(calls[0] + ” ” + calls[1] + ” ” + calls[2]); // Line 3
Syntax error on line 1
Syntax error on line 2
ClassCastException on Line 2
NullPointerException on Line 3
Compiles and runs with no errors; the output is:
888-888-8888 888-888-8888 null
65.
After correctly completing the IncomingCallWithName constructor, as requested in Question 63, Kim wrote the following test code:
IncomingCall call = new IncomingCallWithName(“800-749-2000”, “PizzaPalace”);
System.out.println(call);
The output was
800-749-2000 PizzaPalace
Kim’s teacher suggested that Kim try to compile and run the program again with IncomingCallWithName’s toString method commented out. What would be the result of this experiment?
Syntax error “IncomingCallWithName shoul dbe declared abstract”
Infinite recursion, stack overflow
The program compiles with no errors and displays 800-749-2000
The program compiles with no errors and displays the same output as before, 800-749-2000 PizzaPalace
The program compiles with no errors and displays IncomingCallWithName@47e553
66.
Suppose calls and name are initialized as follows:
Call[] calls = {
new IncomingCallWithName(“800-749-2000”, “Pizza Palace”),
new IncomingCall(“888-237-3757”),
new IncomingCallWithName(“800-555-1234”, “Burger Heaven”)
};
String name = “Pizza Palace”;
The following code segment is intended to count the number of Call objects in the calls array that came from a given source:
String name = IO.readline(); // Read the name of the source
int count = 0;
for (int i = 0; i < calls.length; i++)
if ( < condition > )
count++;
Which of the following replacements for ( < condition > ) will compile with no errors and correctly set count to 1?
calls[i].getSource().indexOf(name) >= 0
calls[i].toString().indexOf(name) >= 0
calls[i].getName().equals(name)
((IncomingCallWithName) calls[i]).getName().equals(name)
None of the above
67. (AB)
Consider the following class:
public class CallerID
{
public List calls;
public CallerID()
{
calls = new LinkedList();
}
// precondition: calls hold IncomingCall objects
// postcondition: all calls that came from target are removed from the calls list
public void removeAll(String target) { < code not shown > }
< other methods not shown >
}
If removeAll works as specified in its pre- and postconditions, which of the following code segments can serve as removeAll’s body?
I. for (int i = 0; i < calls.size(); t++)
{
if (((IncomingCall) calls.get{i}).getSource().equals(target))
calls.remove(i);
}
II. int i = 0;
while (i < calls.size(); t++)
{
if (((IncomingCall) calls.get{i}).getSource().equals(target))
calls.remove(i);
else
i++;
}
III. Iterator iter = calls.iterator();
while (iter.hasNext())
{
if (((IncomingCall) calls.get{i}).getSource().equals(target))
iter.remove(i);
}
I only
II only
I and II
II and III
I, II, and III
68. (AB)
What is the output of the following code segment?
Map m = new TreeMap();
m.put(“La”, “La”);
m.put(“La-La”, “La”);
m.put(“La-La-La”, “Ye-Ye”);
Iterator it = m.keySet().iterator();
while (it.hasNext())
System.out.println(m.get(it.next()) + ” “);
La Ye-Ye
La La Ye-Ye
La La-La-La
La La La-La-La Ye-Ye
La La La-La La La-La-La Ye-Ye
69. (AB)
Suppose ListNode head refers to the first node of a linked list. Consider the following code fragment:
ListNode node, temp;
for (node = head; node != null; node.getNext())
{
while (node.getNext() != null && node.getNext().getValue().equals(node.getValue()))
{
node.setNext((node.getNext().getNext()))l
}
}
If head refers to a linked list with 11 nodes that hold letters
“M”, “I”, “S”, “S”, “I”, “S”, “S”, “I”, “P”, “P”, “I”
(in that order), what letters are stored in the nodes of this list after the above code is executed?
“M”
“M”, “I”, “S”
“M”, “I”, “I”, “I”
“M”, “I”, “S”, “P”
“M”, “I”, “S”, “I”, “S”, “I”, “P”, “I”
70. (AB)
Consider the following method:
public int mysteryCount(TreeNode root)
{
int count = 0;
if (root != null)
{
count = mysteryCount(root.getLeft()) + mysteryCount(root.getRight());
if ((root.getLeft() == null && root.getRight() == null) ||
(root.getLeft() != null && root.getRight() != null && root.getLeft().getValue().equals(root.getRight().getValue())))
count++;
}
}
If root refers to the tree
A
/
/
B C
/ /
D D D D
/ /
E E E E
which value is returned by mysteryCount(root)?
1
3
4
5
10
71. (AB)
Consider the following method that creates a binary tree from a linked list:
public TreeNode listToTree(ListNode head)
{
if (head == null || head.getNext() == null)
return null;
else
return new TreeNode(head.getValue(),
lisToTree(head.getNext()),
listToTree(head.getNext().getNext()));
}
If head refers to a linked list with five nodes—
“A”, “B”, “C”, “D”, “E”
—how many nodes in the tree returned by listToTree(head) hold “E”?
0
3
4
5
8
72. (AB)
Consider the following method that builds a linked list from a binary tree:
public ListNode treeToList(TreeNode root)
{
if (root == null)
return null;
else if (Math.random() < 0.5)
return new ListNode(root.getValue(), treeToList(root.getLeft()));
else
return new ListNode(root.getValue(), treeToList(root.getRight()));
}
If root refers to the tree
A
/
/
B C
/ /
D E F
which of the following lists could possibly result from treeToList(root)?
I. A, B, D
II. A, B, C, D
III. A, C, F
I only
II only
I and II
I and III
I, II, and III
73. (AB)
Consider the following method that builds a linked list from a queue:
// precondition: q holds Comparable objects
public TreeNode queueToTree(ListQueue q)
{
if (q.isEmpty())
return null;
ListQueue q1 = new ListQueue();
ListQueue q2 = new ListQueue();
Comparable x, y;
x = (Comparable) q.dequeue();
while (!q.isEmpty())
{
y = (Comparable) q.dequeue();
if (y.compareTo(x) < 0)
q1.enqueue(y);
else
q2.enqueue(y);
}
return new TreeNode(x, queueToTree(q1), queueToTree(q2));
}
If q contains letters A, P, R, I, C, O, T (represented by Character or String objects, in this order, from front to rear), what is the result of inorder transversal (left-to-right) of the tree returned by queueToTree(q)?
A, C, I, O, P, R, T
A, P, R, T, I, C, O
A, P, R, C, I, O, T
A, C, O, I, T, R, P
A, P, I, C, O, R, T
74. (AB)
Consider the following method eval:
String eval(Queue q)
{
Stack stk = new ArrayStack();
String s = “”;
while (!q.isEmpty())
{
s = (String) q.dequeue();
if (!s.equals(“+”))
stk.push(s);
else
{
String s1 = “”, s2 = “”;
if (!stk.isEmpty())
s2 = (String) stk.pop();
if (!stk.isEmpty())
s1 = (String) stk.pop();
stk.push(s1 + s2);
}
}
if (!stk.isEmpty())
s = (String) stk.pop();
return s;
}
The program reads strings (which may hold single characters), separated by spaces, one by one from the input line and puts them into a queue q. Then it displays the string returned by eval(q). For which of the following input lines is the output HELLO?
front
?
H + E + L + L + O
H E L + + L O + +
H E + + L L + O
+ + + + O L L E H
None of the above
75.
A multiple-choice test contains 25 questions. The correct answers include five A’s, five B’s, five C’s, five D’s, and five E’s. Both Constance and Randy solve the first 15 questions correctly but then run out of time. Constance picks the letter (or one of the letters) that is least frequent among the first 15 answers and fills the remaining 10 answers with this letter. Randy picks random answers for the remaining 10 questions, but he makes sure that at the end each letter A-E appears exactly five times among all 25 answers. Which of the following statements is FALSE?
Randy and Constance can get the same score
Randy’s score can be any number from 15 to 25
Constance scores not more than 17
Constance scores not more than 20
Neither Randy nor Constance can score exactly 24
2002
76.
If a is and int array of length 2 and a[0] and a[1] holds values 7 and 13 respectively, what are their values after fun(a) is called? The method fun is defined as follows:
public void fun(int[] x)
{
x[0] = (int)(100.0 * x[0] / (x[0] + x[1]));
x[1] = (int)(100.0 * x[1] / (x[0] + x[1]));
}
7 and 13
35 and 27
34 and 64
35 and 65
34 and 66
77.
Consider a method
public boolean isProcessedX(int n, int[] v)
{
if (n >= 2 && isProcessedX(n-1, v))
{
v[n-1] = v[n-2];
return true;
}
else
return false;
}
What happens if an int array s holds values 1, 2, 3, 4, 5 and isProcessedX(5, s) is called?
s holds 1, 2, 3, 4, 5 and isProcessedX returns false
s holds 1, 2, 3, 4, 4 and isProcessedX returns true
s holds 1, 1, 1, 1, 1 and isProcessedX returns true
indexOutOfBoundsException
Stack overflow error
78.
An array mix holds seven elements. For which seven values in mix will the value of the variable property be true after the following code segments is executed?
int i;
boolean property = true;
for (i = 1; i < 6; i++)
{
if (mix[i] >= mix[i-1] || mix[i] >= mix[i+1])
property = false;
}
1, 2, 3, 4, 5, 6, 7
7, 6, 5, 4, 3, 2, 1
7, 1, 6, 2, 5, 3, 4
1, 2, 3, 4, 3, 2, 1
1, 5, 2, 6, 3, 7, 4
79. (AB)
The class Game has a data member char[][] board and a constructor defined as follows:
public Game()
{
board = new char[4][4];
int r, c;
for (r = 0; r < 4; r++)
for (c = 0; c < 4; c++)
board[r] = ‘.’;
for (r = 0; r < 4; r++)
board[r][(r + 1) % 4] = ‘x’;
}
What values are stored in board when a Game object is constructed with the above constructor?
a. …x
..x.
.x..
x… b. ..x.
.x..
x…
…x c. …x
x…
.x..
..x. d. .x..
..x.
…x
x… e. .x..
x…
…x
..x.
80.
Consider the following method prepare:
public String prepare(String s)
{
int k = s.length() / 2;
if (k <= 1)
return s;
return s.charAt(k – 1) + prepare(s.substring(0, k – 1) + s.substring(k + 1, 2*k)) + s.charAt(k);
}
what does prepare(“LEMONADE”) return?
ONMAEDLE
OLEMADEN
OMELEDAN
OOOONNNN
LEMONADE
81.
What are the values of a and b after the following code fragment is executed?
int a = 3, b = 5, s;
for (int i = 0; i < 10; i++)
{
s = a + b;
b = a – b;
a = s;
}
0 and 96
96 and 0
96 and 96
96 and 160
160 and 96
82.
If int weekDay contains the code for the day of the week on November 1 (0 for Sunday, 1 for Monday, …, 6 for Saturday), which of the following expressions gives the date for Thanksgiving (the fourth Thursday in November)?
weekDay + 26
26 – weekDay
(4 – weekDay) % 7 + 22
(11 – weekDay) % 7 + 22
(weekDay + 3) % 7 + 22
83.
The method average3 below “simultaneously” replaces all elements in an array. Each element is replaced with the average of that element’s current value and its left and right neighbors. If a “neighbor” is outside the array, its value is assumed to be 0:
public void average3 (double a[])
{
int i, len = a.length;
double tempSaved[] = new double[len];
for (i = 0; i < len; i++)
tempSaved[i] = a[i];
double leftNeighbor, rightNeighbor;
for (i = 0; i < len; i++)
{
if (i > 0)
leftNeighbor = tempSaved[i-1];
else
leftNeighbor = 0;
if (i < len – 1)
rightNeighbor = tempSaved[i+1];
else
rightNeighbor = 0;
a[i] = (leftNeighbor = tempSaved[i] = rightNeighbor) / 3;
}
}
Suppose the first and lest elements in v are zeroes. Which of the following statements is FALSE after average3(v) is called? (Disregard all inaccuracies that may be introduced due to floating-point arithmetic.)
If v holds the values 0, 3, 6, 9, 12, 9, 6, 3, 0, the resulting array will hold 1, 3, 6, 9, 10, 9, 6, 3, 1.
The sum of all the elements in v remain the same.
If in the original array the sum of all the values in even positions, v[0] + v[2] + …, is the same as the sum of all the values in the odd positions, v[1] + v[3] + …, then the same will remain true for the resulting array.
The maximum value in the resulting array does not exceed the maximum value in the original array.
The position of the maximum element in the resulting array remains the same as in the original array or shifts to one of the two neighboring positions.
84. (AB)
An array arr contains n integer elements whose values form an arithmetic sequence (i.e., arr[i+1] – arr[i] == arr[i] – arr[i-1] for any 0 < i < n-1). Whatr is the “big-O” for an optimal algorithm that determines whether such an array contains two given values?
O(1)
O(log n)
O(2 log n)
O(n)
O(n2)
85.
Given
Random generator = new Random();
int bigNum = 10000;
int r = generator.nextInt(bignum);
which of the following expressions is the best way to initialize x to the value of a randomly chosen element from an array arr of 3 values? (The odds for choosing any element must be the same or almost the same.)
x = arr[r / bignum * 3];
x = arr[(int)(3.0 * r / bignum)];
x = arr[(int)(2.9 * r / bignum)];
x = arr[(int)(3.0 * (r – 1) / (bignum -1)];
x = arr[3 * (int)((double) r / bigNum)];
86.
Given three integer variables, a, b, and c, with small non-negative values, which of the following code fragments tests the condition that any two of the values are zeroes while the third one is positive? The variable ok should be set to true if and only if the above condition is true.
I. boolean ok =
a == 0 && b == 0 && c > 0 ||
b == 0 && c == 0 && a > 0 ||
c == 0 && a == 0 && b > 0;
II. boolean ok = a + b + c > 0 && a*b + b*c + c*a == 0;
III. boolean ok = a > 0 || b > 0 || c > 0;
if (ok) ok = a + b == 0 || b + c == 0 || c + a == 0;
I only
II only
I and II
I and III
I, II, and III
Questions 87-91 are based on the following classes:
public class Person implements Comparable
{
private String name;
public Person(String name) { this.name = name; }
public String getName() { return name; }
public boolean equals(Object other)
{
return other != null && name.equals(((Person) other).name);
}
public int compareTo(Object other)
{
return name.compareTo((Person other).name);
}
public int hashCode() { return name.hashCode(); }
}
public class SoccerPlayer extends person
{
private int numGoals;
public SoccerPlayer(String name, int n)
{
super(name);
numGoals = n;
}
public int getNumGoals() { return numGoals; }
public void score() [ numGoals++; }
public int compareTo(SoccerPlayer other)
{
return getNumGoals() – other.getNumGoals();
}
public String toString()
{
return gatName() + “/” + getNumGoals();
}
}
87.
Which of the following declarations is invalid?
Person p = new Person(“Mia Hamm”);
SoccerPlayer p = new Person(“Mia Hamm”);
Comparable p = new Person(“Mia Hamm”);
Person p = new SoccerPlayer(“Kristine Lilly”, 0);
Comparable p = new SoccerPlayer(“Kristine Lilly”, 0);
88.
What is the result of the following code?
Person players[] = { new SoccerPlayer(“Mia Hamm”, 7), new SoccerPlayer(“Kristine Lilly”, 6) };
System.out.println(players[0].compareTo((SoccerPlayer) players[1])); // Line ***
Syntax error in the class Person: other.name is not accessible
Syntax error in the class SoccerPlayer: compareTo is redefined
ClassCaseException on Line ***
Compiles with no errors, displays 1
Compiles with no errors, displays 2
89. (AB)
Suppose the Person and SoccerPlayer classes are changed as follows:
other.name is replaced with other.getame() and compareTo in SoccerPlayer is renamed into compareGoals. What will be the result of running the following code segment?
SoccerPlayer mia = new SoccerPlayer(“Mia Hamm”, 6);
SoccerPlayer kristine = new SoccerPlayer(“Kristine Lilly”, 5);
Set team = new HashSet();
team.add(mia);
team.add(kristine);
kristine.score();
team.add(kristine);
Iterator iter = team.Iterator(); // Line ***
while(iter.hasNext())
System.out.print(iter.next() + ” “);
Kristine Lilly/5 Mia Hamm/6
Kristine Lilly/6 Mia Hamm/6
Mia Hamm/6 Kristine Lilly/5 Kristine Lilly/6
Kristine Lilly/5 Kristine Lilly/6 Mia Hamm/6
Syntax error on Line ***
Questions 90-91 are concerned with a class SoccerTeam that represents a team of soccer players:
public class SoccerTeam
{
private SoccerPlayer[] players;
private ArrayList mvps; //holds all the players who scored the same highest number of goals
public void score(int k)
{
players[k].score(); // Line *1*
int goals = players[k].getNumGoals();
int maxGoals = ((SoccerPlayer) mvps.get(0)).getNumGoals(); // Line *2*
if (goals >= maxGoals)
{
if (goals == maxGoals) // Line *3*
mvps.add(players[k]);
else
{
// mvps is left with only one player in it, players[k]:
< missing statements >
}
}
}
< constructors and other methods not shown >
}
90.
SoccerTeam’s score method is intended to update the number of scored goals for a given player on the team and update the list of “most valuable players” (all of whom have the same score, the highest on the team). If the player’s new score is higher than the old best, the mvps list is updated to contain only that one player. However, the score method has an error. Which of the following actions would correct that error?
I. Move Line *2* before Line *1*
II. Replace Line *3* with
if (goals == maxGoals && players[k] != mvps.get(0))
III. Replace Line *3* with
if (goals == maxGoals && != mvps.contains(players[k]))
I only
II only
I and II
II and III
I, II, and III
91.
Which of the following would be an appropriate replacement for < missing statements > in SoccerTeam’s score method?
mvps.set(0, players[k]);
mvps.reize(0);
mvps.add(players[k]);
mvps = new ArrayList();
mvps.add(players[k]);
mvps = new ArrayList(1);
mvps.set(0, players[k]);
delete mvps;
mvps = new ArrayList():
mvps.add(players[k]);
92. (AB)
The elements in an array of size n are first increasing (a[i] < a[i+1]), until they reach a maximum value, then decreasing (a[i] > a[i+1]). What are the respective “big-O” estimates for the number of comparisons in two optimal algorithms, one that finds a maximum value in such an array and the other that sorts the array in ascending order?
O(log 2) and O(n)
O(log n) and O(n log n)
O(n) and O(n)
O(n) and O(n log n)
O(n) and O(n2)
93. (AB)
What is the output from the following code segment?
Set set = new TreeSet();
String str = “A”;
set.add(str);
str += “B”;
set.add(str);
str += “C”;
set.add(str);
Iterator iter = set.Iterator();
while (iter.hasNext())
System.out.print(iter.next() + “-“);
A-
ABC-
A-B-C-
A-AB-ABC-
None of the above
94. (AB)
Suppse ListNode p1, p2 initially refer to two nodes in the same circular linked list. Under what conditions does the following loop terminate?
do
{
p1 = p1.getNext();
p2 = ps.getNext().getNext();
} while (p1 != p2);
Always
If and only if p1 == p2.getNext()
If and only if the total number of nodes in the list is even
If and only if the number of nodes from p2 to p1 (excluding both ends of this segment of the list) is even
If and only if the list contains two nodes with the same info
95. (AB)
What does the following code display?
String expr = “(a + b) / (2 * (a – b)”;
Stack stk = new ArrayStack();
int i, k;
for (k = 0; k < expr.length(); k++)
{
if (expr.charAt(k) == ‘(‘)
{
stk.push(new Integer(k + 1));
}
else
{
i = ((Integer) stk.pop()).intValue();
System.out.println(expr.substring(i, k));
}
}
(2 * (a – b))
(a – b)
(a + b)
(a – b)
(2 * (a – b))
(a + b)
a – b
a + b
(2 * (a – b))
a + b
a – b
2 * a – b
a + b)
a – b)
2 * (a – b))
96.
The following method packed analyzes a string passed to it and returns a new string:
String packed(String msg)
{
String packedMsg = “”;
for (int i = 0; i < msg.length(); i+)
{
if (msg.charAt(i) !- ‘.’)
{
int len = packedMsg.length();
if (len == 0 || msg.charAt(i) != packedMsg.charAt(len-1))
packedMsg += msg.substring(i, i+1);
}
}
return packedMsg;
}
For which of the following values of msg, is packed(msg) NOT equal to packed(“xxo.ooo.xx.x”)?
xxo..ooo..xx..x
..xxooooooxxxx..
xxoooxxx
xxooooooxxox
xox
97. (AB)
What is the value of sum after the following code is executed?
int sum = 0;
int r = 0, c = 0;
int temp, d1 = 1; d2 = 2;
int table[][] = new int[8][8];
for (int k = 0; k < 64; k++)
{
table [r] = 1;
r = (r + d1) % 8;
c = (c + d2) % 8;
temp = d1; d1 = d2; d2 = temp;
}
for (r = 0; r < 8; r++)
for (c = 0; c < 8; c++)
sum += table[r];
8
15
16
22
64
Questions 98-99 assume that TreeNode root points to the following binary tree:
A
/
B C
/ /
D E F
G
98. (AB)
Consider the following method traverse:
void traverse(TreeNode root)
{
if (root != null)
{
traverse(root.getLeft());
traverse(root.getRight());
System.out.print(root.getValue());
traverse(root(getRight());
traverse(root.getLeft());
}
}
How many letters will be displayed when traverse(root) is called?
1
7
13
14
25
99. (AB)
Consider the following method:
public void grow(TreeNode root)
{
if (root !- null)
{
if (root.getLeft() != null && root.getRight != null)
root.setRight(new TreeNode(“X”, null, null));
else if (root.getLeft() == null && root.getRight != null)
root.setLeft(“X”, null, null));
grow(root.getLeft());
grow(root.getRight());
}
}
Which of the following represents the resulting tree after grow(root) is called?
a. A
/
B C
/ /
D E F
G
X b. A
/
/
B C
/ /
D X E F
/
X G c. A
/
/
B C
/ /
D X E F
/ / / /
X X X X X X X X d. A
/
/
B C
/ /
D X E F
/ / /
X X X X X G
/
X X e. None of the above
100.
An exam contains 24 questions for 40 minutes. Some questions are easy, while other questions are really hard. Constance and Skip always solve any easy question in 20 seconds, but a hard question always takes each of them 3 minutes. Constance’s strategy is to take each question in turn and take whatever time it takes to solve it. Skip tries a question for 20 seconds and if he can’t solve it, he moves on to the next one. If he has looked at all the questions, Skip returns to the unsolved hard questions, but he has to start solving them from scratch because by then he has forgotten what they were about. If the first half of the test contains at least 8 easy questions and the second half contains at least 8 hard questions, which of the following statements is FALSE?
Skip will solve at least 18 questions
Constance will solve at least 20 questions
If at most 10 of the questions are hard, both Skip and Constance will solve all 24 questions
Skip will solve at most 10 hard questions
Constance will always solve at least as many questions as Skip
2001
101.
What is the output of the following code?
int a = 1, b = 2, c = 3;
a += b + c;
b += a + c;
c += a + b;
System.out.println(a + ” ” + b + ” ” + c);
3 3 4
3 5 6
5 4 3
5 8 13
6 11 20
102.
Consider two methods:
public int f(int x)
{
return x + 2;
}
and
public int g(int x)
{
return x * 2;
}
What is the value of x after the following code executes?
int x = 1;
x += f(g(x)) – g(f(x));
-9
-2
-1
3
7
103.
What is the value of y after the following code is executed?
int x = 123;
while (x > 0)
{
y *= 10;
y += x % 10;
x /= 10;
}
1
3
6
12
321
104. (AB)
The method xWon below is supposed to return true is a tic-tac-toe board (represented by a 3-by-3 array of characters) has three x’s in any line, false otherwise:
public boolean xWon (char[][] b)
{
if (b[1][1] == ‘x’)
{
if (b[0][0] == ‘x’ && b[2][2] == ‘x’) return true;
if (b[0][1] == ‘x’ && b[2][1] == ‘x’) return true;
if (b[1][0] == ‘x’ && b[1][2] == ‘x’) return true;
if (b[0][2] == ‘x’ && b[2][0] == ‘x’) return true;
}
else if (b[0][0] == ‘x’)
{
if (b[0][1] == ‘x’ && b[0][2] == ‘x’) return true;
if (b[1][0] == ‘x’ && b[2][0] == ‘x’) return true;
}
else if (b[2][2] == ‘x’)
{
if (b[2][0] == ‘x’ && b[2][1] == ‘x’) return true;
if (b[0][2] == ‘x’ && b[1][2] == ‘x’) return true;
}
return false;
}
a. x..
xxo
xoo b. o.x
ox.
xox c. xxo
o.o
oxx d. x.o
oxo
x.x e. oox
o..
xxx
105.
Consider the following method:
public void divide5 (int[] a, int[] q, int[] r)
{
q[0] = a[0] / 5;
r[0] = a[0] % 5;
}
What is the value of y[0] after the following statements are executed?
int[] x = {21, 22, 23], y = new int[3];
divide5(x, y, z);
0
1
2
4
21
106. (AB)
Suppose the method fun is defined as follows:
public void fun (int m[][], String s)
{
for (int i = 1; i < s.length(); i++)
{
int r = Character.digit(s.charAt(i), 10);
int c = Character.digit(s.charAt(i – 1), 10);
m[r]++;
}
}
What is the output when the following code fragment is executed?
int m[][] = new int[10][10];
String s = “20012002”;
fun(m, s);
int sum = 0;
for (int k = 0; k < 10; k++)
sum += m[k][k];
System.out.println(sum);
1
2
4
7
8
107.
Which of the following conditions is always true after the while loop in the following code fragment has finished (assuming it executes without errors)?
int k = 0; n = 10;
while (k < n && a[k] >= 0)
k++;
k >= n && a[k] < 0
k < n && a[k] < 0
k < n || a[k] < 0
k >= n || a[k] < 0
None of the above
108.
The method
public boolean xyz (String s)
{
return s.length() >= 3 &&
((s.charAt(0) == s.charAt(1) &&
s.charAt(1) == s.charAt(2)) || xyz(s.substring(1)));
}
returns true if and only if
s contains three or more of the same characters in a row
s starts with three or more of the same characters
s ends with three or more of the same characters
s contains three or more of the same characters
s[0] is the same as two other characters in s
109.
The following version of Selection Sort is supposed to sort an array in ascending order. For better performance it tries to tackle the array from both ends simultaneously:
public void sort (int a[])
{
int left = 0, right = a.length() – 1;
int k;
while (left < right)
{
for (k = left + 1; k < right; k+)
{
if (a[k] < a[left])
swap(a, k, left);
else if (a[k] > a[right])
swap(a, k, right);
}
left++;
right–;
}
}
swap(a, i, j) correctly swaps a[i] and a[j]. This code has a bug, though. Which one of the following changes would assure that the method sorts the array correctly?
I. Remove else in
else if (a[k] > a[right]) …
II. Replace
for (k = left + 1; k < right; k+)
with
for (k = left; k <= right; k+)
III. Add
if (a[left] > a[right])
swap(a, left, right);
at the beginning of the while loop (before the for loop).
I only
II only
III only
I or II
II or III
110. (AB)
Insertion Sort is a sorting algorithm that works as follows: keep the first k elements of the array sorted; find the right place and insert the next element among the first k. These steps are repeated for k – 1, …, n. Sequential Search is usually used to find the right spot in which to insert the next element. Suppose we use Binary Search instead of Sequential Search in this algorithm. How would Big-O for the number of comparisons among the elements (not counting the number of moves or swaps) change?
No change
From O(n) to O(log n)
From O(n2) to O(n2/2)
From O(n2) to O(n log n)
From O(n2) to O(n)
Questions 111-112 are based on the following class that represents a moving ball on a rectangular pool table:
public class MovingBall
{
private int mLength, mWidth;
private int mPosX, mPosY;
private int mDirX, mDirY;
public MovingBall(int length, int width, int dx, int dy)
{
mLength = length;
mWidth = width;
mPosX = length / 2;
mPosY = width / 2;
mDirX = dx;
mDirY = dy;
}
public void move()
{
mPosX += mDirX;
mPosY += mDirY;
if (mPosX == 0 || mPosX == mLength) mDirX = -mDirX;
id (mPosY == 0 || mPosY == mWidth) mDirY = -mDirY;
}
}
111.
Giiven
MovingBall b = new MovingBall(8, 4, 1, -1);
what are the values of mPosX and mPosY after 70 moves (i.e., 70 calls to b.move())?
74 and -68
6 and 4
4 and 2
3 and 1
1 and -1
112.
If
MovingBall b = new MovingBall(9, 4, 1, 1);
is defined, how many moves (i.e., calls to b.move()) will ball b hot position mPosX = 6, mPosY = 1?
Never
2
3
7
30
113.
Suppose all the elements in an array have different values. Let us say the array is “nearly sorted” (in ascending order) if each element’s position differs from its appropriate position in the sorted arrangement of the same array by at most 2 (in either direction). The following method takes an array where the first n elements are “nearly sorted” and properly sorts the array.
public void sortNearlySorted(int[] arr, int n)
{
int i = 0;
while (i < n = 1)
{
if (arr[i+1] < arr[i])
swap(arr, i, i + 1);
if (i+2 < n && arr[i+2] < arr[i])
swap(arr, i, i+2);
i++;
}
}
Which of the following is a loop invariant for the while loop in the above method?
arr[0] … arr[n-1] are sorted and 0 <= i < n
arr[0] … arr[n-1] are nearly sorted and 0< n-1
arr[0] … arr[i-1] are placed where they belong in the sorted array and arr[i] … arr[n-1] are “nearly sorted”
arr[i] < arr[i+1] and arr[i] < arr[i+2]
arr[0] … arr[n-3] are sorted
114.
In the ABBAB language the alphabet has only two letters. A string of letters (including and one-letter strings) is a valid word, if and only if the isValid method returns true for that string. isValid is defined as follows:
public boolean isValid(String word)
{
int n = word.length();
return n < 1 ||
(isValid(word.substring(0, n-1) &&
word.charAt(n-1) == ‘B’) ||
(isValid(word.substring(0, n-2) &&
“BA”.equals(word.substring(n-2)));
}
How many valid words of length 7 are there in the ABBABA language?
2
3
15
23
34
115. (AB)
The method below takes a linked list pointed to by head, removes the first node, appends it at the end of the list, and returns a reference to the head of the new list.
public ListNode firstToLast (ListNode head)
{
if (head == null) || head.getNext() == null)
return head;
ListNode p = head;
while (p.getNext() != null)
p = p.getNext();
< missing statements >
return head;
}
Which of the following code fragments correctly completes this method?
I. ListNode temp = head;
head = head.getNext();
p.setNext(temp);
temp.setNext(null);
II. ListNode temp = head.getNext();
head.setNext(null);
p.setNext(head);
head = temp;
III. p.setNext(head);
head = head.getNext();
p.getNext().setNext(null);
I only
II only
I and II
II and III
I, II, and III
116. (AB)
The following method goodHand checks whether s stack of Integers (that represent ranks of playing cards in a small deck) has a certain property:
public boolean goodHand (Stack hand)
{
int[] count = new int[2];
Object x, y;
for (int k = 0; k <= 1; k++)
{
if (hand.isEmpty())
return false;
x = hand.pop();
Stack stk = new ArrayStack();
while (!hand.isEmpty())
{
y = hand.pop();
if (x.equals(y))
count[k]++;
else
stk.push(y);
}
hand = stk;
}
return Math.abs(count[0] – count[1]) <= 1 && hand.isEmpty();
}
For which of the following stacks does goodHand return true?
top ==>
a. 2
3
4
5
6 b. 2
2
3
3
4 c. 2
3
2
2
3 d. 3
3
3
3
2 e. 2
2
2
2
2
117. (AB)
An n by n square image contains black and white pixels. The first several columns contain one or more black pixels at the top with only white pixels below; the remaining columns are all white. For example:
xxxx..
xxxx..
x.xX..
x.x…
..x…
……
A program is allowed to examine individual pixels in the image; its task is to find the position of the lowest black pixel in the rightmost column that has at least one black pixel (the uppercase pixel in the above example). What is the worst case big-O for the number of examined pixels in the best possible algorithm.
O(log n)
O((log n)2)
O(n)
O(n log n)
O(n2)
Questions 118-122 use the following classes:
public class Point
{
private int x;
private int y;
public Point(int x, int y) { this.x = x; this.y = y; }
public int getX() { return x; }
public int getY() { return y; }
public boolean equals(Point other)
{
return getX() == other.getX() && getY() == other.getY();
}
public int hashCode()
{
return (new Integer(getX() + getY())).getHashCode();
}
public void setX(int x) { this.x = x; }
public void setY(int Y) { this.y = y; }
public String toString()
{
return “(” + getX() + “, ” + getY() + “)”;
}
}
public class MovingPoint extends Point
{
private Point myPoint;
public MovingPoint(Point p)
{
< missing statements >
myPoint = p;
}
public int getX() { return myPoint.getX(); }
public int getY() { return myPoint.getY(); }
public void move(int x, int y)
{
myPoint(setX(x));
myPoint(setY(y));
}
public String toString()
{
return myPoint.toString();
}
}
118.
Which of the following can replace < missing statements > in MovingPoint’s constructor?
super();
super(0, 0);
setX(0); setY(0);
super(); setX(p.getX()); seyY(p.getY());
// set myPoint to p:
119.
Which line in the following code segment causes a syntax error?
Point p1 = new Point(100, 100); // Line 1
MovingPoint p2 = new MovingPoint(p1); // Line 2
Point p3 = new MovingPoint(p2); // Line 3
MovingPoint p4 = new MovingPoint(p2); // Line 4
No syntax errors on these lines
Line 1
Line 2
Line 3
Line 4
120.
What is the output of the following code?
Point p = new Point(0, 0);
MovingPoint mp = new MovingPoint(p);
mp.move(1, 1);
System.out.println(p + ” ” + p.equals(mp));
NullPointerException
ClassCastException
(0, 0) true
(0, 0) false
(1, 1) true
121. (AB)
Consider the following two code segments:
Set points = new HashSet();
MovingPoint p;
p = new MovingPoint(new Point(0, 0));
points.add(p);
p = new MovingPoint(new Point(0, 2));
points.add(p);
p = new MovingPoint(new Point(2, 2));
points.add(p);
p = new MovingPoint(new Point(2, 0));
points.add(p);
p = new MovingPoint(new Point(1, 1));
points.add(p);
System.out.println(points.size());
Set points = new HashSet();
MovingPoint p;
p = new MovingPoint(new Point(0, 0));
points.add(p);
p.move(0, 2);
points.add(p);
p.move(2, 2);
points.add(p);
p.move(2, 0);
points.add(p);
p.move(1, 1);
points.add(p);
System.out.println(points.size());
What are their respective outputs?
3 and 1
3 and 3
5 and 1
5 and 3
5 and 5
122. (AB)
What is the output of the following code segment?
Point p = new Point(0, 0);
MovingPoint p1 = new MovingPoint(p);
movingPoint p2 = new MovingPoint(p);
Queue q = new ListQueue();
p1.move(1, 0);
q.enqueue(p1);
p2.move(0, 1);
q.enqueue(p2);
System.out.println(q.dequeue() + ” ” + q.dequeue());
(0, 0) (0, 0)
(1, 0) (1, 0)
(0, 1) (0, 1)
(1, 0) (0, 1)
(0, 1) (1, 0)
123. (AB)
Consider the following method:
public int magic (TreeNode root)
{
if (root != null)
{
if (root.getLeft() == null && root.getRight() == null)
return 0;
if (magic(root.getLeft()) + magic(root.getRight()) == 0)
{
TreeNode temp = root.getLeft();
root.setLeft(root.getRight());
root.setRight(temp);
}
}
return -1;
}
What does this method do to a tree referred to by root?
Nothing, leaves the tree unchanged
Swaps the left and right branches of the tree at the root
Replaces the tree with its mirror image
Swaps any two leaves that have the same parent
Swaps the leftmost and rightmost leaves
124. (AB)
Suppose traversePreOrder and traversePostOrder are defined as follows:
public void traversePreOrder(TreeNode root, Stack s)
{
if (root != null)
{
s.push()(root.getValue());
traversePreOrder(root.getLeft(), s);
traversePreOrder(root.getRight(), s);
}
}
public void traversePostOrder(TreeNode root, Stack s)
{
if (root != null)
{
traversePostOrder(root.getLeft(), s);
traversePostOrder(root.getRight(), s);
root.setValue(s.pop());
}
}
If root initially refers to
A
/
/
B C
/ /
D E F G
what is the resulting tree after the following statements are executed?
Stack s = new ArrayStack ();
traversePreOrder(root, s);
traversePostOrder(root, s);
a. A
/
/
B C
/ /
D E F G b. A
/
/
C B
/ /
G F E D c. G
/
/
D F
/ /
A B E C
d. A
/
/
C B
/ /
F G D E e. G
/
/
F D
/ /
E C B A
125.
A multiple-choice question offers three options, I, II, and III, and asks which ones fit into a given situation. The offered answers are a) I only; b) II only; c) III only; d) I and II; and e) II and III. Assuming that it takes the same amount of time to examine any one of the three options, that the odds that any option fits are 50-50, and that s student always gets all answers right and doesn’t waste time considering unnecessary options, which option should she consider first?
Doesn’t matter
Either I or II
Either I or III
Definitely I
Definitely II
2000
126.
Which of the following statements does NOT display 2/3?
System.out.println(“2/3”);
System.out.println(“2” + “/” + “3”);
System.out.println(2/3);
System.out.println(2 + “/” + 3);
System.out.println((int)2 + “/” + (int)3);
127.
If array arr has five elements with values 0 1 2 3 4, what are the values in arr after the following code is executed?
for (int k = 0; k < 5; k++)
arr[k] = arr[arr[k]];
0 1 2 3 4
1 2 3 4 0
1 2 2 2 2
0 0 0 0 0
1 2 3 4 4
128.
If c and d are boolean variables, which of the answer choices is NOT equivalent to the following expression?
(c && d) != (c || d)
(c && !d) || (!c && d)
(c || d) && (!c && !d)
(c || d) && (!c || !d)
(c || d) && !(c && d)
c != d
129.
The value of (1 + (1/n))n for large enough n (e.g., n >= 50) approximates the base of the natural logarithm e = 2.71828… A student decided to test this property and wrote the following method:
public double approxE()
{
double e = 1.0 + 1.0 / 64;
for (int count = 1; count <= 6; count++)
e *= e;
return e;
}
What value is returned by approxE()?
No value is returned: the method throws an ArithmeticException
1.0
2.6973449525651
1.642359568597906
7.275669793128421
130.
What is the output from the following code?
int[] counts = new int[3];
int i, j;
for (int i = 0; i < 100; i++)
for (j = 0; j < 10; j++)
counts[j % 3]++;
System.out.println((counts[1] + counts[2]) / counts[0]);
1
1.5
2
2.5
3
131.
Suppose an array A has n elements. Let’s call it periodic with a period of p if 0 < p < n and A[i] == A[i+p] for all 0 <= i < n-p and p is the smallest such number. What is the period of array v after the following code is executed?
int v[] = new int[100];
v[0] = 0; v[1] = 1;
for (int i = 2; i < 100; i++)
v[i] = v[i-1] – v[i-2];
2
3
4
6
No period
132.
What is the output from the following code?
StringBuffer s = new StringBuffer(“WYOMING”);
int k, i, n = s.length();
char temp;
for (k = 0; k < 3; k++)
{
temp = s.charAt(n-1);
for (i = k+1; i < n; i++)
s.setCharAt(i, s.charAt(i-1));
s.setCharAt(k, temp);
}
System.out.println(s);
YOMINGW
MINGWYO
GWWWWWW
MINGOYW
GNIMOYW
133.
A recursive method upNdown is defined as follows:
public void upNdown(int n)
{
if (n > 1)
{
if (n % 2 != 0) upNdown(n+1);
else upNdown(n/2);
System.out.println(“*”);
}
}
How many stars are displayed when upNdown(5) is called?
1
2
3
4
5
134.
Given
String a = “a”, b = “b”, zero = “”;
Integer c = new Integer(0);
what is the output of
System.out.println(
((a+b)+c).equals(a+(b+c)) + ” ” +
(c + zero).equals(zero + c) + ” ” +
(a + null).equals(a + “null”));
false false false
false true true
true false true
true true false
true true true
135. (AB)
The method below uses a stack to check whether parentheses and brackets match in a string of characters:
public boolean parensAndBracketsMatch(String expr)
{
Stack s = new ArrayStack();
char ch0, ch;
for (int k = 0; k < expr.length(); k++)
{
ch = expr.charAt(k);
if (ch == ‘(‘ || ch == ‘[‘)
s.push(new Character(ch));
else if (ch == ‘)’ || ch == ‘]’)
{
if (s.isEmpty())
return false;
ch0 = ((Character)s.pop().charValue();
if ((ch0 == ‘(‘ && ch != ‘)’) ||
(ch == ‘[‘ && ch != ‘]’))
return false;
}
}
return true;
}
However, it has a bug. For which of the following strings does this method return a result that is DIFFERENT from what is expected?
Expected result:
“[(a+b) * (c+d)]/2” true
“[(a+b) * (c+d)/2]” true
“[(a+b) * (c+d)]/2[” false
“](a+b) * (c+d)/2[” false
“[(a+b] * x, int[] y)
{
x[0] = x[0] – 2 * x[0] * y[1];
y[1] = y[1] – 2 * x[0] * y[0];
}
public void mixUp(int[] x, int[] y)
{
int d = 2 * x[0] * y[1];
x[0] -= d;
y[1] -= d;
}
Suppose the following arrays are declared and initialized:
int[] a = {1, 1}, b = {0, 0}, c = {1, 1};
Which of the following calls to mixUp result in the same values in a, b, and c for bother versions of the code?
I. mixUp(a, a)
II. mixUp(a, b)
III. mixUp(a, c)
I only
II only
I and II
II and III
I, II, and III
137.
The Binary Search algorithm normally finds a value in an array sorted in ascending order. Suppose that by mistake the algorithm is used on an unsorted array with the following seven elements:
1 3 2 5 13 8 21
Which of the following target values will NOT be found?
1
3
5
13
21
138.
An array has 4095 = 212 -1 elements, arranged in ascending order. Binary Search is used to find the position of a target value. This Binary Search is implemented iteratively, in such a way that in each iteration the target is compared to one of the elements of the array. Suppose we know that the target is somewhere in the array. What number of iterations guarantees that a target value is found.
10
11
12
2047
4095
139.
Which of the following arithmetic expressions maps the values x = 0, 1, 2, 3, 4, 5, 6 onto y = 4, 3, 9, 8, 7, 6, 5, respectively?
y = 11 – x + (x + 4) % 7;
y = (4 – x) % 7 + 2 * x;
y = 3 + (8 – x) % 7;
y = 9 – (x – 2) % 7;
y = 4 + x % 7 – 2 * x;
140.
The method below implements a simplified square cipher:
public char[][] encrypt(char[][] key, String msg)
{
int i, j, n = key.length, k = 0;
char[][] result = new char[n][n]; // fills with spaces
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (key[i][j] == ‘x’)
result[i][j] = msg.charAt(k++);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (key[i][j] == ‘x’)
result[n-i-1][n-j-1] = msg.charAt(k++);
return result;
}
If key is a 4 by 4 matrix
.x..
x..x
.xx.
xx.x
and msg is “ransom received “, which of the following matrices is returned from encrypt(key, msg)?
a. rean
csoe
mivr
d e b. rde
avin
esoc
m er c. rvc
aein
dsoe
m er d. rdsr
no
aeve
iemc e. rcan
esoi
mvre
d ee
Questions 141-142 use the following class:
public class Circle
{
private int xCenter, yCenter, radius;
public Circle(int x, int y, int r)
{
xCenter = x;
yCenter = y;
radius = r;
}
public void moveTo(int x, int y)
{
xCenter = x;
yCenter = y;
}
// Draw this circle in the graphics context g
public void draw(Graphics g) { < code not shown > }
}
141.
Suppose the following code is added to a method that repaints a window within a graphics context g:
for (int x = 10; x <= 30; x += 10)
{
Circle circle = new Circle(x + 100, 100, x);
circle.draw(g);
}
The origin of the coordinate system in in the upper left corner of the window with the y-axis pointing down. Which of the following pictures will be displayed?
a.
b.
c.
d.
e.
142.
The method drawOrnament draws several circles, as follows:
public void drawOrnament(Graphics g, int k)
{
if (k < 8)
return;
Circle c = new Circle(100 – k, 100 – k, k);
c.draw(g);
c.moveTo(100 + k, 100 + k);
c.draw(g);
drawOrnament(g, k/2);
}
Which of the following pictures is produced by drawOrnament(g, 32)?
a.
b.
c.
d.
e.
143.
What is displayed by
System.out.println(expand(expand(“1001”)));
where expand is defined as follows?
public String expand(String s)
{
String d = “”;
for (int i = 0; i < s.length(); i++)
switch (s.charAt(i))
{
case ‘0’: d += “01”; break;
case ‘1’: d += “10”; break;
}
return d;
}
1001
1*0*0*1
10010110
10*01*01*10*
1001011001101001
Questions 144-146 use the following interface and class:
public interface Toggleable
{
void toggle();
boolean isOn();
}
public class toggleSwitch implements Toggleable
{
private boolean on;
public ToggleSwitch() { on = false; }
public ToggleSwitch(boolean state) { on = state; }
public void toggle() { on != on; }
public boolean isOn() { return on; }
}
144.
Suppose we have found the ToggleSwitch.class file but have no access to its source code. Which of the following code segments, if it compiles with no errors, will convince us that ToggleSwitch implements Toggleable?
I. Toggleable x = new ToggleSwitch();
II. ToggleSwitch x = new ToggleSwitch();
x.toggle();
III. ToggleSwitch x = new ToggleSwitch();
if (!x.isOn()) x.toggle();
I only
II only
III only
II and III
I, II, and III
145.
Consider the following class that represents a set of checkboxes
public class CheckBoxSet
{
private Togleable[] buttons;
public CheckBoxSet(int nButtons)
{
< missing statements >
}
public int numButtons() { return buttons.length; }
public void push(int k) { buttons[k].toggle(); }
public boolean isOn(int k) { return buttons[k].isOn(); }
public void clear()
{
for (int k = 0; k < buttons.length; k++)
if (buttons[k].isOn())
buttons[k].toggle();
}
}
Which of the following can replace < missing statements> in the CheckBoxSet constructor?
I. buttons = new Toggleable[nButtons];
for (int k = 0; k < buttons.length; k++)
buttons[k] = new ToggleSwitch();
II. buttons = new ToggleSwitch[nButtons];
clear();
III. buttons = new ToggleSwitch[nButtons];
for (int i = 0; i < buttons.length; i++)
if (buttons[i].isOn())
buttons[i].toggle();
I only
II only
I and II
II and III
I, II, and III
146. (AB)
A set of “radio buttons” is a user interface control used to choose one of several options. For example:
small medium large
Consider the following class RadioSet that implements a set of radio buttons:
public class RadioSet extends CheckBoxSet
{
// precondition: nButtons > k >= 0
// postcondition: creates an array of nButtons and
// sets the k-th button to “on”
public RadioSet(int nButtons, intk)
{
super(nButtons);
push(k);
}
// postcondition: sets the k-th button to “on”, all other
// buttons to “off”
public void push(int k)
{
< missing code >
}
// postcondition: returns the number of the button that is “on”;
// throws an exception if none are “on”
{
for (int k = 0; k < numButtons(); k++)
if (isOn(k))
return k;
throw IllegalStateException();
}
}
Which of the following can replace < missing code> in this class?
I. clear();
push(k);
II. clear();
super.push(k);
III. for (int j = 0; j < numButtons(); j++)
if (buttons[j].isOn())
buttons[j].toggle();
buttons[k].toggle();
I only
II only
I and II
II and III
I, II, and III
147. (AB)
char[][] m holds the following picture:
……..
..xxxxx.
..xx….
..xxx…
….xxx.
……x.
.x.xxx..
..xxx…
……..
What picture is stored in m after process(m) is called? The method process is defined as follows:
public void process(char[][] m)
{
int rows = m.length, cols = m[0].length, r, c;
char[][] t = new char[rows][cols];
for (r = 0; r < rows; r++)
for (c = 0; c < cols; c++)
t[r] = m[r];
for (r = 1; r < rows; r++)
for (c = 1; c < cols; c++)
if (t[r] == ‘x’ && (t[r-1] != ‘x’
|| t[r][c-1] != ‘x’))
m[r] = ‘x’;
else
m[r] = ‘.’;
}
a. ……..
..xxxxxx
..xxxxx.
..xxxx..
..xxxxxx
….xxxx
.xxxxxx.
.xxxxx..
..x….. b. ……..
..xxxxx.
..x…..
..x.x…
….xxx.
……x.
.x.xxx..
..x…..
…….. c. ……..
..xxxxxx
……..
..xxx…
…..xx.
……..
.x.xxx..
..x…..
…….. d. ……..
…xxxx.
…x….
…xx…
…..xx.
……..
….xx..
…xx…
…….. e. ……..
..xxxxx.
..xxx…
..xxx…
….xxx.
……x.
.x.xxxx.
..xxxx..
……..
148.
Suppose Mergesort is implemented as follows:
public void sort(int[] a, int n1, int n2)
{
if (n1 == n2)
return;
else if (n2 == n1 + 1)
{
if (a[n2] < a[n1])
swap(a, n1, n2); // swaps a[n1] and a[n2]
return;
}
int m = (n1 + n2) / 2;
sort(a, n1, m);
sort(a, m+1, n2);
if (a[m] > a[m+1])
merge(a, n1, m, n2); // merges a[n1]…a[m] and a[m+1]…a[n2]
}
How many times will the method merge be called if an array a contains the values
2 1 4 3 6 5 8 7
and sort(a, 0, 7) is called?
7
4
3
1
0
149. (AB)
Consider the following method:
public void xQ(Queue q)
{
if (q.isEmpty())
return;
Queue q1 = new ListQueue(), q2 = new ListQueue();
Object x = q.dequeue();
while (!q.isEmpty())
{
Object y = q.dequeue();
if (((Comparable)y).compareTo(x) <= 0)
q1.enqueue(y);
else
q2.enqueue(y);
}
xQ(q1);
xQ(q2);
while (!q1.isEmpty())
q.enqueue(q1.dequeue());
q.enqueue(x);
while (!q2.isEmpty())
q.enqueue(q2.dequeue());
}
What are the values in q after xQ(q) is called, if q initially holds Integer objects with the values 7, 11, 3, 5, 6, 0 (listed starting from the front)?
0, 3, 5, 6, 7, 11
0, 6, 5, 3, 11, 7
3, 5, 6, 0, 7, 11
11, 3, 5, 6, 0, 7
11, 7, 6, 5, 3, 0
150. (AB)
Consider the following method:
public int xSum(TreeNode root)
{
if (root == null)
return 0;
else
return ((Integer)root.getValue()).intValue() +
xSum(root.getRight()) – xSum(root.getLeft());
}
What value is returned by xSum(root) if root points to the following tree?
5
/
4 2
/ /
3 7 1
12
-9
-10
5
12
20
1999
151.
What is the output from the following code?
int x = 5, y = 2;
System.out.println(x/y – (double)(x/y));
0
0.5
-0.5
-2.5
None of the above
152.
What are the values of u and v after the following code is executed?
int u = 3, v = 5;
u += v;
v += u;
u -= v;
v -= u;
0, 0
3, 5
5, 3
-5, -3
-5, 18
153.
Which of the following does NOT display 9.95?
System.out.println(9 + 0.95);
System.out.println(995/100.0);
System.out.println(9. + 95/100);
System.out.println(9 + 95.0/100);
System.out.println(9 + “.” + 95);
154.
What is the output from the following code?
int count1 = 0, count2 = 0, inc = 1;
for (int i = 0; i < 11; i++)
{
count1 += inc;
inc = -inc;
count2 += inc;
}
System.out.println(count1 – count2);
0
2
-2
22
-22
155.
What is the result of the following code segment?
Integer i = new Integer(0); // Line 1
if (!i.equals(0)) // Line 2
System.out.println(i + ” does not equal to ” + 0); // Line 3
else
System.out.println(“Done”);
Syntax error on Line 2
Syntax error on Line 3
ClassCastException
0 is not equal to 0
Done
156.
What is the output from the following code?
int a = 0, b = 0;
while (a < 3)
{
switch(a + b)
{
case 0: a++;
case 1:
case 2: b++; break;
case 3: a++; break;
default: b = 0; break;
}
System.out.print(b);
}
0123
122011
0122011
0122123
112300
157.
What is the value of n after the following code is executed?
int i, n = 0;
while (n < 90)
{
for (i = 0; i < 10; i++)
{
n += 3;
if (n > 50)
break;
}
n++;
}
51
61
91
93
104
158.
What is the set of all possible outputs of the following code when the user correctly follows the input instructions and the program terminates without an error?
System.out.print(
“Enter an integer from -1000 to 1000 (inclusive): “);
int n = console.readInt(); // Read an integer
while (n > 0 && Math.sqrt(n) < 10.0)
n++;
System.out.println(n);
{0, …, 99, 100}
{100, …, 999, 1000}
{-1000, -999, …, 0} union {100, …, 999, 1000}
{-1000, -999, …, 0, …, 999, 1000}
{-1000, -999, …, 0, …, 99}
159.
An integer array a has 19 elements. What is the value of the middle element after the following code is executed?
int i, j, n = 19;
for (i = 0; i < n; i++)
a[i] = i+1;
for (i = 0, j = n-1; i <= j; i++, j–)
a[(i+j)/2] -= (a[i] + a[j]) / 2;
0
10
-41
-62
-71
160.
Consider the following method:
public void mysteryMix(Integer a, Integer b)
{
a = new Integer(2 * a.intValue());
b = a;
}
What is the output of the following code?
Integer a = new Integer(1);
Integer b = new Integer(2);
mysteryMix(a, a);
mysteryMix(a, b);
System.out.println(a + ” ” + b);
1 1
1 2
2 2
1 4
4 4
161.
The following interface Index describes the location of a document:
public interface Index
{
String getKey();
Document getAddress();
}
Document is a class that has a public method getSize(). An ArrayList folder contains Index objects and describes a collection of documents. Which of the following expressions refers to size of the k-th document in folder?
folder[k-1].getAddress().getSize()
(Index) folder.get(k-1).getAddress().getSize()
((Index) folder.get(k-1)).getAddress().getSize()
((Document) (folder[k-1].getAddress())).getSize()
((Document) (folder.get(k-1).getAddress())).getSize()
162.
Which of the following could safely appear and make sense in place of < condition > in some suitable context?
if ( < condition > )
msg = new message(“o”);
I. msg == null || msg.getStatus().equals(“x”)
II. msg.getStatus().equals(“x”) || msg == null
III. “x”.equals(msg.getStatus()) || msg == null
I only
II only
I and II
II and III
I, II, and III
Questions 163-167 use the following interface and classes used in a picture drawing application:
public interface Drawable
{
void draw(Graphics g);
}
public class Line implements Drawable
{
private int xBeg, yBeg, xEnd, yEnd;
public Line(int x0, int y0, int x1, int y1)
{
xBeg = x0; yBeg = y0; xEnd = x1; yEnd = y1;
}
public void draw(Graphics g)
{
g.drawLine(xBeg, yBeg, xEnd, yEnd);
}
}
public class Picture implements Drawable
{
private List pictures;
public Picture()
{
pictures = new LinkedList();
}
public void add(Drawable obj)
{
pictures.add(obj);
}
public void draw(Graphics g)
{
Iterator it = pictures.iterator();
while (it.hasNext())
((Drawable) it.next()).draw(g);
}
}
163.
Which of the following code segments compiles with no errors?
Drawable picture = new Picture(new Line(0, 0, 100, 100));
Drawable picture = new Picture();
picture.add(new Line(0, 0, 100, 100));
Picture picture1 = new Picture();
Picture picture2 = new Picture(picture1);
Picture picture = new Picture();
picture.pictures.add(new Line(0, 0, 100, 100));
Drawable picture = new Picture();
((Picture) picture).add(new Picture());
164.
Consider the following code segment:
Picture picture = new Picture();
picture.add(new Line(100, 100, 200, 50));
picture.add(new Line(200, 50, 300, 100));
Picture box = new Picture();
box.add(new Line(100, 100, 100, 300));
box.add(new Line(100, 300, 300, 300));
box.add(new Line(300, 300, 300, 100));
box.add(new Line(300, 100, 100, 100));
Which of the following pictures will be displayed when pictures.draw(g) is called from an appropriate paint method within the graphics context g?
a. Empty picture b.
c.
d.
e.
165.
Suppose the class Box extends Picture and has the following constructor:
public Box(int x, int y, int width, int height)
{
super();
add(new Line(x, y, x + width, y));
add(new Line(x + width, y, x + width, y + height));
add(new Line(x + width, y + height, x, y + height));
add(new Line(y, y + height, x, y));
}
Suppose the statements
Box box = new Box(100, 100, 300, 200);
box.draw(g);
—when executed from an appropriate paint method within the graphics context g—draw a box with the upper left corner at (100, 100), width 300 and height 200. Besides the above constructor, which methods must be supplied in the Box class for this to happen?
No methods are needed
add(Drawable)
draw(Graphics)
add(Drawable) and add(Graphics)
add(Drawable), add(Line), and draw(Graphics)
166.
Suppose the following statements have been added to the Line class:
public String getName() { return “Line”; }
public String toString()
{
return “[” + getName() +
/* ” ” + xBeg + ” ” + yBeg +
” ” + xEnd + ” ” + yEnd + */
“]”;
}
Also, the following methods have been added to the Picture class:
public String getName() { return “Picture”; }
public String toString()
{
String str = “[” + getName() + ” “;
Iterator it = pictures.iterator();
while (it.hasNext())
str += it.next();
return str + “]”;
}
Finally, the following method has been added to the Box class mentioned in the previous question:
public String getName() { return “Box”; }
What is the output of the following code?
Box box = new Box(100, 100, 100, 100);
box.add(new Line(100, 100, 200, 200));
box.add(new Line(100, 200, 200, 100));
Picture picture = new Picture();
picture.add(box);
System.out.println(picture);
[Picture [Line] [Line] [Line] [Line] [Line] [Line]
[Picture [Box [Line] [Line] [Line] [Line] ] ]
[Picture [Box [Line] [Line] [Line] [Line] [Line] [Line] ] ]
[Picture [Picture [Line] [Line] [Line] [Line] [Line] [Line] ]
[Picture [Picture [Line] [Line] [Line] [Line] [Line] [Line] ] ]
167.
The class DrawingBoard extends JFrame and represents a window on the screen:
public class DrawingBoard extends javax,Swing,JFrame
{
private Drawable picture;
public DrawingBoard(Drawable picture)
{ this.picture = picture; }
public void paint(Graphics g) { picture.draw(g); }
}
Consider the following code segment:
Picture picture = new Picture();
picture.add(picture); // Line ***
DrawingBoard w = new DrawingBoard(picture);
w.setBounds(50, 50, 400, 400);
w.show();
What happens when we try to compile and execute this code?
Syntax error on Line ***
ClassCastException
The code compiles and runs, but goes into an infinite loop
StackOverflowError
The code compiles and runs; a blank window is displayed
Questions 168-169 use the following class:
public class PetDog implements Comparable
{
private String myName, myBreed;
public petDog(String name, String breed)
{ myName = name; myBreed = breed; }
public String getName() { return myName; }
public String getBreed() { return myBreed; }
public boolean equals(Object other)
{ return other != null && getName.equals(other.toString()); }
public int compareTo(Object other)
{
return getName().compareTo(other.toSstring());
}
public int hashCode() { return getName().hashCode(); }
public String toString()
{ return getName() + “–” + + getBreed(); }
}
Suppose the following variables are declared and initialized:
PetDog honey = new PetDog(“Honey”, “Cocker Spaniel”);
PetDog lucie = new PetDog(“Lucie”, “Springer Spaniel”);
PetDog murray = new PetDog(“Murray”, “Golden Retriever”);
168. (AB)
The (AB)
a Cocker Spaniel
Map map = new HashMap();
map.put(honey.getName(), honey);
map.put(lucie.getName(), lucie);
map.put(murray.getName(), murray);
System.out.println(honey.getNamer() + ” is a ” +
< missing expression > );
Which of the following can replace < missing expression >?
I. PetDog(map.get(honey.getName())
II. ((PetDog)map.get(honey)).getBreed()
III. ((PetDog)map.get(honey.getName())).getBreed()
I only
II only
I and II
II and III
I, II, and III
169. (AB)
Which of the following code segments will compile with no errors and produce an alphabetical list of all three pets:
Honey — Cocker Spaniel
Lucie — Springer Spaniel
Murray — Golden Retriever
I. Set set = new TreeSet();
set.add(honey);
set.add(lucie);
set.add(murray);
Iterator iter = set.iterator();
while (iter.hasNext())
System.out.println(iter.next());
II. Map map = new TreeMap();
map.put(homey.getName(), honey);
map.put(lucie.getName(), lucie);
map.put(murray.getName(), murray);
Iterator iter = map.values().iterator();
while (iter.hasNext())
System.out.println(iter.next());
III. Map map = new HashMap();
map.put(homey.getName(), honey);
map.put(lucie.getName(), lucie);
map.put(murray.getName(), murray);
Iterator iter = map.keySet().iterator();
while (iter.hasNext())
System.out.println(map.get(iter.next()));
I only
II only
I and II
II and III
I, II, and III
170. (AB)
head1 points to the first node of a linked list that has three nodes with Integer values 0, 1, 2; head2 points to the first node of a list that has three nodes with Integer values 3, 4, 5. What is the output from the following code?
ListNode node;
if (head1 != null && head2 != null)
{
node = head1.getNext();
head1.setNext(head2.getNext());
head2.setNext(node);
}
for (node = head1; node != null; node = node.getNext())
System.out.println(node.getValue() + ” “);
for (node = head2; node != null; node = node.getNext())
System.out.println(node.getValue() + ” “);
0 1 2 3 4 5
0 4 5 3 1 2
3 4 5 0 1 2
3 0 2 0 4 5
3 0 1 2 4 5
171. (AB)
What is the contents of the stack s1 (its elements listed starting from the top) after the following code is executed?
Stack stk = new ArrayStack();
Stack stk1 = new ArrayStack();
Stack stk2 = new ArrayStack();
int n;
Integer obj;
for (n = 1; n <= 6; n++)
stk.push(new Integer(n));
while (!stk.isEmpty())
{
obj = (Integer stk.pop());
n = obj.intValue();
if (N % 2 != 0)
stk1.push(obj);
else
stk2.push(obj);
}
while (!stk1.isEmpty())
stk.push(stk1.pop());
while (!stk2.isEmpty())
stk.push(stk2.pop());
1, 2, 3, 4, 5, 6
6, 5, 4, 3, 2, 1
1, 3, 5, 2, 4, 6
2, 4, 6, 1, 3, 5
None of the above
172. (AB)
Consider the following method:
public boolean someProperty(TreeNode root)
{
return root != null &&
(root.getLeft() != null && root.getRight() != null ||
someProperty(root.getLeft()) ||
someProperty(root.getRight()));
}
This method returns true if and only if the tree pointed to by root
is not empty.
is not empty and the root is not a leaf.
is not empty and the root is either a leaf or has two children.
has at least one node with two children.
is a full tree.
173. (AB)
The method max(TreeNode root) assumes a precondition that root points to a non-empty binary search tree containing Comparable objects. max returns the value from the tree’s largest node. Which of the following three versions of max return the correct answer when the precondition is met?
I. public Object max(TreeNOde root)
{
while (root.getRight() != null)
root = root.getRight();
return root.getValue();
}
II. public Object max(TreeNOde root)
{
Object maxValue = root.getValue();
if (root.getRight() != null)
{
Object temp = max(root.getRight());
if (((Comparable)temp).compareTo(maxValue) > 0)
maxValue = temp;
}
return maxValue;
}
III. public Object max(TreeNOde root)
{
Object maxValue = root.getValue();
if (root.getLeft() != null &&
((Comparable)max(root.getLeft())).
compareTo(maxValue) > 0)
maxValue = max(root.getLeft());
if (root.getRight() != null &&
((Comparable)max(root.getRight())).
compareTo(maxValue) > 0)
maxValue = max(root.getRight());
return maxValue;
}
I only
II only
I and II
II and III
I, II, and III
174.
Given
int[] a = {1, 3, 5, 7, 9, 11, 13};
what are the values in a after disarray(int[] a, int n) is called? The method disarray is defined as follows:
public void disarray(int[] a, int n)
{
if (n > 1)
{
disarray(a, n-1);
a[n-1] += a[n-2];
}
}
1, 4, 9, 16, 25, 36, 49
1, 4, 8, 12, 16, 20, 24
1, 8, 12, 16, 20, 24, 13
1, 24, 20, 16, 12, 8, 4
None of the above
175.
The method mixup is defined as follows:
String mixup(String word)
{
if (word.length() == 1)
return “”;
else
return mixup(word.substring(0, word.length() – 1))
+ word.charAt(word.length() – 1);
}
What is the value of the string returned by mixup(“IDEAL”)?
IDEAL
IDEA
LEAD
LEDA
DEAL
Answer of ques no. 5
Chitkara ka paper de rha h kya