Traversals

Help Questions

AP Computer Science A › Traversals

Questions 1 - 10
1

Consider the code below:

public static class BTNode {

public static final int PARSE_IN = 1;

public static final int PARSE_PRE = 2;

public static final int PARSE_POST = 3;

String name;

BTNode lPointer,rPointer;

public BTNode(String s) {

name = s;

lPointer = rPointer = null;

}

public void insert(String s) {

insert(this,s);

}

private static void insert(BTNode node,String s) {

int comparison = s.compareTo(node.name);

if(comparison < 0) {

if(node.lPointer != null) {

insert(node.lPointer,s);

} else {

node.lPointer = new BTNode(s);

}

} else if(comparison > 0) {

if(node.rPointer != null) {

insert(node.rPointer,s);

} else {

node.rPointer = new BTNode(s);

}

}

}

public ArrayList parse(final int parseOrder) {

return parse(this,parseOrder);

}

private static ArrayList parse(BTNode node, final int parseOrder) {

ArrayList retVal = new ArrayList();

if(node == null) {

return(retVal);

}

ArrayList leftList = parse(node.lPointer,parseOrder);

ArrayList rightList = parse(node.rPointer,parseOrder);

if(parseOrder == PARSE_PRE) {

retVal.add(node.name);

retVal.addAll(leftList);

retVal.addAll(rightList);

} else if (parseOrder == PARSE_POST) {

retVal.addAll(leftList);

retVal.addAll(rightList);

retVal.add(node.name);

} else {

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

}

return retVal;

}

}

public static void main(String\[\] args) {

String\[\] names = {"Hervaeus","Peter Auriol","Guiral","Felix","Lila","Lola","Yippy","Yiiiipppy","Acton","Pierce","Betty"};

BTNode node = new BTNode(names\[0\]);

for(int i = 1; i < names.length; i++) {

node.insert(names\[i\]);

}

ArrayList traversedNames = node.parse(BTNode.PARSE_IN);

for(String s : traversedNames) {

System.out.println(s);

}

}

What is the output for this method?

Acton

Betty

Felix

Guiral

Hervaeus

Lila

Lola

Peter Auriol

Pierce

Yiiiipppy

Yippy

Acton

Betty

Felix

Guiral

Hervaeus

Lila

Lola

Peter Auriol

Pierce

Yiiiipppy

Yippy

There is an error in the recursion in BTNode.

There is an error in the recursion in BTNode.

Betty

Acton

Felix

Guiral

Lola

Lila

Pierce

Yiiiipppy

Yippy

Peter Auriol

Hervaeus

Betty

Acton

Felix

Guiral

Lola

Lila

Pierce

Yiiiipppy

Yippy

Peter Auriol

Hervaeus

Hervaeus

Guiral

Felix

Acton

Betty

Peter Auriol

Lila

Lola

Yippy

Yiiiipppy

Pierce

Hervaeus

Guiral

Felix

Acton

Betty

Peter Auriol

Lila

Lola

Yippy

Yiiiipppy

Pierce

Peter Auriol

Hervaeus

Guiral

Acton

Betty

Felix

Lila

Lola

Yippy

Pierce

Yiiiipppy

Peter Auriol

Hervaeus

Guiral

Acton

Betty

Felix

Lila

Lola

Yippy

Pierce

Yiiiipppy

Explanation

The code given is a standard implementation of a binary tree containing an insert and a parse method. For now, you can merely pay attention to your parse logic, particularly just the logic that will be invoked for the indicator value PARSE_IN. (Notice that this is merely in the else of the parse method. This is a "catch all" / default in case a bad value is given for the parse order.)

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

This is just the standard binary tree style of parsing based on our insert. The smaller items are on the left of the current node, and the larger ones are on the right of it. Thus, you have:

List of all smaller values + This current value + List of all larger values

Recursively, this will end with an ordered list, which is just what you need.

2

Consider the code below:

