| . | |
Study this code:
String[] a = new String[3];
String[] b = a;
a[0] = "0a";
a[2] = "2a";
b[0] = "0b";
b[1] = "1b";
b[2] = a[0] + a[1] + a[2]
The final value of b[2] is... |
|
| D.
a and b refer to the exact same object. |
|
| . (1 pt.) | |
| List mlist = new ArrayList();
Does this work? |
|
| notes and answers | |
| . | |
| Let S = {a,b,c,d}. Let R = {(a,a), (b,b), (c,d), (c,a), (d,c)}. For each property, state whether R has the property (YES/NO); if not, explain why. |
B. a function (domain and range S)
|
| a) no, having both (c,d)
and (d,c) violate the requirement
b) no, the value c participates as the left member (operand) of two ordered pairs in the relation. |
|
| . (3 pts.) | |
Here is a Java method:
public static int calc(int x, int y) {
if (x > y) return x-y;
else return y-x;
}
A relation R between ints can be defined by saying: (a,b) are in R if and only if calc(a,b) <= 3. Is R an equivalence relation? First state what an equivalence relation is, and then explain why R is one or not.
|
|
| NO -- .
(1 pt.) A e.r. is one which is reflexive, symmetric, and transitive. (2 pts.) This relation is not transitive (it is reflexive and symmetric). A pair of ints (x,y) is in R if |x-y| <=3. (0,3) and (3,6) are both in R, but (0,6) is not. If you wanted to write out R in set notation you might say R = {(x,y) elt (Int,Int) : |x-y| <= 3} OR R = {(0,-3) (0,-2), (0,-1), (0,0), (0,1), (0,2), (0,3), (1,-2) (1,-1), (1,0), (1,1), (1,2), (1,3), (1,4), (2,-1) (2,0), (2,1), (2,2), (2,3), (2,4), (2,5), (3,0), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (4,1), (4,2), (4,3), (4,4), (4,5), (4,6), (4,7), (-1,-4), (-1,-3) (-1,-2), (-1,-1), (-1,0), (-1,1), (-1,2), (-2,-5), (-2,-4), (-2,-3) (-2,-2), (-2,-1), (-2,0), (-2,1), (-3,-6), (-3,-5), (-3,-4), (-3,-3) (-3,-2), (-3,-1), (-3,0), (-4,0), (-4,-6), (-4,-5), (-4,-4), (-4,-3) (-4,-2), (-4,-1), ...}
|
|
| . (4 pts.) | |
Suppose the following is part of a class which
implements a stack using an internal ArrayList.
public void push(Object value) {
this.theList.add(value);
}
Assuming that what you see is a complete and correct implementation of push,
write code for top within the same class. Make no
assumptions about the class except what you can reasonably deduce from the
code shown.
/** Return the current top of the stack, or null if the stack is empty*/ |
|
| Analysis of push: The instance
variable theList must hold the stack. Since the add method places
a new value at the end of a list, the top of the stack is at the
end. Push and top must therefore take the value from the end.
public Object top() { int last = this.theList.size() -1; if (last < 0) return null; else return this.theList.get(last); } 1 pt. method signature, general Java 1 pt. null check 2 pt. locating the last element and returning it |
|
| . | |
| Give the correct postfix corresponding to the
following Java infix expression
1 + 2 - 3 * 4 |
|
| D.
The precedence in Java (and ordinary math) is * before +. Postfix does not use parentheses. |
|
| . | |
| Consider the stack-based algorithm for checking
expressions which have balanced pairs of (), {}, and [].
The following expression { ( ) { ( ( [ ] [ ] ) ) } } has 15 symbols, the 7th of which is a [. Show the contents of the stack just after this [ has been processed by the algorithm. Please label the stack to indicate where the top is. |
answer here: |
| { { ( ( [
with the top on the right |
|
| . | |
Given an initially empty queue of characters, what
character is at the front of the queue after this series of pseudo-code operations:
enqueue('a')
enqueue('b')
x = dequeue()
enqueue(x)
enqueue('c')
enqueue('d')
x = dequeue()
x = dequeue()
enqueue('e')
enqueue(x)
|
|
| C. The full queue (front to rear) is c d e a | |
| . | |
| In the Big-O sense, rank these functions best to worst. Then pick the second worst. |
|
| The correction on E was made during
the test.
2 log n is just n. The sequence best to worst is C/A, D, B, E |
|
| . | |
| In the definition of Big-O as we learned it, n0 and c occur. If f(n) = 100 and g(n) = 2n+4, and we wish to show that f(n) is O(g(n), what value of n0 will work in the definition if c is chosen to be 1? |
|
| The smallest value (the cutover point) is found by setting f = g. Any value greater than that is a correct answer. | |
| . | |
| There are a number of strategies for implementing a queue. Among the choices listed, which one has the worst time complexity (in the Big-O sense) for the enqueue operation? |
|
| In A and B, note that it is the queue
that has the fixed or unlimited length, not the array used to
implement the queue. In the worst case, when the array is full,
and the queue length is unlimited, an enqueue operation requires
creating a new array and copy the old elements to it -- a O(N) operation
where N is the current size of the queue. For the linked list implementations, a enqueue can be done in constant time since it just involves creating a new link and adjust the rear pointer to point to it. |
|
| . | |
| Which one of the following is NOT true about using JUnit? |
|
| C. Test method names must start with "test...", but the class name can be anything, as long as it extends TestCase. | |
| . | |
Study this method:
static void arrayMyst(int[] dnums, int x) {
if (x < 0) return x;
if (dnums[x] > 0) return x;
return arrayMyst(dnums, x-1);
}
Suppose we have these parameter values: int[] numsA = new double[] {3, 2, -1, 4, -7, 8}; int x = 4; |
B. Give a value for x so that the value of arrayMyst(numsA,x) is 0, or explain why that is not possible. |
| A. 3
B. x = 0 |
|
| . (6 pts.) | |
| The capitalization of a word can suggest how to
check its spelling. For example, if a word has only capital letters, maybe it
should be looked up in a special acronym dictionary. Implement the following method recursively (no loops allowed). You may define and implement a helper method if desired (no loops in it, either!) Note: there is a static method Character.isUpperCase(char c) which returns true iff c is an upper case letter. /**Count the number of capital letters in a word.
@param word a non-null string
@return the number of capital letters in the string */
public static int countCaps(String word) {
|
|
| A helper method is needed for any
efficient implementation. With
the original parameters, there is no way to tell how much of the string
has been examined. The only alternative would be to create a new
string (a substring of the original) and pass it to countCaps; this is
inelegant and inefficient.
By the way, instead of writing Character.isUpperCase(c) you could simply say c >= 'A' && c <= 'Z'. A trick like this will work in most languages and is handy when you don't know what library methods are available. public static int countCaps(String word) {
return helper(word, 0);
}
/** Count the number of upper case characters in the word, starting at
the position given. */
public static int helper(String word, int pos) {
if (pos >= word.length()) {
return 0;
}
int currentVal = 0;
if (Character.isUpperCase(word.charAt(pos))) {
currentVal = 1;
}
return currentVal + (helper(word, pos+1));
}
|
|