Question 1 If an element is present in a list of length n, how many element visi

ID: 3828701 • Letter: Q

Question

Question 1

If an element is present in a list of length n, how many element visits, on average, are necessary to find it using a linear search?

Question options:

n / 2

Question 2

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 for loop was replaced with: for i in range(len(values) - 1) :?

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 3

In a sorting algorithm, it may be necessary to find the position of the maximum element in a list, starting from some initial position, start. What code should be placed in the blank to complete the maximumPosition function?

def maximumPosition(values, start) :

maxPos = start

for i in range(start + 1, len(values)) :

____________________

maxPos = i

return maxPos

Question options:

if values[maxPos] > values[i] :

if values[i] > values[maxPos] :

if values[i] < values[maxPos] :

if values[i] <= values[maxPos]

Question 4

Which of the following completes the selection sort function minimumPosition()?

def minimumPosition(values, from) :

minPos = from

for i in range(from + 1, len(values)) :

_____________________________

return minPos

Question options:

if values[i] > values[minPos] : minPos = i

if values[i] < values[minPos] : minPos = i

if values[i] < values[i] : minPos = i

if values[i] < values[minPos] : i = minPos

Question 5

What requirement must be satisified before an element can be located in a list using a binary search?

Question options:

The list must only contain integers

The list must be sorted

The length of the list must be a power of 2

The list must not contain any repeated values

Question 6

Which of the following expressions most precisely describes the growth behavior of an algorithm?

Question options:

O(n2) (big-Oh)

(n2) (Theta)

(n2) (Omega)

(n2) (Phi)

Question 7

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 8

What must hold true after 5 iterations of selection sort when it is working to sort a list of 10 elements?

Question options:

Exactly 5 more iterations are always necessary to complete the sort

Exactly 4 more iterations are always necessary to complete the sort

Up to 5 more iterations may be needed to complete the sort

Up to 4 more iterations may be needed to complete the sort

Question 9

Consider a list with n elements. If we visit each element n times, how many total visits will there be?

Question options:

Question 10

After 9 iterations of selection sort working on an list of 10 elements, what must hold true?

Question options:

The largest element is correctly placed by default.

One more iteration is needed to complete the sort.

The smallest element is incorrectly placed.

The largest element is incorrectly placed.

Question 11

Consider the following code segment that examines the elements of two lists:

matches = 0

for i in range(len(lst1)) :

for j in range(len(lst2)) :

if lst1[i] == lst2[j] :

matches = matches + 1

What can you conclude about the running time of this code segment if both lists contain n elements?

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(n log n).

Question 12

Which element does selection sort place in the correct location during each iteration?

Question options:

The smallest in the list

The smallest element that has not been placed in the correct location during a prior iteration

The largest element in the list

A random element

Question 13

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:

Question 14

Recall the Cash Register class developed in the textbook. What is output by the following code segment?

from cashregister2 import CashRegister

reg1 = CashRegister()

reg1.addItem(3.00)

reg2 = reg1

reg1.addItem(5.00)

print(reg2.getCount())

Question options:

The program terminates with a runtime error

Question 16

Recall the Cash Register class developed in the textbook. What is output by the following code segment?

from cashregister2 import CashRegister

reg1 = CashRegister()

reg2 = reg1

reg1.addItem(3.00)

reg1.addItem(5.00)

reg2.clear()

print(reg1.getCount())

Question options:

The program terminates with a runtime error

Question 17

Which of the following strings is a palindrome?

Question options:

"Test"

"B"

"canal"

"salami"

Question 18

How many squares are drawn by the following code segment?

def tSquare(width, x, y, canvas) :

canvas.drawRect(x, y, width, width)

if width >= 4 :

tSquare(width / 2, x, y, canvas)

tSquare(width / 2, x + width / 2, canvas)

tSquare(width / 2, x, y + width / 2, canvas)

tSquare(width / 2, x + width / 2, y + width / 2, canvas)

# Code to setup the canvas has been omitted

tSquare(0, 0, 16, canvas)

Question options:

Question 19

The following code segment is supposed to determine whether or not a string is a palindrome, meaning that it is the same forward and backward.

def isPalindrome(s) :

return palindromeHelper(s, l, h)

def palidromeHelper(s, l, h) :

if h <= l :

return True

if s[l] != s[h] :

return False

____________________

What line of code should be placed in the blank to achieve this goal?

Question options:

isPalindrome(s, l, h)

isPalindrome(s, l + 1, h - 1)

palindromeHelper(s, l, h)

palindromeHelper(s, l + 1, h - 1)

Question 20

A palindrome is a word or phrase spelled which reads the same forward or backward. Consider the following code snippet:

def palindrome(s) :

return isPal(s, 0, len(s) - 1)

def isPal(s, left, right) :

if left >= right :

return True

elif s[left] == s[right] :

return isPal(s, left + 1, right - 1)

else :

return False

What does the function palindrome return?

n / 2

Explanation / Answer

Hi, I have answered first 7 Questions.

please repost others in separate post.

please let me knwo in case of any issue in first 7.

Q1)

Ans: n

In linear search, we start searching from first element in list
So, at max we have to visit all element

Q2)
Ans: The list would still be sorted, but it would take one less iteration

So, we can ommit the iteration to sort a list with one element is not

Q3)
Ans: if values[i] > values[maxPos] :
Q4)
Ans: if values[i] < values[minPos] : minPos = i

Q5)
Ans: The list must be sorted
Q6)
Ans: (n2) (Theta) : Theta gives the on an average time complexity
Q7)
Ans: O(log n)

Navigate

Question 1 If an electron travels 0.300 m from an electron gun to a TV screen in

Question 1 If an organism has sustained a tissue-damaging injury, which receptor

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Question 1 If an element is present in a list of length n, how many element visi

Question

Explanation / Answer

Related Questions

Navigate