public static class BTNode {

public static final int PARSE_IN = 1;

public static final int PARSE_PRE = 2;

public static final int PARSE_POST = 3;

String name;

BTNode lPointer,rPointer;

public BTNode(String s) {

name = s;

lPointer = rPointer = null;

}

public void insert(String s) {

insert(this,s);

}

private static void insert(BTNode node,String s) {

int comparison = s.compareTo(node.name);

if(comparison < 0) {

if(node.lPointer != null) {

insert(node.lPointer,s);

} else {

node.lPointer = new BTNode(s);

}

} else if(comparison > 0) {

if(node.rPointer != null) {

insert(node.rPointer,s);

} else {

node.rPointer = new BTNode(s);

}

}

}

public ArrayList parse(final int parseOrder) {

return parse(this,parseOrder);

}

private static ArrayList parse(BTNode node, final int parseOrder) {

ArrayList retVal = new ArrayList();

if(node == null) {

return(retVal);

}

ArrayList leftList = parse(node.lPointer,parseOrder);

ArrayList rightList = parse(node.rPointer,parseOrder);

if(parseOrder == PARSE_PRE) {

retVal.add(node.name);

retVal.addAll(leftList);

retVal.addAll(rightList);

} else if (parseOrder == PARSE_POST) {

retVal.addAll(leftList);

retVal.addAll(rightList);

retVal.add(node.name);

} else {

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

}

return retVal;

}

}

public static void main(String\[\] args) {

String\[\] names = {"Hervaeus","Peter Auriol","Guiral","Felix","Lila","Lola","Yippy","Yiiiipppy","Acton","Pierce","Betty"};

BTNode node = new BTNode(names\[0\]);

for(int i = 1; i < names.length; i++) {

node.insert(names\[i\]);

}

ArrayList traversedNames = node.parse(BTNode.PARSE_IN);

for(String s : traversedNames) {

System.out.println(s);

}

}

What is the output for this method?

Acton

Betty

Felix

Guiral

Hervaeus

Lila

Lola

Peter Auriol

Pierce

Yiiiipppy

Yippy

There is an error in the recursion in BTNode.

Betty

Acton

Felix

Guiral

Lola

Lila

Pierce

Yiiiipppy

Yippy

Peter Auriol

Hervaeus

Hervaeus

Guiral

Felix

Acton

Betty

Peter Auriol

Lila

Lola

Yippy

Yiiiipppy

Pierce

Peter Auriol

Hervaeus

Guiral

Acton

Betty

Felix

Lila

Lola

Yippy

Pierce

Yiiiipppy

Explanation

The code given is a standard implementation of a binary tree containing an insert and a parse method. For now, you can merely pay attention to your parse logic, particularly just the logic that will be invoked for the indicator value PARSE_IN. (Notice that this is merely in the else of the parse method. This is a "catch all" / default in case a bad value is given for the parse order.)

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

This is just the standard binary tree style of parsing based on our insert. The smaller items are on the left of the current node, and the larger ones are on the right of it. Thus, you have:

List of all smaller values + This current value + List of all larger values

Recursively, this will end with an ordered list, which is just what you need.

3

Consider the code below:

public static class BTNode {

public static final int PARSE_IN = 1;

public static final int PARSE_PRE = 2;

public static final int PARSE_POST = 3;

String name;

BTNode lPointer,rPointer;

public BTNode(String s) {

name = s;

lPointer = rPointer = null;

}

public void insert(String s) {

insert(this,s);

}

private static void insert(BTNode node,String s) {

int comparison = s.compareTo(node.name);

if(comparison < 0) {

if(node.lPointer != null) {

insert(node.lPointer,s);

} else {

node.lPointer = new BTNode(s);

}

} else if(comparison > 0) {

if(node.rPointer != null) {

insert(node.rPointer,s);

} else {

node.rPointer = new BTNode(s);

}

}

}

public ArrayList parse(final int parseOrder) {

return parse(this,parseOrder);

}

private static ArrayList parse(BTNode node, final int parseOrder) {

ArrayList retVal = new ArrayList();

if(node == null) {

return(retVal);

}

ArrayList leftList = parse(node.lPointer,parseOrder);

ArrayList rightList = parse(node.rPointer,parseOrder);

if(parseOrder == PARSE_PRE) {

retVal.add(node.name);

retVal.addAll(leftList);

retVal.addAll(rightList);

} else if (parseOrder == PARSE_POST) {

retVal.addAll(leftList);

retVal.addAll(rightList);

retVal.add(node.name);

} else {

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

}

return retVal;

}

}

