Deck 5: Recursion

Question 1

Computer scientists in the field of artificial intelligence (AI) often use recursion to write programs that exhibit intelligent behavior.

Answer 1

True

Question 2

Whenever a method is called, Java pushes a new activation frame onto the run-time stack and saves this information on the stack.

Answer 2

True

Question 3

A characteristic of a recursive algorithm is that there must be at least one case (the base case), for a small value n, that can be solved directly.

Answer 3

True

Question 4

Linear search is an O(n²) algorithm.

Question 5

If it is easier to conceptualize an algorithm using recursion, then you should code it as a recursive method, because the advantage of readable code that is easy to debug outweighs the reduction in efficiency of recursion.

Question 6

The process of returning from the recursive calls and computing the partial results is called ____________________ the recursion.

Question 7

Java maintains a run-time stack, on which it saves new information in the form of a(n) ____________________.

Question 8

The exception ____________________ implies that the memory area used to store information about method calls has been used up.

Question 9

The purpose of a(n) ____________________ method is to call the recursive method and return its result.

Question 10

The simplest way to search an array is a(n) ____________________ search.

Question 11

Binary search can only be performed on an array that has been ___________________.

Question 12

An array of size 16 requires at most____________________ probes in the worst case of binary search.

Question 13

The Arrays.binarySearch method throws a(n) ____________________ if the target is not comparable to the array elements.

Question 14

Method ____________________ returns an integer whose value indicates the relative ordering of the two objects being compared.

Question 15

Classes that implement the Comparable interface must define a(n) ____________________ method that enables its objects to be compared in a standard way.

Question 16

Based on the algorithm below, which of the following steps is the recursive step?
1) if there is one figure in the nest
2) Do whatever is required to the figure.
3) Do whatever is required to the outer figure in the nest.
4) Process the nest of figures inside the outer figure in the same way.

A) Step 1
B) Step 2
C) Step 3
D) Step 4

Question 17

Which of the following is a recursive method?

A) public static int length(String str) {
if (str == null || str.equals(""))
return 0:
else
return 1 + length(str.substring(1));
}
B) public static int length(Strin str) {
if (str == null || str.equals(""))
return 0:
else
return 1;
}
C) public static int length(Strin str) {
if (str == null || str.equals(""))
return 0:
else
return 1 + len(str.substring(1));
}
D) public static int length(String str) {
if (str == null || str.equals(""))
return 0:
}

Question 18

A(n) ____ data structure is one that has another version of itself as a component.

A) linear
B) array
C) linked list
D) recursive

Question 19

____ is an approach to implementing systematic trial and error in a search for a solution.

A) Binary search
B) Backtracking
C) Recursion
D) Iteration

Question 20

In terms of efficiency, the following method is ____.
Public static int factorialIter(int n) {
Int result = 1;
For (int k = 1; k <= n; k++)
Result = result * k;
Return result;
}

A) O(n²)
B) O(1)
C) O(n)
D) O(log₂n)

Question 21

Which of the following methods calculates the nth Fibonacci number?

A) public static int method1(int n) {
if (n <= 2)
return 1;
else
return A(n - 1);
}
B) public static int method1(String str) {
if(str == null || str.equals(""))
return 0;
else
return 1 + method1(str.substring());
}
C) private static int method1(int Current, int Previous, int n) {
if (n == 1)
return Current;
else
return method1(Current + Previous, Current, n - 1);
}
D) public void method1(Object data) {
if (head == null)
head = new Node(data);
else
method1(head, data);
}

Question 22

The first language developed for artificial intelligence research was a recursive language called ____.

A) C++
B) Java
C) Pascal
D) LISP

Question 23

Complete the following algorithm:
If n equals 0
N! is 1.
Else
N! = _____.

A) n*(n-1)
B) n*(n+1)
C) (n-1)!
D) n*(n-1)!

Question 24

Complete the following algorithm for calculating gcd(m,n) for m>n.
If n is a divisor or m
The result is n.
Else
The result is gcd(____).

A) m % n
B) n
C) n, m % n
D) n, m / n

Question 25

In a(n) ____ search, we examine one array element at a time, starting with the first element or the last element, to see whether it matches the target.

A) recursive
B) binary
C) iterative
D) linear