Question 1 Consider the triangleArea function from the textbook shown below: 1.

Question

Question 1

Consider the triangleArea function from the textbook shown below:

1. def triangleArea(sideLength) :

2.    if sideLength <= 0 :

3.       return 0

4.    if sideLength == 1 :

5.       return 1

6.    smallerSideLength = sideLength - 1

7.    smallerArea = triangleArea(smallerSideLength)

8.    area = smallerArea + sideLength

9.    return area

What will happen if line #6 is changed to:

smallerSideLength = sideLength

Question options:

Infinite recursion will occur when sideLength is equal to 0.

Infinite recursion will occur when sideLength is equal to 1.

Infinite recursion will occur when sideLength is greater than or equal to 2.

Infinite recursion will occur for any value of sideLength.

Question 2

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, 8, canvas)

Question options:

1

4

5

8

Question 3

Consider the following function:

1. def mystery(n, m) :

2.    if n == 0 :       # special case 1

3.       return 0

4.    if n == 1 :       # special case 2

5.       return m

6.    return m + mystery(n - 1), m)

What will happen if lines #2 and #3 were swapped with lines #4 and #5?

Question options:

The original function and the modified function will return the same result for all integer values of n and m.

The original function and the modified function will return different results for all integer value of n and m.

The original function and the modified function will return the same result when n is greater than m, and different results when m is greater than n.

The original function and the modified function will return the same result when n is less than m, and different results when m is less than n.

Question 4

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 5

Complete the code for the myFactorial recursive function shown below, which is intended to compute the factorial of the value passed to the function:

1. def myFactorial(n) :

2.    if _____________________________ :

3.       return 1

4.    else :

5.       return n * myFactorial(n - 1)

Question options:

n == 1

(n - 1) == 1

n * (n - 1) == 1

myFactorial(n) == 1

Question 6

Recall the permutations function from Section 11.5 in the textbook.

def permutations(word) :

   result = []

   if len(word) == 0 :

      result.append(word)

      return result

   else:

      for i in range(len(word)) :

         shorter = word[ : i] + word[i + 1 : ]

         shorterPermutations = permutations(shorter)

         for string in shorterPermutations :

            result.append(word[i] + string)

      return result

What is the base case for this function?

Question options:

The empty list

Any list containing exactly one character

The empty string

Any string containing exactly one character

Question 7

Which sorting algorithm has better than O(n2) behavior, even in the worst case?

Question options:

Insertion sort

Merge sort

Quicksort

Selection sort

Question 8

A particular algorithm visits n3 + nlog(n) + n! elements in order to perform its task on a list of n elements. Which big-Oh expression best describes the growth rate of this algorithm?

Question options:

O(n)

O(n3)

O(n!)

O(nlog(n))

Question 9

Assume we are using quicksort to sort a list into ascending order. Where does quicksort place the pivot element after partitioning the list?

Question options:

The pivot element is placed at the lowest index in the list that is still available.

The pivot element is placed at the highest index in the list that is still available.

The pivot element is placed in a position that is closer to its final correct location.

The pivot element is placed in its final correct location.

Question 10

Consider the swap function shown below from the SelectionSorter class. If we modified it as shown in the swap2 function shown below, what would be the effect on the sort function?

def swap(values, i, j) :

   temp = values[i]

   values[i] = values[j]

   values[j] = temp

def swap2(values, i, j) :

   values[i] = values[j]

   values[j] = values[i]

Question options:

There would be no effect

Some list elements would be overwritten

It would sort the list in reverse order

It would still be correct, but run a little faster

Question 11

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 12

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 13

The function findLargest examines the elements of an list lst which contains non-negative values

curLargest = -1

for i in range(len(lst)) :

   if lst[i] >= curLargest :

      curLargest = lst[i]

What can you conclude about the running time of this section of code?

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 14

Recall the merge sort algorithm presented in the textbook. That algorithm requires T(n) = T(n / 2) + T(n / 2) + 5n visits to sort a list of n elements. The function to merge two sorted lists requires a total of 5n visits. What does T(n / 2) describe?

Question options:

The total number of visits needed to merge sort a list of n elements

Half the number of visits needed to merge sort a list of n elements

The total number of visits needed to merge sort a list of n / 2 elements

Half the number of visits needed to merge sort a list of n / 2 elements

Question 15

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 16

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 17

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 18

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 19

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 20

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

Infinite recursion will occur when sideLength is equal to 0.

Infinite recursion will occur when sideLength is equal to 1.

Infinite recursion will occur when sideLength is greater than or equal to 2.

Infinite recursion will occur for any value of sideLength.

Explanation / Answer

Answers in bold.

1. Consider the triangleArea function from the textbook shown below:

1. def triangleArea(sideLength) :

2.    if sideLength <= 0 :

3.       return 0

4.    if sideLength == 1 :

5.       return 1

6.    smallerSideLength = sideLength - 1

7.    smallerArea = triangleArea(smallerSideLength)

8.    area = smallerArea + sideLength

9.    return area

What will happen if line #6 is changed to:

smallerSideLength = sideLength

Question options:

Infinite recursion will occur when sideLength is equal to 0.

Infinite recursion will occur when sideLength is equal to 1.

Infinite recursion will occur when sideLength is greater than or equal to 2.

Infinite recursion will occur for any value of sideLength

2. 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, 8, canvas)

Question options:

1

4

5

8

3. Consider the following function:

1. def mystery(n, m) :

2.    if n == 0 :       # special case 1

3.       return 0

4.    if n == 1 :       # special case 2

5.       return m

6.    return m + mystery(n - 1), m)

What will happen if lines #2 and #3 were swapped with lines #4 and #5?

Question options:

The original function and the modified function will return the same result for all integer values of n and m.

The original function and the modified function will return different results for all integer value of n and m.

The original function and the modified function will return the same result when n is greater than m, and different results when m is greater than n.

The original function and the modified function will return the same result when n is less than m, and different results when m is less than n.

4. 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)

Infinite recursion will occur when sideLength is equal to 0.

Infinite recursion will occur when sideLength is equal to 1.

Infinite recursion will occur when sideLength is greater than or equal to 2.

Infinite recursion will occur for any value of sideLength

2. 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, 8, canvas)

Question options:

1

4

5

8

3. Consider the following function:

1. def mystery(n, m) :

2.    if n == 0 :       # special case 1

3.       return 0

4.    if n == 1 :       # special case 2

5.       return m

6.    return m + mystery(n - 1), m)

What will happen if lines #2 and #3 were swapped with lines #4 and #5?

Question options:

The original function and the modified function will return the same result for all integer values of n and m.

The original function and the modified function will return different results for all integer value of n and m.

The original function and the modified function will return the same result when n is greater than m, and different results when m is greater than n.

The original function and the modified function will return the same result when n is less than m, and different results when m is less than n.

4. 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)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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