public static void main(String\[\] args) {

String\[\] names = {"Hervaeus","Peter Auriol","Guiral","Felix","Lila","Lola","Yippy","Yiiiipppy","Acton","Pierce","Betty"};

BTNode node = new BTNode(names\[0\]);

for(int i = 1; i < names.length; i++) {

node.insert(names\[i\]);

}

ArrayList traversedNames = node.parse(BTNode.PARSE_IN);

for(String s : traversedNames) {

System.out.println(s);

}

}

What is the output for this method?

Acton

Betty

Felix

Guiral

Hervaeus

Lila

Lola

Peter Auriol

Pierce

Yiiiipppy

Yippy

There is an error in the recursion in BTNode.

Betty

Acton

Felix

Guiral

Lola

Lila

Pierce

Yiiiipppy

Yippy

Peter Auriol

Hervaeus

Hervaeus

Guiral

Felix

Acton

Betty

Peter Auriol

Lila

Lola

Yippy

Yiiiipppy

Pierce

Peter Auriol

Hervaeus

Guiral

Acton

Betty

Felix

Lila

Lola

Yippy

Pierce

Yiiiipppy

Explanation

The code given is a standard implementation of a binary tree containing an insert and a parse method. For now, you can merely pay attention to your parse logic, particularly just the logic that will be invoked for the indicator value PARSE_IN. (Notice that this is merely in the else of the parse method. This is a "catch all" / default in case a bad value is given for the parse order.)

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

This is just the standard binary tree style of parsing based on our insert. The smaller items are on the left of the current node, and the larger ones are on the right of it. Thus, you have:

List of all smaller values + This current value + List of all larger values

Recursively, this will end with an ordered list, which is just what you need.

4

Consider the code below:

public static class BTNode {

public static final int PARSE_IN = 1;

public static final int PARSE_PRE = 2;

public static final int PARSE_POST = 3;

String name;

BTNode lPointer,rPointer;

public BTNode(String s) {

name = s;

lPointer = rPointer = null;

}

public void insert(String s) {

insert(this,s);

}

private static void insert(BTNode node,String s) {

int comparison = s.compareTo(node.name);

if(comparison < 0) {

if(node.lPointer != null) {

insert(node.lPointer,s);

} else {

node.lPointer = new BTNode(s);

}

} else if(comparison > 0) {

if(node.rPointer != null) {

insert(node.rPointer,s);

} else {

node.rPointer = new BTNode(s);

}

}

}

public ArrayList parse(final int parseOrder) {

return parse(this,parseOrder);

}

private static ArrayList parse(BTNode node, final int parseOrder) {

ArrayList retVal = new ArrayList();

if(node == null) {

return(retVal);

}

ArrayList leftList = parse(node.lPointer,parseOrder);

ArrayList rightList = parse(node.rPointer,parseOrder);

if(parseOrder == PARSE_PRE) {

retVal.add(node.name);

retVal.addAll(leftList);

retVal.addAll(rightList);

} else if (parseOrder == PARSE_POST) {

retVal.addAll(leftList);

retVal.addAll(rightList);

retVal.add(node.name);

} else {

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

}

return retVal;

}

}

public static void main(String\[\] args) {

String\[\] names = {"Hervaeus","Peter Auriol","Guiral","Felix","Lila","Lola","Yippy","Yiiiipppy","Acton","Pierce","Betty"};

BTNode node = new BTNode(names\[0\]);

for(int i = 1; i < names.length; i++) {

node.insert(names\[i\]);

}

ArrayList traversedNames = node.parse(BTNode.PARSE_IN);

for(String s : traversedNames) {

System.out.println(s);

}

}

What is the output for this method?

Acton

Betty

Felix

Guiral

Hervaeus

Lila

Lola

Peter Auriol

Pierce

Yiiiipppy

Yippy

There is an error in the recursion in BTNode.

Betty

Acton

Felix

Guiral

Lola

Lila

Pierce

Yiiiipppy

Yippy

Peter Auriol

Hervaeus

Hervaeus

Guiral

Felix

Acton

Betty

Peter Auriol

Lila

Lola

Yippy

Yiiiipppy

