Questions Chapter 6

Question 1

If the user enters 10 in the triangle.java program (Listing 6.1), what is the maximum number of “copies” of the triangle( ) method (actually just copies of its argument) that exist at any one time?

Answer 1

10

Question 2

Where are the copies of the argument in the triangle.java program stored?

a. in a variable in the triange( ) method
b. in a field of the TriangleApp class
c. in a variable of the getString( ) method
d. on a stack

Answer 2

d. on a stack.

Question 3

Assume the user enters10 in the triangle.java program. What is the value of n when the triangle ( ) method first returns a value other than 1?

Answer 3

2

Question 4

Assume the user enters 10 in the triangle. java program. What is the value of n when the triangle method is about to return to main( )?

Answer 4

10

Question 5

In the anagram.java program (Listing 6.2), at a certain depth of recursion, a version of the doAnagram( ) method is working with the string “led”. When this method calls a new version of itself, what letters will the new version be working with?

Answer 5

ed

Question 6

True or False: In the triangle ( ) method, the return values are store on the stack.

Answer 6

False

Question 7

We’ve seen that recursion can take the place of a loop, as in the loop-oriented orderedArray.java program (Listing 2.4) and the recursive binarySearch.java program (Listing 6.3). Which of the following is NOT true?

a. Both programs divide the range repeatedly in half
b. if the key is not found, the loop version returns because the range bounds cross, but the recursive version occurs because it reaches the bottom recursion level.
c. if the key is found, the loop version returns from the entire method, whereas the recursive version returns from only one level of recursion.
d. in the recursive version, the range to be searched must be specified in the arguments, while in the loop version it need not be.

Answer 7

b

Question 8

In the recFind( ) method in the binarySearch.java program (Listing 6.3), what takes the place of the loop in the non-recursive version?

a. the recFind( ) method
b. arguments to recFind( )
c. recursive calls to recFind( )
d. the call from main( ) to recFind( )

Answer 8

c. recursive calls to recFind( )

Question 9

The binarySearch.java program is an example of the _______________ approach to solving a problem.

Answer 9

divide and conquer approach

Question 10

What gets smaller as you make repeated recursive calls in the towers.java program (Listing 6.4)?

Answer 10

top

Question 11

What becomes smaller as you make repeated recursive calls in the recFind( ) method?

Answer 11

range to search

Question 12

The algorithm in the towers.java program involves:

a. “trees” that are data storage devices
b. secretly putting small disks under large disks
c. changing which columns are the source and destination
d. moving one small disk and then a stack of larger disks

Answer 12

c. changing which columns are the source and destination

Question 13

Which is NOT true about the merge( ) method in the merge.java program (Listing 6.5)?

a. its algorithm can handle arrays of different sizes
b. it must search the target array to find where to put the next item
c. it is not recursive
d. it continuously takes the smallest item irrespective of what array it’s in.

Answer 13

b. it must search the target array to find where to put the next item

Question 14

The disadvantage of mergesort is that:

a. it is not recursive
b. it uses more memory
c. although faster than the insertion sort, it is much slower than quicksort
d. it is complicated to implement

Answer 14

b. it uses more memory

Question 15

Besides a loop, a ________ can often be used instead of recursion.

Answer 15

stack

Question 16

A __________ method calls itself repeatedly, with different values each time

Answer 16

recursive

Question 17

Some value of its arguments causes a recursive method to return without calling itself. This is called the _______ ______.

Answer 17

base case

Question 18

A ____________ ________ is the sum of itself and all numbers smaller than itself.

Answer 18

triangular number

Question 19

The anagram of a word (all possible combinations of its n letters) can be found recursively by repeatedly ________ all its letters and anagramming the __________ of them.

Answer 19

repeatedly rotating all its letters, anagramming the rightmost n-1 of them.

Question 20

A ________ search can be carried out recursively by checking which half of a sorted range the search key is in, and then doing the same thing with that half.

Answer 20

binary search

Question 21

The __________ can be solved recursively by moving all but the ________ disk of a subtree to a(n) __________ tower, moving the ________ disk to the ________ tower, and finally moving the subtree to the _________.

Answer 21

The Towers of Hanoi puzzle can be solved recursively by moving all but the bottom disk of a subtree to an intermediate tower, moving the bottom disk to the destination tower, and finally moving the subtree to the destination.

Question 22

In _________, 1-element subarrays of a larger array are merged into 2-element subarrays, 2-element subarrays are merged into 4-element subarrays, and so on until the entire array is sorted

Answer 22

mergesort

Question 23

mergesort requires _______ time.

Answer 23

O(N*logN) time

Question 24

Any operation that can be carried out with recursion can be carried out with _________.

Answer 24

a stack.