Font size
WorksheetsCSC 1351 Test 3
Total questions: 84
Worksheet time: 21hrs 0mins
What is a recursive method?
A method that can call itself with simpler values. It must handle the simplest values without calling itself.
A method that can call itself with complex values. It must handle the most complex values without calling itself.
A method that can't call itself with simpler values. It must handle the simplest values without calling itself.
A method that can't call itself with complex values. It must handle the most complex values without calling itself.
What is a breakpoint?
A point in a program, specified in a debugger, at which the debugger stops executing the program and lets the user inspect the program state.
A point in a program, specified in a debugger, at which the debugger starts the program and lets the user inspect the program state.
A point in a program, specified in a debugger, at which the debugger stops executing the program but doesn't lets the user inspect the program state.
A point in a program, specified in a debugger, at which the debugger starts the program and doesn't lets the user inspect the program state.
What is a call stack?
The ordered set of all methods that currently have been called but not yet terminated, starting with the current method and ending with main.
The ordered set of some methods that currently have been called and terminated, starting with the current method and not ending with main.
The ordered set of no methods that currently have been called and terminated, starting with the current method and ending with main.
What is overloading?
Giving more than one meaning to a method name.
Giving one meaning to a method name.
Giving no meaning to a method name.
What is selection sort?
A sorting algorithm in which the smallest element is repeatedly found and removed until no elements remain.
A sorting algorithm in which the largest element is repeatedly found and removed until no elements remain.
A sorting algorithm in which the largest element is repeatedly found and removed until the smallest element remains.
A sorting algorithm in which the smallest element is repeatedly found and removed until the largest element remains.
What is the big-Oh notation?
The notation g(n) = O(f(n)), which denotes that the function g grows at a rate that is bounded by the growth rate of the function f with respect to n. For example, 10n2 + 100n - 1000 = O(n2).
The notation g(n) = O(f(n)), which denotes that the function g grows at a rate that is unbounded by the growth rate of the function f with respect to n. For example, 10n2 + 100n - 1000 = O(n2).
What is a merge sort?
A sorting algorithm that first sorts two halves of a data structure and then merges the sorted subarrays together.
A sorting algorithm that first sorts two halves of a data structure and then sorts subarrays.
A sorting algorithm that merges the sorted subarrays together and then sorts two halves of a data structure.
What is a linear search (sequential search)?
Searching a container (such as an array or list) for an object by inspecting each element in turn.
Searching a container (such as an array or list) for an object by inspecting all elements together.
Searching a container (such as an array or list) for an object but not inspecting each element in turn.
What is a binary search?
A fast algorithm for finding a value in a sorted array. It narrows the search down to half of the array in every step.
A slow algorithm for finding a value in a sorted array. It narrows the search down to half of the array in every step.
A slow algorithm for finding a value in a sorted array. It widens the search of the array in every step.
What is a collection?
A data structure that provides a mechanism for adding, removing, and locating elements.
A data structure that provides a mechanism for locating and removing elements.
A data structure that provides a mechanism for adding and removing elements.
What is a linked list?
A data structure that can hold an arbitrary number of objects, each of which is stored in a link object, which contains a pointer to the next link.
A data structure that can hold any number, each of which is stored in a link object, but doesn't contain a pointer to the next link.
A data structure that can't hold an arbitrary number of objects, each of which is stored in a link object, which contains a pointer to the next link.
What is a generic class?
A class with one or more type parameters.
A class with only one type parameters.
A class with many type parameters.
A class with no type parameters.
What is an iterator?
An object that can inspect all elements in a container such as a linked list.
An object that can't inspect any elements in a container such as a linked list.
An object that can inspect some elements in a container such as a linked list.
An object that can inspect one element in a container such as a linked list.
What is a doubly-linked list?
A linked list in which each link has a reference to both its predecessor and successor links.
A linked list in which each link doesn't have a reference to its predecessor or successor links.
A linked list in which each link has a reference to its predecessor but not its successor links.
A linked list in which each link has a reference to its successor links but not its predecessor links.
What is a stack?
A data structure with “last-in, first-out” retrieval. Elements can be added and removed only at one position, called the top of the stack.
A data structure with “last-in, first-out” retrieval. Elements can neither be added nor removed only at one position, called the top of the stack.
A data structure with “last-in, first-out” retrieval. Elements can only be added but not removed only at one position, called the top of the stack.
A data structure with “last-in, first-out” retrieval. Elements can only be removed but not added only at one position, called the top of the stack.
What is a run-time stack?
The data structure that stores the local variables of all called methods as a program runs.
The data structure that stores the local variables of some called methods as a program runs.
The data structure that stores the local variables of one called method as a program runs.
The data structure that stores the local variables of none of the called methods as a program runs.
What is a queue?
A collection of items with “first in, first out” retrieval.
A collection of items with “last in, first out” retrieval.
A collection of items with “last in, last out” retrieval.
A collection of items with “first in, last out” retrieval.
What is required to make a recursive method successful?
I special cases that handle the simplest computations directly
II a recursive call to simplify the computation
III a mutual recursion
I, II, and III
II only
I only
I and II only
Consider the getArea method from the textbook shown below.
Where is/are the recursive call(s)?
. lines #1 and #2
line #4
line #1
line #2
Consider the getArea method from the textbook shown below.
Where is/are the terminating condition(s)?
line #2
line #4
line #1
lines #1 and #2
Consider the getArea method from the textbook shown below:
Assume the code in line #3 is changed to:
Triangle smallerTriangle = new Triangle(width);
This change would cause infinite recursion for which triangles?
Those with width equal to 0
Triangles of any width.
Those with width equal to 1.
Those with width greater than or equal to 2.
Consider the getArea method from the book shown below.
Assume lines #1 and #2 were replaced with this:
if (width == 1) { return 1; } // replacement for lines #1 and #2
What will happen when this code is executed?
Nothing - the method would still be correct.
We would lose our only recursive case.
A positive width would reduce the correct area by 1.
A negative or zero width would cause problems.
Consider the getArea method from the textbook shown below.
Assume line #1 is replaced with this line:
if (width <= 0) {return width;}
What will be the result?
The method will return incorrect results for triangles with width equal to 0.
The method will return incorrect results for triangles with width equal to 1.
The method will return area to be one too high for all triangles.
The method will still return correct results for all non-negative width triangles.
Consider the following code snippet for recursive addition:
Identify the terminating condition in this recursive method.
there is no terminating condition
i == 0
return j
return add(i - 1, j + 1)
Consider the following code snippet for calculating Fibonacci numbers recursively:
Identify the terminating condition in this recursive method.
n < 1
n <= 1
fib(n - 1)
fib(n - 1) + fib(n - 1)
Consider the following recursive code snippet:
Identify the terminating condition(s) of method mystery?
n <= 0
n > 0
n == 1
n <= 0 or n == 1
Consider the following recursive code snippet:
What value is returned from a call to mystery(1,5)?
1
11
5
6
Consider the following recursive code snippet:
What value is returned from a call to mystery(3,6)?
18
3
6
729
Consider the recursive method myPrint:
What is printed for the call myPrint(8)?
4
21
10
8
Consider the recursive method myPrint in this code snippet:
What is printed for the call myPrint(821)?
821
12
10
128
Consider the recursive method myPrint shown in this code snippet:
What does this method do?
Prints a positive int value forward, digit by digit.
Divides the int by 10 and prints out the result.
Divides the int by 10 and prints out its last digit.
Prints a positive int value backward, digit by digit.
Complete the code for the recursive method printSum shown in this code snippet, which is intended to return the sum of digits from 1 to n:
return (n + printSum(n - 1));
return (n - printSum(n - 1));
return (n + printSum(n + 1));
return (printSum(n - 1));
Consider the code for the recursive method mystery shown in this code snippet:
What will be printed by the statement System.out.println(mystery(-4));?
Nothing - a StackoverflowError exception will occur
0
-22
-10
Consider the code for the recursive method riddle shown in this code snippet:
To avoid infinite recursion, which of the following lines of code should replace the current terminating case?
if (n <= 0)
if (n == -1)
if (n >= 0)
The terminating case as shown will avoid infinite recursion.
Insert the missing code in the following code fragment. This fragment is intended to recursively compute xn, where x and n are both non-negative integers:
return power(x, n - 1);
return x;
return 1;
return x * power(x, n - 1);
A recursive method without a special terminating case would _________
be more efficient.
never terminate.
end immediately.
not be recursive.
Consider the following recursive code snippet:
What parameter values for n would cause an infinite recursion problem in the following method?
all n with n < 0
n == 0
all n with n >= 0
n == 1
____ recursion can occur when a recursive algorithm does not contain a special case to handle the simplest computations directly.
Non-mutual
Terminating condition
Mutual
Infinite
If a recursive method does not simplify the computation within the method and the base case is not called, what will be the result?
The recursion calculation will occur correctly regardless.
Infinite recursion will occur.
This cannot be determined.
The terminating condition will be executed and recursion will end.
When a recursive method is called correctly, and it does not perform recursion, what must be true?
Both a terminating condition and a recursive case condition were true.
A terminating condition was true.
All recursive case conditions were true.
One recursive case condition was true.
Consider the getArea method from the textbook shown below:
Assume that line #3 is changed to this:
Triangle smallerTriangle = new Triangle(width);
This would cause infinite recursion for ____.
triangles with width equal to 1
triangles with width equal to 0
triangles with width greater than or equal to 2
triangles of any width
Consider the getArea method from the textbook shown below:
If line #1 was eliminated from the method, what would be the result when calling getArea?
A positive width would reduce the correct area by 1.
We would lose our only recursive case.
Nothing - the method would still work correctly.
A negative or zero width would cause problems.
How many recursive calls to the fib method shown below would be made from an original call to fib(4)? (Do not count the original call)
8
4
1
2
Would switching the special case order affect the return value of the following method?
An exception will be thrown.
Yes
No
It is impossible to tell.
Which of the following options could be used as a terminating condition for a recursive method that finds the middle character of a String with any number of characters?
I the length of the String is 1
II first and last String characters match
III the String is not empty
I only
I and III only
I, II and III
II only
Consider the problem of arranging matchsticks so as to form a row of squares, as shown below for three squares and ten matchsticks.
_ _ _
|_|_|_|
Complete the recursive method below, which is designed to return the number of matchsticks needed to form n squares.
4 * squares;
3 + matchsticks(squares - 1);
4 + matchsticks(squares - 1);
matchsticks(squares + 4);
Consider the method below, which implements the exponentiation operation recursively. Select the statement that should be used to complete the method so that it handles the special case correctly.
return 0;
return 1 * power(base, exponent - 1);
return base;
return 1;
Consider the method below, which displays the characters from a String in reverse order. Each character appears on a separate line. Select the statement that should be used to complete the method so that it performs a recursive method call correctly.
printReverse(word.length() - 1);
printReverse(word.substring(1));
printReverse(word);
printReverse(new String(word.charAt(1)));
Consider the method below, which prints the digits of an arbitrary positive integer in reverse order, one digit per line. The method should print the last digit first. Then, it should recursively print the integer obtained by removing the last digit. Select the statements that should be used to complete the method.
System.out.println(value / 10); printReverse(value / 10);
System.out.println(value / 10); printReverse(value % 10);
System.out.println(value % 10); printReverse(value / 10);
System.out.println(value % 10); printReverse(value % 10);
Consider the method powerOfTwo shown below:
What is the best interpretation of line #1?
1 is an invalid choice for n
Any multiple of one is a power of two
One is not a power of two
One is a power of two
Consider the method powerOfTwo shown below:
How many recursive calls are made from the original call of powerOfTwo(64) (not including the original call)?
6
4
8
2
Complete the code for the myFactorial recursive method shown below, which is intended to compute the factorial of the value passed to the method:
if (anInteger * (anInteger - 1) == 1)
if (anInteger == 1)
if (myFactorial(anInteger) == 1)
if ((anInteger - 1) == 1)
Complete the code for the recursive method shown below, which is intended to compute the sum of the first n positive integers:
return n + s(n - 1);
return s(n) + n - 1;
return n + (n - 1);
return n + s(n + 1);
Complete the code for the calcPower recursive method shown below, which is intended to raise the base number passed into the method to the exponent power passed into the method:
if (exponent == -1)
if (exponent == 1)
if (exponent != 1)
if (exponent == 0)
Given the following class code:
What values will be printed?
1, 3, and 6
3, 6, 9, and 12
1, 3, 6, and 9
3, 6, and 9
Given the following class code:
What values will be printed when this code is executed?
4
8
0, 4, and 8
4 and 8
Given the following code snippet:
What value will be returned when this code is executed with a call to newCalc(15)?
2
6.5
2.5
6
Given the following class code:
What values will be printed when this code is executed?
8
4
4 and 8
0, 4, and 8
Complete the following code snippet, which is intended to be a recursive method that will find the smallest value in an array of double values from index to the end of the array:
minVal(elements, index - 1)
minVal(index - 1)
minVal(elements, index + 1)
minVal(index + 1)
Complete the following code snippet, which is intended to be a recursive method that will find the sum of all elements in an array of double values from the beginning of the array to index:
Assume that this method would be called using an existing array named myArray as follows:
findSum(myArray, myArray.length - 1);
return (arr[index] + findSum(arr, index + 1));
return (findSum(arr, index - 1));
return (findSum(arr, index + 1));
return (arr[index] + findSum(arr, index - 1));
Complete the following code snippet, which is intended to be a recursive method that reverses a String value:
return s.charAt(0);
return 0;
return s.substring(1);
return s;
Consider the code for the recursive method printSum shown in this code snippet, which is intended to return the sum of digits from 1 to n:
Which of the following statements is correct?
line #3 is incorrect, and should be changed to return (n + printSum(n + 1));
line #1 is incorrect, and should be changed to if (n <= 1)
line #3 is incorrect, and should be changed to return (n + printSum(n - 1));
line #3 is incorrect, and should be changed to return (printSum(n - 1));
What type of algorithm places elements in order?
deletion
searching
sorting
insertion
In each iteration, selection sort places which element in the correct location?
The smallest in the array.
The largest element in the array.
A random element.
The smallest element not yet placed in prior iterations.
Consider the sort method shown below for selection sort:
Suppose we modify the loop condition to read i < a.length. What would be the result?
The sort would work exactly the same as before the code modification.
The sort would work, but run one more iteration.
The sort would work but with one less iteration.
An exception would occur.
Consider the sort method shown below for selection sort:
Suppose we modify the call to the swap method call to read swap(i, minPos). What would be the result?
An exception would occur.
The sort would produce incorrect results.
The sort would produce correct results
The sort would work, but sort backwards.
Consider the sort method for selection sort shown below:
Suppose we modify the loop control to read int i = 1; i < a.length – 1; i++. What would be the result?
The sort would still work correctly.
The sort would not consider the first array element.
An exception would occur.
The sort would not consider the last array element.
Which of the following completes the selection sort method minimumPosition()?
if (a[i] > a[minPos]) { minPos = i; }
if (a[i] < a[j]) { minPos = i; }
if (a[i] < a[minPos]) { minPos = i; }
if (a[i] < a[minPos]) { i = minPos; }
Consider the minimumPosition method from the SelectionSorter class. Complete the code to write a maximumPosition method that returns the index of the largest element in the range from index from to the end of the array.
if(a[i] == a[maxPos]) { maxPos = i; }
if(a[i] <= a[maxPos]) { maxPos = i; }
if(a[i] > a[maxPos]) { maxPos = i; }
if(a[i] < a[maxPos]) { maxPos = i; }
Consider the swap method shown below from the SelectionSorter class. If we modified it as shown in the swap2 method shown below, what would be the effect on the sort method?
Some array elements would be overwritten.
It would sort the array in reverse order.
It would still be correct, but run a little faster.
There would be no effect.
After 9 iterations of selection sort working on an array of 10 elements, what must hold true?
The largest element is correctly placed by default.
The largest element is incorrectly placed.
One more iteration is needed to complete the sort.
The smallest element is incorrectly placed.
.The largestPosition method below returns the index of the largest element in the tail range of an array of integers. Select the expression that would be needed to complete the selectionSort method below, so that it sorts the elements in descending order.
. (int i = 0; i < a.length – 1; i++)
(int i = a.length – 1; i > 0; i--)
(int i = a.length; i > 0; i--)
(int i = 0; i < a.length; i++)
Which sort algorithm starts by cutting the array in half and then recursively sorts each half?
insertion sort
quicksort
merge sort
selection sort
How many times can an array with 4,096 elements be cut into two equal pieces?
10
8
16
12
The merge sort algorithm presented in section 14.4, which sorts an array of integers in ascending order, uses the merge method which is partially shown below. Select the condition that would be needed to complete the method so that the elements are sorted in descending order.
first[iFirst] > second[iSecond]
first[iFirst] < second[iSecond]
iFirst > iSecond
iFirst < iSecond
The following code is an example of a ___ search.
binary
sorted
linear
random
Another name for linear search is ____ search.
random
sequential
sorted
binary
Given an ordered array with 15 elements, how many elements must be visited in the worst case of binary search?
2
8
4
3
Given an ordered array with 31 elements, how many elements must be visited in the worst case of binary search?
16
8
5
4
A binary search is generally ____ a linear search.
faster than
less efficient than
slower than
equal to
A search technique where, in each step, you split the size of the search in half is called a____ search.
random
merging
linear
binary
Can you search the following array using binary search?
int[] A = {6, 5, 4, 2, 0, 1, -1, -17};
No, negative numbers are not allowed because they indicate that a value is not present.
Yes. Binary search can be applied to any array.
No. Binary search can be applied to a sorted array only.
Yes, but the algorithm runs slower because the array is in descending order.
. The partial linear search method below is designed to search an array of String objects. Select the expression that would be needed to complete the method.
a[i] == item
a[i].compareTo(item)
a[i].equals(item)
a[i].indexOf(item)
The partial binary search method below is designed to search an array of String objects sorted in ascending order. Select the expression that would be needed to complete the method.
a[low].compareTo(item)
item.compareTo(a[mid])
item.equals(a[mid])
a[mid].compareTo(item)