Pierce

Peter Auriol

Hervaeus

Guiral

Acton

Betty

Felix

Lila

Lola

Yippy

Pierce

Yiiiipppy

Explanation

The code given is a standard implementation of a binary tree containing an insert and a parse method. For now, you can merely pay attention to your parse logic, particularly just the logic that will be invoked for the indicator value PARSE_IN. (Notice that this is merely in the else of the parse method. This is a "catch all" / default in case a bad value is given for the parse order.)

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

This is just the standard binary tree style of parsing based on our insert. The smaller items are on the left of the current node, and the larger ones are on the right of it. Thus, you have:

List of all smaller values + This current value + List of all larger values

Recursively, this will end with an ordered list, which is just what you need.

5

Consider the code below:

public static class BTNode {

public static final int PARSE_IN = 1;

public static final int PARSE_PRE = 2;

public static final int PARSE_POST = 3;

String name;

BTNode lPointer,rPointer;

public BTNode(String s) {

name = s;

lPointer = rPointer = null;

}

public void insert(String s) {

insert(this,s);

}

private static void insert(BTNode node,String s) {

int comparison = s.compareTo(node.name);

if(comparison < 0) {

if(node.lPointer != null) {

insert(node.lPointer,s);

} else {

node.lPointer = new BTNode(s);

}

} else if(comparison > 0) {

if(node.rPointer != null) {

insert(node.rPointer,s);

} else {

node.rPointer = new BTNode(s);

}

}

}

public ArrayList parse(final int parseOrder) {

return parse(this,parseOrder);

}

private static ArrayList parse(BTNode node, final int parseOrder) {

ArrayList retVal = new ArrayList();

if(node == null) {

return(retVal);

}

ArrayList leftList = parse(node.lPointer,parseOrder);

ArrayList rightList = parse(node.rPointer,parseOrder);

if(parseOrder == PARSE_PRE) {

retVal.add(node.name);

retVal.addAll(leftList);

retVal.addAll(rightList);

} else if (parseOrder == PARSE_POST) {

retVal.addAll(leftList);

retVal.addAll(rightList);

retVal.add(node.name);

} else {

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

}

return retVal;

}

}

public static void main(String\[\] args) {

String\[\] names = {"Hervaeus","Peter Auriol","Guiral","Felix","Lila","Lola","Yippy","Yiiiipppy","Acton","Pierce","Betty"};

BTNode node = new BTNode(names\[0\]);

for(int i = 1; i < names.length; i++) {

node.insert(names\[i\]);

}

ArrayList traversedNames = node.parse(BTNode.PARSE_IN);

for(String s : traversedNames) {

System.out.println(s);

}

}

What is the output for this method?

Acton

Betty

Felix

Guiral

Hervaeus

Lila

Lola

Peter Auriol

Pierce

Yiiiipppy

Yippy

There is an error in the recursion in BTNode.

Betty

Acton

Felix

Guiral

Lola

Lila

Pierce

Yiiiipppy

Yippy

Peter Auriol

Hervaeus

Hervaeus

Guiral

Felix

Acton

Betty

Peter Auriol

Lila

Lola

Yippy

Yiiiipppy

Pierce

Peter Auriol

Hervaeus

Guiral

Acton

Betty

Felix

Lila

Lola

Yippy

Pierce

Yiiiipppy

Explanation

The code given is a standard implementation of a binary tree containing an insert and a parse method. For now, you can merely pay attention to your parse logic, particularly just the logic that will be invoked for the indicator value PARSE_IN. (Notice that this is merely in the else of the parse method. This is a "catch all" / default in case a bad value is given for the parse order.)

retVal.addAll(leftList);

retVal.add(node.name);

retVal.addAll(rightList);

This is just the standard binary tree style of parsing based on our insert. The smaller items are on the left of the current node, and the larger ones are on the right of it. Thus, you have:

List of all smaller values + This current value + List of all larger values

Recursively, this will end with an ordered list, which is just what you need.

6

Suppose you are given an array of integers:

int array\[\] = {1,2,3,4,5};

and the following method:

public static void printArray(int\[\] arr)

{

for (int a = 0; r < arr.length-1; a++)

{

if (a%2==0)

{

System.out.println(arr\[a\]);

}

}

}

