C949 TEST
True - answerdef find(lst, item, low, high, indent):
"""
Finds index of string in list of strings, else -1.
Searches only the index range low to high
Note: Upper/Lower case characters matter
"""
print(indent, 'find() range', low, high)
range_size = (high - low) + 1
mid = (high + low) // 2
if item == lst[mid]: # Base case 1: Found at mid
print(indent, 'Found person.')
pos = mid
elif range_size == 1: # Base case 2: Not found
print(indent, 'Person not found.')
pos = 0
else: # Recursive search: Search lower or upper half
if item < lst[mid]: # Search lower half
print(indent, 'Searching lower half.')
pos = find(lst, item, low, mid, indent + ' ')
else: # Search upper half
print(indent, 'Searching upper half.')
pos = find(lst, item, mid+1, high, indent + ' ')
print(indent, 'Returning pos = %d.' % pos)
return pos
attendees = []
attendees.append('Adams, Mary')
attendees.append('Carver, Michael')
attendees.append('Domer, Hugo')
attendees.append('Fredericks, Carlo')
attendees.append('Li, Jie')
name = input("Enter person's name: Last, First: ")
pos = find(attendees, name, 0, len(attendees)-1, ' ')
if pos >= 0:
print('Found at position %d.' % pos)
else:
print( 'Not found.')
The above debug approach requires an extra parameter to be passed to indicate the
amount of indentation.
,True - answerdef find(lst, item, low, high, indent):
"""
Finds index of string in list of strings, else -1.
Searches only the index range low to high
Note: Upper/Lower case characters matter
"""
print(indent, 'find() range', low, high)
range_size = (high - low) + 1
mid = (high + low) // 2
if item == lst[mid]: # Base case 1: Found at mid
print(indent, 'Found person.')
pos = mid
elif range_size == 1: # Base case 2: Not found
print(indent, 'Person not found.')
pos = 0
else: # Recursive search: Search lower or upper half
if item < lst[mid]: # Search lower half
print(indent, 'Searching lower half.')
pos = find(lst, item, low, mid, indent + ' ')
else: # Search upper half
print(indent, 'Searching upper half.')
pos = find(lst, item, mid+1, high, indent + ' ')
print(indent, 'Returning pos = %d.' % pos)
return pos
attendees = []
attendees.append('Adams, Mary')
attendees.append('Carver, Michael')
attendees.append('Domer, Hugo')
attendees.append('Fredericks, Carlo')
attendees.append('Li, Jie')
name = input("Enter person's name: Last, First: ")
pos = find(attendees, name, 0, len(attendees)-1, ' ')
if pos >= 0:
print('Found at position %d.' % pos)
else:
print( 'Not found.')
Each recursive call should add a few spaces to the indent parameter.
False - answerdef find(lst, item, low, high, indent):
"""
Finds index of string in list of strings, else -1.
Searches only the index range low to high
Note: Upper/Lower case characters matter
"""
print(indent, 'find() range', low, high)
,range_size = (high - low) + 1
mid = (high + low) // 2
if item == lst[mid]: # Base case 1: Found at mid
print(indent, 'Found person.')
pos = mid
elif range_size == 1: # Base case 2: Not found
print(indent, 'Person not found.')
pos = 0
else: # Recursive search: Search lower or upper half
if item < lst[mid]: # Search lower half
print(indent, 'Searching lower half.')
pos = find(lst, item, low, mid, indent + ' ')
else: # Search upper half
print(indent, 'Searching upper half.')
pos = find(lst, item, mid+1, high, indent + ' ')
print(indent, 'Returning pos = %d.' % pos)
return pos
attendees = []
attendees.append('Adams, Mary')
attendees.append('Carver, Michael')
attendees.append('Domer, Hugo')
attendees.append('Fredericks, Carlo')
attendees.append('Li, Jie')
name = input("Enter person's name: Last, First: ")
pos = find(attendees, name, 0, len(attendees)-1, ' ')
if pos >= 0:
print('Found at position %d.' % pos)
else:
print( 'Not found.')
The function should remove a few spaces from the indent parameter before returning.
True - answerA recursive function with parameter n counts up from any negative
number to 0. An appropriate base case would be n == 0.
True - answerA recursive function can have two base cases, such as n == 0 returning 0,
and n == 1, returning 1.
False - answern factorial (n!) is commonly implemented as a recursive function due to
being easier to understand and executing faster than a loop implementation.
True - answerIn the code below, suppose str1 is a pointer or reference to a string. The
code only executes in constant time if the assignment copies the pointer/reference, and
not all the characters in the string.
srt2 = str1
, True - answerCertain hardware may execute division more slowly than multiplication,
but both may still be constant time operations.
False - answerThe hardware running the code is the only thing that affects what is and
what is not a constant time operation.
True - answerComputational complexity analysis allows the efficiency of algorithms to
be compared.
False - answerTwo different algorithms that produce the same result have the same
computational complexity.
False - answerRuntime and memory usage are the only two resources making up
computational complexity.
False - answerNearly every algorithm has a best-case time complexity when N = 0.
False - answerAn algorithm's best and worst case scenarios are always different.
listSize - answerGetEvent(list, listSize) {
i=0
evensList = Create new, empty list
while (i < listSize) {
if (list[i] % 2 == 0)
Add list[i] to evensList
i=i+1
}
return evensList
}
What is the maximum possible size of the returned list?
0 - answerGetEvent(list, listSize) {
i=0
evensList = Create new, empty list
while (i < listSize) {
if (list[i] % 2 == 0)
Add list[i] to evensList
i=i+1
}
return evensList
}
What is the minimum possible size of the returned list?
S(N) = N + k - answerGetEvent(list, listSize) {