Question 1: Consider the code for the recursive function myPrint shown in this c
ID: 3828700 • Letter: Q
Question
Question 1:
Consider the code for the recursive function myPrint shown in this code snippet:
1. def myPrint(n) :
2. if n == 0 :
3. return 0
4. else :
5. return n + mysteryPrint(n - 1)
To avoid infinite recursion, which of the following lines of code should replace the current terminating case?
Question options:
if n == -1
if n <= 0
if n >= 0
The terminating case as shown will avoid infinite recursion
Question 2
Which problem is well suited to being solved with mutually recursive functions?
Question options:
Computing the factorial of a number
Determining if a string is a palindrome
Computing Fibonacci numbers
Evaluating a numeric expression
Question 3
Recall the backtracking strategy outlined in the textbook. A similar strategy can be used to solve Sudoku puzzles.
def solve(gameBoard) :
status = examine(gameBoard)
if status == CONTINUE :
for nextBoard in extend(gameBoard) :
solve(nextBoard)
elif status == ACCEPT:
____________________
What code should be placed in the blank to complete the solution to this problem?
Question options:
print(status)
print(gameBoard)
solve(gameBoard)
gameBoard = extend(gameBoard)
Question 4
Consider the following recursive code snippet:
1. def mystery(n, m) :
2. if n == 0 :
3. return 0
4. if n == 1 :
5. return m
6. return m + mystery(n - 1, m)
What value is returned from a call to mystery(1, 5)?
Question options:
1
5
6
11
Question 5
Consider the function powerOfTwo shown below:
1. def powerOfTwo(n) :
2. if n == 1 :
3. return True
4. elif n % 2 == 1 :
5. return False
6. else :
7. return powerOfTwo(n / 2)
How many recursive calls are made from the original call powerOfTwo(63) (not including the original call)?
Question options:
6
4
1
0
Question 6
Which statement(s) about recursion are true?
I. Recursion is faster than iteration
II. Recursion is often easier to understand than iteration
III. Recursive design has an economy of thought
Question options:
I
II
II and III
I and III
Question 7
Consider the following recursive function:
def myPrint(n) :
if n < 10 :
print(n)
else :
m = n % 10
print(m)
myPrint(n // 10)
What does this function do?
Question options:
It prints a positive value forward, digit by digit
It prints a positive value backward, digit by digit
It divides the number by 10 and prints out its last digit
It divides the number by 10 and prints out the result
Question 8
The following function is supposed to use recursion to compute the area of a square from the length of its sides. For example, squareArea(3) should return 9.
def squareArea(sideLength) :
if sideLength == 1 :
return 1
else :
____________________
What line of code should be placed in the blank to achieve this goal?
Question options:
return squareArea(sideLength - 1)
return 2 * squareArea(sideLength - 1)
return 2 * sideLength + squareArea(sideLength - 1)
return 2 * (sideLength - 1) + squareArea(sideLength - 1)
Question 9
Consider the following code snippet for calculating Fibonacci numbers recursively:
1. def fib(n) :
2. # assumes n >= 0
3. if n <= 1 :
4. return n
5. else :
6. return fib(n - 1) + fib(n - 2)
Identify the terminating condition in this recursive function.
Question options:
n < 1
n <= 1
fib(n - 1)
fib(n - 1) + fib(n - 1)
Question 10
Which statement about backtracking is correct?
Question options:
Backtracking starts from the end of the program and works backward to the beginning.
Backtracking builds up partial solutions that get increasingly closer to the goal.
Backtracking never abandons a partial solution.
Backtracking explores only one path toward a solution
Question 11
Consider the following code segment:
def triangleArea(sideLength) :
if sideLength == 1:
return 1
return triangleArea(sideLength - 1) + sideLength
print(triangleArea(5))
How many times is the triangleArea function called when this code segment executes?
Question options:
1
4
5
6
Question 12
Why does the best recursive function usually run slightly slower than its iterative counterpart?
Question options:
Testing the terminating condition takes longer.
Each recursive function call takes processor time.
Multiple recursive cases must be considered.
Checking multiple terminating conditions take more processor time.
Question 13
Consider the function powerOfTwo shown below:
1. def powerOfTwo(n) :
2. if n == 1 :
3. return True
4. elif n % 2 == 1 :
5. return False
6. else :
7. return powerOfTwo(n / 2)
How many recursive calls are made from the original call powerOfTwo(64) (not including the original call)?
Question options:
8
6
4
2
Question 14
Consider the code for mergeSort shown below, which works correctly:
def mergeSort(values) :
if len(values) <= 1 : return
mid = len(values) // 2
first = values[ : mid]
second = values[mid : ]
mergeSort(first)
mergeSort(second)
mergeLists(first, second, values)
What would happen if the line mid = len(values) // 2 was replaced with the line mid = len(values) // 4
Question options:
Merge sort would continue to work at the same speed as the original version
Merge sort would continue to work, but it would be slower than the original version
Merge sort would continue to work, and it would be faster than the original
The modified version would not sort the list successfully
Question 15
Consider the following function, which correctly merges two lists:
def mergeLists(first, second, values) :
iFrist = 0
iSecond = 0
j = 0
while iFirst < len(first) and iSecond < len(second) :
if first[iFirst] < second[iSecond] :
values[j] = first[iFirst]
iFirst = iFirst + 1
else :
values[j] = second[iSecond]
iSecond = iSecond + 1
j = j + 1
while iFrist < len(first) :
values[j] = first[iFirst]
iFirst = iFirst + 1
j = j + 1
while iSecond < len(second) :
values[j] = second[iSecond]
iSecond = iSecond + 1
j = j + 1
What is the big-Oh complexity of this algorithm, where n is the total number of elements in first and second?
Question options:
O(1)
O(log(n))
O(n)
O(n2)
Question 16
Consider the selection sort function and function call shown below:
def selectionSort(values) :
for i in range(len(values)) :
print(values)
minPos = minimumPosition(values, i)
swap(values, minPos, i)
data = [9, 1, 7, 2]
selectionSort(data)
print(data)
What is displayed when this code segment executes?
Question options:
[1, 2, 7, 9]
[9, 1, 7, 2]
[1, 9, 7, 2]
[1, 2, 7, 9]
[9, 1, 7, 2]
[1, 9, 7, 2]
[1, 2, 7, 9]
[1, 2, 7, 9]
[9, 1, 7, 2]
[1, 9, 7, 2]
[1, 2, 7, 9]
[1, 2, 7, 9]
[1, 2, 7, 9]
Question 17
How many comparisons does selection sort make when sorting a list of length n?
Question options:
n
log(2n)
n(n + 1) / 2
n / 2
Question 18
What is printed when the following code segment executes?
def mergeSort(values) :
if len(values) <= 1 : return
print(values)
mid = len(values) // 2
first = values[ : mid]
second = values[mid : ]
mergeSort(first)
mergeSort(second)
mergeLists(first, second, values)
# The implementation of mergeLists has been omitted.
# It can be found in the textbook.
data = [3, 1, 2, 4]
mergeSort(data)
Question options:
[1, 2, 3, 4]
[3, 1, 2, 4]
[1, 2]
[3, 4]
[3, 1, 2, 4]
[3 ,1]
[2, 4]
[3, 1, 2, 4]
[1, 2]
[3, 4]
[1, 2, 3, 4]
Question 19
In the textbook, we found that the number of element visits for merge sort totaled n + 5nlog2n. Which of the following is the appropriate big-Oh notation for merge sort?
Question options:
5nlog2n
n + log2
n + 5n
nlog2n
Question 20
Which sorting algorithm does the following code segment employ?
def mysterySort(values) :
if len(values) <= 1 :
return
first = values[ : mid]
second = values[mid : ]
mysterySort(first)
mysterySort(second)
mergeLists(first, second, values)
Question options:
Merge Sort
Quicksort
Selection Sort
Shell Sort
if n == -1
if n <= 0
if n >= 0
The terminating case as shown will avoid infinite recursion
Explanation / Answer
Hi, I have answered last 4 Questions with explanation.
Please repost others in separate post.
Q20)
Ans: Merge Sort
Q19)
Ans: 5nlog2n
Total : n + 5nlog2n, in Big-O notation, we neglect lower order term
Q18)
[3, 1, 2, 4]
[3 ,1]
[2, 4]
In merger sort : first partation: [3, 1] and [2, 4]
Q17)
Ans: n(n + 1) / 2
In each iteration we make : (n-i) comparisons, where i = 0, 2,1... n
So, = n + (n-1) + (n-2)+ ..+ 2+1
Q16)
[9, 1, 7, 2]
[1, 9, 7, 2]
[1, 2, 7, 9]
In each itertation, we are bringing smallest element at front
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.