After the method cacll printArray(array) is called, the output would be:

1

3

2

4

1

2

3

4

5

1

3

5

2 4 6

Explanation

The correct answer is:

1

3

The important line here is the if statement, which only executes if (a%2==0) is true, or if the loop counter divided by 2 is 0. A possible error is to divide each element of the array by 2 instead of the loop counter. So the println statement will only execute if the loop counter is even, which happens on the 1st itteration (a=0) and the 3rd itteration (a=2). The for loop ends at arr.length-1, which means that a takes on a maximum value of 3, and not 4 (choosing the option 1 3 5 would mean you did not notice the bounds on the for loop). Finally, println prints a new line every time, so, it is not possible for all the integers to be on one line, as println is executed twice.

7

Suppose you are given an array of integers:

int array\[\] = {1,2,3,4,5};

and the following method:

public static void printArray(int\[\] arr)

{

for (int a = 0; r < arr.length-1; a++)

{

if (a%2==0)

{

System.out.println(arr\[a\]);

}

}

}

After the method cacll printArray(array) is called, the output would be:

1

3

2

4

1

2

3

4

5

1

3

5

2 4 6

Explanation

The correct answer is:

1

3

The important line here is the if statement, which only executes if (a%2==0) is true, or if the loop counter divided by 2 is 0. A possible error is to divide each element of the array by 2 instead of the loop counter. So the println statement will only execute if the loop counter is even, which happens on the 1st itteration (a=0) and the 3rd itteration (a=2). The for loop ends at arr.length-1, which means that a takes on a maximum value of 3, and not 4 (choosing the option 1 3 5 would mean you did not notice the bounds on the for loop). Finally, println prints a new line every time, so, it is not possible for all the integers to be on one line, as println is executed twice.

8

Suppose you are given an array of integers:

int array\[\] = {1,2,3,4,5};

and the following method:

public static void printArray(int\[\] arr)

{

for (int a = 0; r < arr.length-1; a++)

{

if (a%2==0)

{

System.out.println(arr\[a\]);

}

}

}

After the method cacll printArray(array) is called, the output would be:

1

3

2

4

1

2

3

4

5

1

3

5

2 4 6

Explanation

The correct answer is:

1

3

The important line here is the if statement, which only executes if (a%2==0) is true, or if the loop counter divided by 2 is 0. A possible error is to divide each element of the array by 2 instead of the loop counter. So the println statement will only execute if the loop counter is even, which happens on the 1st itteration (a=0) and the 3rd itteration (a=2). The for loop ends at arr.length-1, which means that a takes on a maximum value of 3, and not 4 (choosing the option 1 3 5 would mean you did not notice the bounds on the for loop). Finally, println prints a new line every time, so, it is not possible for all the integers to be on one line, as println is executed twice.

9

What's the best way to traverse this list in Swift (iOS)?

var list: \[Int\] = \[0, 1, 2, 3, 4, 5\]

for i in list {

println(i)

}

for (var i = 0; i < list.count; i++) {

println(i)

}

var i = 0

for (i; i < list.count; i++) {

println(i)

}

for i in range(list.count) {

println(i)

}

Explanation

The correct answer is the best way because it uses Swift's built in "in" operator. In this case, "in" will convert the thing that comes after "in" (so in this case, list) into a range operator. Essentially it will say "i in range(list.count)." This is why the other answer choice that uses "in" is incorrect in terms of the "best" way to traverse a list of integers in Swift.

10

What's the best way to traverse this list in Swift (iOS)?

var list: \[Int\] = \[0, 1, 2, 3, 4, 5\]

for i in list {

println(i)

}

for (var i = 0; i < list.count; i++) {

println(i)

}

var i = 0

for (i; i < list.count; i++) {

println(i)

}

for i in range(list.count) {

println(i)

}

Explanation

The correct answer is the best way because it uses Swift's built in "in" operator. In this case, "in" will convert the thing that comes after "in" (so in this case, list) into a range operator. Essentially it will say "i in range(list.count)." This is why the other answer choice that uses "in" is incorrect in terms of the "best" way to traverse a list of integers in Swift.

Page 1 of 4
Return to subject