Question 1: Trace the execution of the following method by listing what is print
ID: 3725128 • Letter: Q
Question
Question 1:
Trace the execution of the following method by listing what is printed when the method is invoked with the following parameters:
array = [12, 5, 6, 2, 3, 4, 7]
a=2
b=5
void recMethod(int[] array, int a, int b) {
if(b > a) {
print the array
double the value in the array at position b
recMethod(array, a, b-1)
print the array
} else {
print "done"
}
}
Question 2:
Trace the execution of the following method by listing what is printed when the method is invoked with the first node in the following chain: 4 -> 6 -> 5 -> 3 -> 2
void recMethod(Node firstNode) {
print the chain of nodes headed by firstNode
if(firstNode.next!=null) {
double the data in firstNode
recMethod(firstNode.next.next);
} else {
print "done"
}
print the chain of nodes headed by firstNode
}
Question 3:
Rewrite the getFrequencyOf method in the ArrayBag class using recursion.
For full credit, do not invoke the toArray method.
The original, non-recursive version is displayed below.
public int getFrequencyOf(T anEntry) {
int counter = 0;
for (int index = 0; index < numberOfEntries; index++) {
if (anEntry.equals(bag[index])) {
counter++;
}
}
return counter;
}
Question 4:
Rewrite the getFrequencyOf method in the LinkedBag class using recursion.
For full credit, do not invoke the toArray method.
The original, non-recursive version is below.
public int getFrequencyOf(T anEntry) {
int frequency = 0;
int counter = 0;
Node currentNode = firstNode;
while ((counter < numberOfEntries) && (currentNode != null)) {
if (anEntry.equals(currentNode.data)) {
frequency++;
}
counter++;
currentNode = currentNode.next;
}
return frequency;
}
Driver program:
import java.util.*;
public class HomeworkW07Driver {
public static void main(String[] args) {
// Note: you need to use a revised ArrayBag and LinkedBag
classes to test these methods
// Q3
ArrayBag<Integer> numbersArrayBag = new
ArrayBag<Integer>();
numbersArrayBag.add(1);
numbersArrayBag.add(2);
numbersArrayBag.add(1);
numbersArrayBag.add(4);
numbersArrayBag.add(3);
System.out.println("The bag contains[1, 2, 1, 4, 3]
" + Arrays.toString(numbersArrayBag.toArray()));
System.out.println("Should be 2: " +
numbersArrayBag.getFrequencyOf(1));
System.out.println("Should be 1: " +
numbersArrayBag.getFrequencyOf(4));
System.out.println("Should be 0: " +
numbersArrayBag.getFrequencyOf(5));
// Q4
LinkedBag<Integer> numbersLinkedBag = new
LinkedBag<Integer>();
numbersLinkedBag.add(1);
numbersLinkedBag.add(2);
numbersLinkedBag.add(1);
numbersLinkedBag.add(4);
numbersLinkedBag.add(3);
System.out.println("The bag contains[3, 4, 1, 2, 1]
" + Arrays.toString(numbersLinkedBag.toArray()));
System.out.println("Should be 2: " +
numbersLinkedBag.getFrequencyOf(1));
System.out.println("Should be 1: " +
numbersLinkedBag.getFrequencyOf(4));
System.out.println("Should be 0: " +
numbersLinkedBag.getFrequencyOf(5));
// Q5
// this is a private method- so you'll have to test it
internally!
// Q6- try it with both AList and LList!
ListInterface<Integer> numbersList = new
AList<Integer>(); // swap this out for an LList- your code should still
work!
numbersList.add(4);
numbersList.add(1);
numbersList.add(3);
numbersList.add(2);
numbersList.add(0);
numbersList.add(9);
System.out.println("Sum is 19: " + sumList(numbersList));
//Extra Credit- try it with both ArrayBag and LinkedBag!
BagInterface<Integer> numbersBag = new
ArrayBag<Integer>(); // swap this out for LinekdBag- your code should
still work!
numbersBag.add(2);
numbersBag.add(-1);
numbersBag.add(3);
numbersBag.add(5);
numbersBag.add(-2);
numbersBag.add(-4);
numbersBag.add(1);
System.out.println("The bag contains[2, -1, 3, 5, -2, -4,
1] " + Arrays.toString(numbersBag.toArray()));
System.out.println("There are 4 positives: " +
countPositives(numbersBag));
System.out.println("The bag still contains [2, -1, 3, 5,
-2, -4, 1] " + Arrays.toString(numbersBag.toArray()));
}
public static int sumList(ListInterface<Integer> list) {
return 0;
}
public static int countPositives(BagInterface<Integer> bag) {
return 0;
}
}
Explanation / Answer
1.
void recMethod(int[] array, int a, int b){
if(b>a){
System.out.println(Arrays.toString(array));
array[b] = 2*array[b];
recMethod(array,a,b-1);
System.out.println(Arrays.toString(array));
}
else{
System.out.println("done");
}
}
let's trace the recursion
a b array
2 5 {12,5,6,2,3,4,7} Now, array[5] is doubled
2 4 {12,5,6,2,3,8,7} array[4] is doubled
2 3 {12,5,6,2,6,8,7} array[3] is doubled
2 2 b>a is false, "done" will be printed
---while tracking back----
2 3 {12,5,6,4,6,8,7}
2 4 {12,5,6,4,6,8,7}
2 5 {12,5,6,4,6,8,7}
2.
void recMethod(Node firstNode){
printNodes(firstNode);
if(firstNode.next!=null){
firstNode.data = 2*firstNode.data;
recMethod(firstNode.next)
}
else{
print("done")
}
printNodes(firstNode)
}
Given chain 4->6->5->3->2
node chain
4. 4->6->5->3->2 4 is doubled
6 8->6->5->3->2 6 is doubled
5 8->12->5->3->2 5 is doubled
3 8->12->10->3->2 3 is doubled
2 8->12->10->6->2
Next Node of 2 is null. So, 'done' is printed
while tracking back
2. 8->12->10->6->2
3 8->12->10->6->2
5 8->12->10->6->2
6 8->12->10->6->2
4 8->12->10->6->2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.