<![CDATA[
CSE143 Sample Midterm handout #12
Autumn 2022
1. Recursive Tracing, 15 points. Consider the following method:
public void mystery(int x) {
System.out.print("*");
if (x == 0) {
System.out.print("=");
} else {
int y = x % 10;
if (y < 5) {
System.out.print(y);
mystery(x / 10);
} else {
mystery(x / 10);
System.out.print(y);
}
}
}
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(9); _____________________________________
mystery(42); ______________________________________
mystery(703); ______________________________________
mystery(5821); ______________________________________
mystery(83105); ______________________________________
2. Recursive Programming, 15 points. Write a recursive method called
countDigit that takes a digit d and an integer n as parameters and that
returns the number of times d occurs in n. For example, the call
countDigit(3, 5323313) would return 4 because there are 4 occurrences of the
digit 3 in 5323313. Your method should throw an IllegalArgumentException if
the digit is less than 0 or if the digit is greater than 9 or if n is less
than 0. Below are more sample calls:
Method Value Method Value
Call Returned Call Returned
--------------------------------- ---------------------------------
countDigit(2, 2) 1 countDigit(9, 919) 2
countDigit(0, 0) 1 countDigit(0, 1234) 0
countDigit(0, 304) 1 countDigit(5, 152535) 3
countDigit(7, 12345) 0 countDigit(7, 777777) 6
countDigit(5, 555) 3 countDigit(4, 4) 1
You are not allowed to construct any structured objects to solve this
problem (no string, array, ArrayList, StringBuilder, Scanner, etc) and you
may not use a while loop, for loop or do/while loop to solve this problem;
you must use recursion.
3. Details of inheritance, 20 points. Assuming that the following classes have
been defined:
public class Wall extends Dragon {
public void method1() {
System.out.println("Wall 1");
}
public void method3() {
System.out.println("Wall 3");
}
}
public class Raven {
public void method1() {
System.out.println("Raven 1");
}
public void method2() {
System.out.println("Raven 2");
method1();
}
}
public class Dragon extends Raven {
public void method1() {
System.out.println("Dragon 1");
super.method1();
}
}
public class Hand extends Raven {
public void method3() {
System.out.println("Hand 3");
}
}
And assuming the following variables have been defined:
Raven var1 = new Wall();
Raven var2 = new Dragon();
Raven var3 = new Raven();
Object var4 = new Dragon();
Dragon var5 = new Wall();
Object var6 = new Hand();
In the table below, indicate in the right-hand column the output produced by
the statement in the left-hand column. If the statement produces more than one
line of output, indicate the line breaks with slashes as in "a/b/c" to indicate
three lines of output with "a" followed by "b" followed by "c". If the
statement causes an error, fill in the right-hand column with either the phrase
"compiler error" or "runtime error" to indicate when the error would be
detected.
Statement Output
------------------------------------------------------------
var1.method1(); ____________________________
var2.method1(); ____________________________
var3.method1(); ____________________________
var4.method1(); ____________________________
var5.method1(); ____________________________
var6.method1(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
((Dragon)var1).method3(); ____________________________
((Hand)var6).method3(); ____________________________
((Wall)var4).method1(); ____________________________
((Raven)var6).method2(); ____________________________
((Raven)var4).method1(); ____________________________
((Wall)var6).method3(); ____________________________
((Wall)var3).method3(); ____________________________
((Wall)var5).method3(); ____________________________
4. Linked List Nodes, 15 points. Fill in the "code" column in the following
table providing a solution that will turn the "before" picture into the
"after" picture by modifying links between the nodes shown. You are not
allowed to change any existing node's data field value and you are not
allowed to construct any new nodes, but you are allowed to declare and use
variables of type ListNode (often called "temp" variables). You are limited
to at most two variables of type ListNode for each of the four subproblems.
You are writing code for the ListNode class discussed in lecture:
public class ListNode {
public int data; // data stored in this node
public ListNode next; // link to next node in the list
<constructors>
}
As in the lecture examples, all lists are terminated by null and the
variables p and q have the value null when they do not point to anything.
before after code
-----------------------+-----------------------+-------------------------------
p->[1] | p |
| |
| |
q->[2]->[3] | q->[2]->[3]->[1] |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2]->[3] | p->[2]->[3] |
| |
| |
q | q->[1] |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2] | p->[2] |
| |
| |
q->[3]->[4] | q->[4]->[3]->[1] |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
| |
| |
p->[1]->[2] | p->[4]->[2]->[3] |
| |
| |
q->[3]->[4]->[5] | q->[5]->[1] |
| |
| |
| |
| |
| |
| |
| |
| |
-----------------------+-----------------------+-------------------------------
5. Array Programming, 10 points. Write a method called removeLast that takes
an integer n as a parameter and that removes the last occurrence of n from a
list of integers if it exists. For example, if a variable called list
stores this sequence of values:
[3, 5, 7, 3, 19, 42, 8, 23, 5, 5, 5, 7, 2, -8, 3, 5, -3]
and the following call is made:
list.removeLast(3);
Then the final occurrence of 3 is removed, leaving this list:
[3, 5, 7, 3, 19, 42, 8, 23, 5, 5, 5, 7, 2, -8, 5, -3]
If the same call is made again, then the list becomes:
[3, 5, 7, 19, 42, 8, 23, 5, 5, 5, 7, 2, -8, 5, -3]
Notice that in each case the last occurrence of the value is removed. If
the value does not appear in the list, then the method should leave the list
unchanged.
You are writing a method for the ArrayIntList class discussed in lecture:
public class ArrayIntList {
private int[] elementData; // list of integers
private int size; // current # of elements in the list
<methods>
}
You may not call any other methods of the ArrayIntList class to solve this
problem, you are not allowed to define any auxiliary data structures (no
array, String, ArrayList, etc), and your solution must run in O(n) time
where n is the length of the original list.
6. Stacks/Queues, 25 points. Write a method called splitStack that
takes a stack of integers as a parameter and that rearranges the values so
that all of the even values appear before the odd values and that otherwise
preserves the original order of the stack. For example, suppose a stack
called s stores this sequence of values:
bottom [3, 5, 4, 17, 6, 83, 1, 84, 16, 37] top
If we make the following call:
splitStack(s);
The stack should store the following values after the call:
bottom [4, 6, 84, 16, 3, 5, 17, 83, 1, 37] top
Notice that all of the evens appear at the bottom of the stack followed by
the odds and that the order of the evens is the same as in the original
stack and the order of the odds is the same as in the original stack.
You are to use one queue as auxiliary storage to solve this problem. You
may not use any other auxiliary data structures to solve this problem,
although you can have as many simple variables as you like. You also may
not solve the problem recursively. Your solution must run in O(n) time
where n is the size of the stack. Use the Stack and Queue structures
described in the cheat sheet and obey the restrictions described there
(recall that you can't use the peek method or a foreach loop or iterator).
]]>