Deck 3: Searching, Sorting, and Complexity Analysis

Question 1

The time() function returns the amount of time a program has been running in seconds.

Answer 1

False

Question 2

This bubble sort has the effect of bubbling the largest items to the end of the list.

Answer 2

True

Question 3

In the average case, where many items in a list are out of order, an insertion sort is linear.

Answer 3

False

Question 4

Using a binary search, a list of 1 million items requires only 20 comparisons.

Question 5

An algorithm that uses the exact same Python code run on two different machines should have the same performance data.

Question 6

Benchmarking is the process of using the computer's clock to obtain run time information for an algorithm.

Question 7

The order of complexity of a linear-time algorithm is Oⁿ .

Question 8

The number of Python instructions executed in an algorithm will differ from the number of machine language instructions executed.

Question 9

In a bubble sort, each pass through the main loop selects a single item to be moved.

Question 10

On sorted data, you can use a binary search.

Question 11

The amount of work of a logarithmic algorithm is proportional to the log₂ of the problem size.

Question 12

The bubble sort has a complexity of O( n ²).

Question 13

Algorithms with linear behavior do more work than those with quadratic behavior.

Question 14

In a selection sort, the inner loop is executed n - 2 times for every pass through the outer loop.

Question 15

The in operator performs a binary search algorithm.

Question 16

All algorithms that perform the same task take the same amount of time to complete.

Question 17

Python's in operator is implemented as a method named __contains__ in the list class.

Question 18

The performance of an algorithm in a single loop is linear.

Question 19

The sequential search algorithm does more work to find a target at the beginning of a list than at the end of the list.

Question 20

In a selection sort, the outer loop executes n - 1 times.

Question 21

The result of fib(4) is 8.

Question 22

Which of the following is a common way to measure the time cost of an algorithm?

A) count lines of code
B) use a stopwatch
C) calculate memory usage
D) use the computer's clock

Question 23

What type of algorithm is list indexing an example of?

A) constant-time
B) logarithmic-time
C) exponential-time
D) linear-time

Question 24

What does the Python time() function return?

A) The seconds elapsed since January 1, 1970
B) The number of instructions executed
C) The number of seconds the code has been running
D) The number of milliseconds to execute a line of code

Question 25

Which of the following is a method to estimate the efficiency of an algorithm that predicts the amount of work an algorithm performs regardless of the platform?

A) using a millisecond counter
B) counting instructions
C) determining memory usage
D) convert the algorithm to byte code

Question 26

What is the worst-case complexity of a binary search?

A) O( n ²)
B) O( n )
C) O(log₂ n )
D) O²

Question 27

A bubble sort always requires approximately n² comparisons.

Question 28

How can the following algorithm be described? left = 0
Right = len(sortedLyst) - 1
While left <= right:
Midpoint = (left + right) // 2
If target == sortedLyst[midpoint]:
Return midpoint
Elif target < sortedLyst[midpoint]:
Right = midpoint - 1
Else:
Left = midpoint + 1
Return -1

A) binary search
B) bubble sort
C) sequential search
D) selection sort

Question 29

What should the missing code be in the following algorithm if the goal is to determine how many seconds the algorithm runs? start = time.time()
MyCount = 1
For x in range(100):
MyCount *= x
Elapsed = time.time() - < missing code >

A) myCount
B) elapsed
C) start
D) x

Question 30

Why is the efficiency of algorithms desirable?

A) an inefficient algorithm may use too much time or space
B) efficient algorithms always cost less money
C) inefficient algorithms always use too much memory
D) efficient algorithms always use less memory

Question 31

In the following code, what is the algorithm's complexity? minIndex = 0
CurrentIndex = 1
While currentIndex < len(lyst):
If lyst[currentIndex] < lyst[minIndex]:
MinIndex = currentIndex
CurrentIndex += 1
Return minIndex

A) O( n ²)
B) O( n )
C) O(log₂ n )
D) O²

Question 32

Which method of determining the efficiency of algorithms allows you to rate them independently of timings or instruction counts?

A) elapsed time profiling
B) byte-code assembly
C) complexity analysis
D) memory usage analysis

Question 33

How can an algorithm be described in which the work it does grows as a function of the square of the problem size?

A) exponential
B) logarithmic
C) quadratic
D) linear

Question 34

The first two numbers in the Fibonacci sequence are 1s, and each number after that is the sum of the previous two numbers.

Question 35

In a binary search of an ascending order list, where does the search algorithm begin the search?

A) the beginning of the list
B) a random spot in the list
C) the end of the list
D) the middle of the list

Question 36

How can the performance complexity of the following algorithm be described?
For x in range(numIterations):
Value = value * x
Print(value)

A) exponential
B) logarithmic
C) quadratic
D) linear

Question 37

The merge sort employs a recursive, divide-and-conquer strategy to break the O( n² ) barrier.

Question 38

What term best describes the following code?
X = myList[ i ]
MyList[ i ] = myList[ j ]
MyList[ j ] = x

A) sequential search
B) binary sort
C) selection algorithm
D) swap function

Question 39

In the first step of the quicksort, you begin by selecting the item at the list's midpoint.

Question 40

How can the following algorithm be described?
Position = 0
While position < len(lyst):
If target == lyst[ position ]:
Return position
Position += 1
Return -1

A) binary search
B) bubble sort
C) sequential search
D) selection sort

Question 41

What is the complexity of a selection sort?

A) O( n ²)
B) O( n )
C) O(log₂ n )
D) O²

Question 42

What is the best case performance of a sequential search?

A) O n
B) linear
C) quadratic
D) O(1)

Question 43

An analysis of an algorithm's complexity divides its behavior into what three types of cases?

A) best case, worst case, average case
B) minimum case, maximum case, average case
C) linear case, quadratic case, logarithmic case
D) sequential case, exponential case, binary case

Question 44

What type of algorithm is the following code?
I = 0
While i < len(myList) - 1:
MinIndex = i
J = i + 1
While j < len(myList):
If myList[ j ] < myList[ minIndex ]:
MinIndex = j
J += 1
If minIndex != i:
Swap(myList, minIndex, i)
I += 1

A) binary search
B) bubble sort
C) sequential search
D) selection sort

Question 45

How many loops are found in a typical insertion sort?

A) 1
B) 2
C) 3
D) 4

Question 46

In terms of complexity, what is the average case for an insertion sort?

A) linear
B) quadratic
C) exponential
D) logarithmic

Question 47

What type of algorithm is the following code?
N = len(myList)
While n > 1:
I = 1
While i < n:
If myList[ i ] < myList[ i - 1 ]:
Swap(myList, i, i - 1)
I += 1
N -= 1

A) linear sort
B) bubble sort
C) insertion sort
D) selection sort

Question 48

What should the missing code be in the following insertion sort algorithm? i = 1
While i < len(myList):
ItemToInsert = myList[i]
J = i - 1
While j >= 0:
If itemToInsert < myList[j]:
MyList[j + 1] = myList[j]
J -= 1
Else:
Break
< missing code >
I += 1

A) myList[ i + 1 ] = itemToInsert
B) myList[ j ] = itemToInsert
C) myList[ j + 1 ] = itemToInsert
D) myList[ i ] = itemToInsert

Question 49

In terms of complexity, what is the worst-case scenario for an insertion sort?

A) O( n ²)
B) O( n )
C) O(log₂ n )
D) O²

Question 50

Which type of algorithm is analogous to how many people organize playing cards in their hands?

A) linear sort
B) bubble sort
C) insertion sort
D) selection sort