FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 3: Searching, Sorting, and Complexity Analysis

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 1

Multiple Choice

Review LaterAdd Note

Review Later

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

E) A) and D)
F) A) and C)

Correct Answer

verified

Show Answer

Question 2

Multiple Choice

Review LaterAdd Note

Review Later

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

E) A) and D)
F) None of the above

Correct Answer

verified

Show Answer

Question 3

True/False

Review LaterAdd Note

The in operator performs a binary search algorithm.

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

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

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

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

On sorted data, you can use a binary search.

The result of fib(4) is 8.

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

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

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

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

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

What is the complexity of a selection sort?

What does the Python time() function return?

Why is the efficiency of algorithms desirable?

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

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

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