1.
Key to answering question: the == function, when called on reference
types, compares the equality of their memory addresses. Thus, while two
objects may contain identical data, as they are not the same object, ==
will return false. Java fudges this a bit with String objects due to the
fact that newly created strings with the same content will sometimes be
constructed as pointers to the same memory location. However, this is not
a universal occurrance, and the == function should not be used to test
String equality.
false
true
false
true
true
true
false (sometimes true, but not guaranteed to be)
true
true
2.
((List)Alist.head).tail.tail=Alist.tail;
Alist.tail=((List)Alist.head).tail;
Alist.tail.tail.tail.tail=Alist;
Alist.head=Alist.tail.tail.tail;
Visual step by step:
Initial:
Alist
|
|
|
|->|--|--| |--|--| |--|--| |--|--|
|| | --->|3 | --->|4 | --->|5 |//|
||-|--| |--|--| |--|--| |--|--|
| ^
V |
|--|--| |--|--| /
|1 | --->|2 | ---/
|--|--| |--|--|
After ((List)Alist.head).tail.tail=Alist.tail;
Alist
|
|
|
|->|--|--| |--|--| |--|--| |--|--|
|| | --->|3 | --->|4 | --->|5 |//|
||-|--| |--|--| |--|--| |--|--|
| ^
V |
|--|--| |--|-||
|1 | --->|2 | ||
|--|--| |--|--|
After Alist.tail=((List)Alist.head).tail;
Alist
|
|
|
|->|--|--| |--|--| |--|--| |--|--|
|| | || |3 | --->|4 | --->|5 |//|
||-|-|| |--|--| |--|--| |--|--|
| | ^
| +----+ |
| | |
V V |
|--|--| |--|-||
|1 | --->|2 | ||
|--|--| |--|--|
After Alist.tail.tail.tail.tail=Alist;
Alist
| +----------------------+
| | |
| V |
|->|--|--| |--|--| |--|--| |
|| | || |3 | --->|4 | ---+
||-|-|| |--|--| |--|--|
| | ^
| +----+ |
| | |
V V |
|--|--| |--|-||
|1 | --->|2 | ||
|--|--| |--|--|
After Alist.head=Alist.tail.tail.tail;
Alist
| +----------------------+
| | |
| V |
|->|--|--| |--|--| |--|--| |
|| | || |3 | --->|4 | ---+
||-|-|| |--|--| |--|--|
| | ^ ^
| +----+ | |
| | | |
| V | |
| |--|-|| |
| |2 | || |
| |--|--| |
| |
+------------------+
3.
Syntax:
Line 2: failure to declare type of N
Line 6: non-static reference to static variable N
Line 7/10: initializing last to N-1 and then accessing Ary[i+1] will give
an array index out of bounds error
Line 17: failure to declare type of myAry
Line 19: attempt to reference class as if it was an array
Line 23: type of variable i not declared
Line 24: attempt to reference class as if it was an array
Line 24: failure to cast from Object to Integer
Functional:
Line 7: this line needs to be within the for loop
Line 9: condition should be i>=0. Arrays are zero indexed.
Working code:
/*Locate and correct the errors in the following segment of code. (The
mainmethod should print 90)
*/
public class ArrayMKII{
private static final int N=32;
private Object [] Ary = new Object [N];
public void RightRotateVariable(int N){
int last = Ary.length-1;
for(; N>0; N--){
Object temp=Ary[last];
for(int i = last-1; i>=0; i--){
Ary[i+1]=Ary[i];
}
Ary[0]=temp;
}
}
public static void main(String [] args){
ArrayMKII myAry=new ArrayMKII();
for(int i=0;i<=31; i++){
myAry.Ary[i]=new Integer(i);
}
myAry.RightRotateVariable(3);
int j=0;
for(int i=0; i<3; i++){
Integer temp =(Integer) myAry.Ary[i];
j+=temp.intValue();
}
System.out.println(j);
}
}
4.
a: {2 5 5 6 3}
b: {7 8 1 3 7}
c: {4 9 3 3 6}
d: {{2 5 5 6 3}{2 4 3 2 5 6}{4 9 3 3 6}}
5.
+-+ +-+-+ +-+-+ +-+-+ +-+-+
l: |-+--->|||-+-->|||-+-->|||-+-->|||/+
+-+ +++-+ +++-+ +>+++-+ +++-+
| | | | ^ |
| | | | | |
V V | V | V
"1" "2" | "6" | "4"
| |
| |
+-+ | |
m: |-+------------------+ |
+-+ |
|
|
+-+ +-+-+ |
n: |-+--->|||-+---------------+
+-+ +++-+
|
|
V
"5"
6. Given the following class definitions:
class ListNode {
ListNode next;
Object item;
}
class List {
ListNode head;
}
Write a method to go inside the list class that will reverse the order of
the listnodes pointed to by head. The function header should look like
this:
public void Reverse();
my Answer:
public void Reverse() {
if ((head != null) && (head.next != null)) {
ListNode l = head;
ListNode unprocessed = head.next;
head.next = null;
while (unprocessed != null) {
ListNode temp = unprocessed.next;
unprocessed.next = l;
l = unprocessed;
unprocessed = temp;
}
head = l;
}}
7.
public static void printAllBitStrings(int n) {
helper(n, "");
}
private static void helper(int n, String append) {
if (n == 0) {
System.out.println(append);
} else if (n == 1) {
System.out.println("1" + append);
System.out.println("0" + append);
}
else {
helper(n - 1, "1" + append);
helper(n - 2, "10" + append);
}
}
8.
public class ListNode {
public Object obj;
public ListNode next;
public ListNode prev;
-> /* fill in with a constructor which takes three arguments:
1. an Object to place in obj
2. a ListNode object to place in next
3. a ListNode object to place in prev
*/
public ListNode(Object obj, ListNode next, ListNode prev) {
this.obj = obj;
this.next = next;
this.prev = prev;
}
}
public class List {
public List() {
head = null;
tail = null;
currentNode = null;
}
/* append should add a new node containing newObj to the end of
this list
make sure you deal with any special cases that arise
*/
public void append(Object newObj) {
-> /* fill in */
if ((tail == null) && (head == null)) {
// list is empty
ListNode newNode = new ListNode(newObj, null, null);
head = newNode;
tail = newNode;
}
else {
// list has a node in it
tail.next = new ListNode(newObj, null, tail); // add new node
tail = tail.next; // advance the tail
}
}
/* prepend should add a new node containing newObj to the beginning
of this list
make sure you deal with any special cases that arise
*/
public void prepend(Object newObj) {
if ((tail == null) && (head == null)) {
// list empty
ListNode newNode = new ListNode(newObj, null, null);
head = newNode;
tail = newNode;
}
else {
head.prev = new ListNode(newObj, head, null); // create and attach new node
head = head.prev; // link it up
}
}
/* returns the obj in the ListNode that is currently being
pointed to
THROWS an NullCurrentNodeException if the currentNode is null
*/
public Object getCurrent() {
if (currentNode == null) throw new NullCurrentNodeException();
return currentNode.obj;
}
/* advances the current ListNode pointed to
THROWS an NullCurrentNodeException if the currentNode is null
*/
public void advanceToNext() {
if (currentNode == null) throw new NullCurrentNodeException();
currentNode = currentNode.next;
}
/* removes the node pointed to by currentNode and returns the value
stored in that node
THROWS an NullCurrentNodeException if the currentNode is null
*/
public Object removeCurrent() {
if (currentNode == null) throw new NullCurrentNodeException();
Object obj = currentNode.obj; // save for return
if (currentNode == head) {
head = head.next; // advance head pointer
head.prev = null; // dettach
}
else if (currentNode == tail) {
tail = tail.prev; // advance tail pointer
tail.next = null; // dettach
}
else {
currentNode.prev.next = currentNode.next; // dettach node right before
currentNode.next.prev = currentNode.prev; // dettach node right after
}
return obj;
}
/* resets the current pointed to ListNode to the list head
NOTE: THIS MUST BE DONE BEFORE STARTING ANY WALK-THROUGH!
MAKE SURE YOUR LIST HAS BEEN INITIALIZED OR IT WILL NOT WORK!
*/
public void setToBeginning() {
currentNode = head;
}
/* resets the current pointed to ListNode to the end of the
list */
public void setToEnd() {
currentNode = tail;
}
private ListNode head; // points to the first node in this list
private ListNode tail; // points to the last node in this list
private ListNode currentNode; // points to the current node
during a walk through
}
9.
public class MyDequeue implements Dequeue {
public void push(Object obj) { // places a new object onto the top
internalList.prepend(obj);
}
public void enqueue(Object obj) { // places a new object onto the back
internalList.append(obj);
}
public Object popTop() { // pops off the top
internalList.setToBeginning(); // move internal pointer to top
try {
Object obj = internalList.getCurrent(); // save for return
internalList.remove(); // trash it
}
catch (NullCurrentNodeException e) {
throw new DequeueEmpty();
}
return obj;
// you could have also used peekTop
}
public Object popTail() { // pops off the back
internalList.setToEnd(); // move internal pointer to tail
try {
Object obj = internalList.getCurrent(); // save for return
internalList.remove(); // trash it
}
catch (NullCurrentNodeException e) {
throw new DequeueEmptyException();
}
return obj;
// you could have also used peekTail
}
public Object peekTop() { // looks at the item on the top w/o popping
internalList.setToBeginning();
try {
return internalList.getCurrent();
}
catch (NullCurrentNodeException e) {
throw new DequeueEmptyException();
}
}
public Object peekTail() { // looks at the item on the back w/o poppin
internalList.setToEnd();
try {
return internalList.getCurrent();
}
catch (NullCurrentNodeException e) {
throw new DequeueEmptyException();
}
}
public Dequeue() { // constructor
internalList = new List();
}
private List internalList;
}
10.
a. Interfaces have the advantage that many of them can be implemented by one class.
b. They're both right! Java is both compiled and interpreted.
c. Yes and no. He's right about y being 9, but x will not be 12. It will remain
7. The pointer reference i is duplicated just like the primitive int j. So, i
does not succumb to reassignment. A method could have been called on i to change
the internal value, but not a simple assignment. Moreover, a newly instantiated
object's constructor arguments are not affected by changes either.
sample diagram:
x y
+---+ +---+
| 7 | | 9 |
+---+ +---+
on calling breaker:
i j
+---+ +---+
| | | | 9 |
+-|-+ +---+
|
|
V
+---+
| 7 |
+---+
just before breaker returns
i j
+---+ +---+
| | | | 9 |
+-|-+ +---+
|
--> +----+
| 12 |
+----+
+---+
| 7 |
+---+
11-14 solutions are at the bottom of this linked page
15.1. False will be printed to the screen. The logical equality (==)
operator should only be used on primitive types. Here, args[0]
and args[1] are references to strings. The logical equality
operator tests whether or not they are referring to the same
object (not the case here, since the command line inputs occupy
different memory locations) -- not whether the content of those
objects is the same. To test equality of content, use the
equals() method.
15.2. A primitive can never be cast into a reference. The converse is
also not possible -- a reference type cannot be cast into a
primitive type.
15.3. In a logical AND (&&), if the first expression evaluates to false,
the second expression will not be evaluated.
15.4. The value printed to the screen is 3. The first method will
not modify the array since the value passed into the method
is only the value of the zeroth element of the array (y[0]). The
second method will modify the array, since the value passed into
the method will be the value of the reference to the array (y).
Therefore in the second method, the local variable x will point to
the original array and be able to operate on it.
15.5. A variation on the previous problem. Note here that we are
working with strings. The expression s + "!" does not append an
exclamation character onto the original string, it creates a new
string. The local reference variable (s) is then set to point at
the new string. The original string is unmodified, so 'Hey' will
be printed to the screen.
15.6. The number 2 will be printed. A break statement will break the
innermost loop or switch statement, which in this case is just the
for loop. Note that we could attach a label to this break
statement and break from either LabelA or LabelB causing a
different value to be printed to the screen.
16.
A correction should be made however, in that there should not be a
NumberOfNodes variable -- this is a holdover from a different list
implementation, and will not work for this type of
implementation. Code follows.
public class ListDriver {
public static void main (String [] args) {
List ListOne, ListTwo;
// Create a list of four elements, denoted by strings.
ListOne = new List ("Node 1",
new List ("Node 2",
new List ("Node 3",
new List ("Node 4", null))));
// Break the list.
ListTwo = ListOne.BreakList (3);
// Print the string.
System.out.println (ListOne.Head);
System.out.println (ListTwo.Head);
}
}
// Here is the method. An argument of 1 is illegal.
public List BreakList (int BreakNode) {
List Current = this;
// Cycle through the list.
for (int Node = 1; Current != null; Node ++, Current = Current.Tail) {
if (Node == BreakNode-1) {
// Check to see if a next one exists.
if (Current.Tail == null) break;
// Else, break the list.
List SecondList = Current.Tail;
Current.Tail = null;
return SecondList;
}
}
// If we didn't find the node the list isn't long enough or the
// number was invalid.
throw new IllegalArgumentException ("Node number specified is invalid!");
}