A binary search ____ a linear search. Question options: can\'t be compared to ge
ID: 3828418 • Letter: A
Question
A binary search ____ a linear search.
Question options:
can't be compared to
generally has a similar running time to
is generally faster than
is generally slower than
Question 3
0 / 1 point
Which sorting algorithm has better than O(n2) behavior, even in the worst case?
Question options:
Insertion sort
Merge sort
Quicksort
Selection sort
Question 4
0 / 1 point
Consider the selection sort function shown below:
def selectionSort(values) :
for i in range(len(values)) :
minPos = minimumPosition(values, i)
swap(values, minPos, i)
The function works correctly in its current form. What would happen if the line calling swap was replaced with: swap(values, i, minPos)?
Question options:
The list would still be sorted, but it would take one less iteration
The list would still be sorted, using the same number of iterations
The list would still be sorted, but it would take one more iteration
A runtime error would occur
Question 5
0 / 1 point
Consider the following function for performing a binary search:
def binarySearch(values, low, high, target) :
if low <= high :
mid = (low + high) // 2
if values[mid] == target :
return mid
elif values[mid] < target :
return binarySearch(values, mid + 1, high, target)
else :
return binarySearch(values, low, mid - 1, target)
else :
return -1
How many elements will be visited when values is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], low is 0, high is 9, and target is 2?
Question options:
1
3
5
10
Question 6
0 / 1 point
In the textbook, we found that the number of element visits for merge sort totaled n + 5nlog2n. Lets consider sorting 1024 elements. How many visits are needed?
Question options:
1,024
6,144
51,200
52,224
Question 7
0 / 1 point
Binary search is an ____ algorithm.
Question options:
O(n)
O(n2)
O(log n)
O(n log n)
Question 8
0 / 1 point
Consider the following function for performing a linear search:
def linearSearch(values, target) :
for i in range(len(values)) :
if values[i] == target :
return i
return -1
How many elements will be visited when values is [1, 5, 7, 6, 2, 4, 9, 3, 8, 0] and target is 2?
Question options:
0
2
5
10
Question 10
0 / 1 point
How many times can an list with 729 elements be cut into three equal pieces?
Question options:
4
5
6
7
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 2
0 / 1 point
In big-Oh notation, when we consider the order of the number of visits an algorithm makes, what do we ignore?
I. Power of two terms
II. The coefficients of the terms
III. All lower order terms
Question options:
I only
II only
I and II only
II and III only
Question 3
0 / 1 point
Consider the following variation of the selection sort algorithm:
def sort(values) :
for i in range(len(values)) :
maxPos = i
for j in range(i + 1, len(values)) :
if values[j] > values[maxPos] :
maxPos = j
temp = values[maxPos]
values[maxPos] = values[i]
values[i] = values[maxPos]
If this algorithm takes 5 seconds to sort 15,000 elements, how long would you expect it to take to sort 30,000 elements?
Question options:
5 seconds
10 seconds
25 seconds
50 seconds
Question 6
0 / 1 point
The checklist function is shown below:
def checklist(lst) :
if(lst[0] >= lst[len(lst)-1] :
return True
return False
What can you conclude about the running time of this function?
Question options:
Its running time will be O(n).
Its running time will be O(n2).
Its running time will be O(log n).
Its running time will be O(1).
Question 8
0 / 1 point
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 9
0 / 1 point
The following program is supposed to time the performance of the selectionSort function. Right now it is missing the code, startTime = time(), which records the starting time. Where should the missing code be inserted?
# Line 1
values = []
# Line 2
for i in range(10000) :
values.append(randint(1, 100))
# Line 3
selectionSort(values)
# Line 4
endTime = time()
Question options:
Line 1
Line 2
Line 3
Line 4
Question 10
0 / 1 point
Selection sort has O(n2) complexity. If a computer can sort 1,000 elements in 4 seconds, approximately how many seconds will it take the computer to sort 1,000 times that many, or 1,000,000 elements?
Question options:
16
1,000
1,000,000
4,000,000
An algorithm that cuts the work in half in each step is an ____ algorithm.
Question options:
O(n)
O(n2)
O(log n)
O(n log n)
Question 4
0 / 1 point
Consider the following function for performing a binary search:
def binarySearch(values, low, high, target) :
if low <= high :
mid = (low + high) // 2
if values[mid] == target :
return mid
elif values[mid] < target :
return binarySearch(values, mid + 1, high, target)
else :
return binarySearch(values, low, mid - 1, target)
else :
return -1
How many elements will be visited when values is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], low is 0, high is 9, and target is 10?
Question options:
0
2
4
10
Question 5
0 / 1 point
Suppose you have a phone number and need to find the address that it corresponds to. If there are 2,000,000 entries, how many do you expect to search in a printed phone directory before finding the address you are looking for?
Question options:
Approximately 50,000 records
Approximately 75,000 records
Approximately 1,000,000 records
Approximately 1,200,000 records
Question 6
0 / 1 point
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 = [1, 2, 3]
selectionSort(data)
print(data)
What is displayed when this code segment executes?
Question options:
[]
[1, 2, 3]
[3, 2, 1]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]
Question 9
0 / 1 point
Which of the following statements about running times of algorithms is correct?
Question options:
An algorithm that is O(1) means that only one comparison takes place.
When determining the running time, constants are not taken into consideration.
When determining the running time, lower-order terms must be taken into consideration.
An algorithm that is O(n) means that the number of comparisons does not grow as the size of the list increases.
can't be compared to
generally has a similar running time to
is generally faster than
is generally slower than
Question 3
0 / 1 point
Explanation / Answer
As per the chegg rules i cannot answer all. I have answered as many as i can.
Answer
1) is generally faster than
2) Merge sort
3) The list would still be sorted, using the same number of iterations
4) 3
5)
6) O(log n)
7) 5
8) 6
9)
10) II and III only
11) 10 seconds
12) Its running time will be O(1).
13)
14)
15) 16
16) O(log n)
17) 4
18)
19)
20) When determining the running time, constants are not taken into consideration.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.