Deck 10: Algorithm Efficiency and Sorting

Question 1

A quadratic algorithm has the growth-rate function ______.

A)O(n²)
B)O(n³)
C)O(2ⁿ)
D)O(log2ⁿ)

Answer 1

A

Question 2

Which of the following can be used to compare two algorithms?

A)growth rates of the two algorithms
B)implementations of the two algorithms
C)test data used to test programs which implement the two algorithms
D)computers on which programs which implement the two algorithms are run

Answer 2

A

Question 3

Algorithm efficiency is typically a concern for ______.

A)small problems only
B)large problems only
C)medium sized problems only
D)problems of all sizes

Answer 3

B

Question 4

Assuming a linked list of n nodes,the code fragment: Node curr = head;
While (curr != null){
System.out.println(curr.getItem());
Curr.setNext(curr.getNext());
} // end while
Requires ______ comparisons.

A)n
B)n - 1
C)n + 1
D)1

Question 5

Which of the following growth-rate functions indicates a problem whose time requirement is independent of the size of the problem?

A)O(n)
B)O(log2ⁿ)
C)O(2ⁿ)
D)O(1)

Question 6

A linear algorithm has the growth-rate function ______.

A)O(log2ⁿ)
B)O(2ⁿ)
C)O(n)
D)O(1)

Question 7

Given the statement: Algorithm A requires time proportional to f(n)
Algorithm A is said to be ______.

A)in class f(n)
B)of degree f(n)
C)order f(n)
D)equivalent to f(n)

Question 8

Assuming a linked list of n nodes,the code fragment: Node curr = head;
While (curr != null){
System.out.println(curr.getItem());
Curr.setNext(curr.getNext());
} // end while
Requires ______ write operations.

A)n
B)n - 1
C)n + 1
D)1

Question 9

The value of which of the following growth-rate functions grows the fastest?

A)O(n)
B)O(n²)
C)O(1)
D)O(log2ⁿ)

Question 10

An algorithm's execution time is related to the number of ______ it requires.

A)parameters
B)test data sets
C)data fields
D)operations

Question 11

If a problem of size n requires time that is directly proportional to n,the problem is ______.

A)O(1)
B)O(n)
C)O(n²)
D)O(2ⁿ)

Question 12

Consider an algorithm that contains loops of the form: for (x = 1 through n ){
For (y = 1 through x){
For (z = 1 through 10){
Task T
} // end for
} // end for
} // end for
If task T requires t time units,the loop on y requires ______ time units.

A)10 * t
B)(10 * t)+ x
C)10 * t * x
D)t * x

Question 13

An exponential algorithm has the growth-rate function ______.

A)O(n²)
B)O(n³)
C)O(2ⁿ)
D)O(log2ⁿ)

Question 14

A growth-rate function of ______ implies a problem whose time requirement is constant.

A)1
B)n
C)2ⁿ
D)log2ⁿ

Question 15

The solution to the Towers of Hanoi problem with n disks requires 2ⁿ - 1 moves.If each move requires the same time m,the solution requires ______ time units.

A)2ⁿ - 1
B)(2ⁿ - 1)+ m
C)(2ⁿ - 1)/ m
D)(2ⁿ - 1)* m

Question 16

Algorithm analysis should be independent of all of the following EXCEPT ______.

A)the programming style used in the implementation of the algorithm
B)the computer used to run a program which implements an algorithm
C)the number of significant operations in an algorithm
D)the test data used to test a program which implements an algorithm

Question 17

The value of which of the following growth-rate functions grows the slowest?

A)O(n)
B)O(n²)
C)O(1)
D)O(log2ⁿ)

Question 18

Consider an algorithm that contains loops of the form: for (x = 1 through n ){
For (y = 1 through x){
For (z = 1 through 10){
Task T
} // end for
} // end for
} // end for
If task T requires t time units,the innermost loop on z requires ______ time units.

A)y
B)10
C)z * t
D)10 * t

Question 19

Assuming a linked list of n nodes,the code fragment: Node curr = head;
While (curr != null){
System.out.println(curr.getItem());
Curr.setNext(curr.getNext());
} // end while
Requires ______ assignments.

A)n
B)n - 1
C)n + 1
D)1

Question 20

Which of the following is NOT part of the human cost of developing a computer program?

A)the efficiency of a program
B)the readability of a program
C)the modifiability of a program
D)the maintainability a program

Question 21

A bubble sort requires at most ______ passes to sort an array of n items.

A)n/2
B)n - 2
C)n - 1
D)n

Question 22

For large arrays,the insertion sort is prohibitively inefficient.

Question 23

In the worst case,a binary search is ______.

A)O(n)
B)O(1)
C)O(log2ⁿ)
D)O(n²)

Question 24

The efficiency of the selection sort depends on the initial arrangement of the data.

Question 25

Given the fact that a selection sort of n items requires n²/2 + 5 * n/2 - 3 major operations,the selection sort is ______.

A)O(n)
B)O(1)
C)O(n²)
D)O(n²/2)

Question 26

In the best case,a sequential search is ______.

A)O(n)
B)O(1)
C)O(log2ⁿ)
D)O(n²)

Question 27

The quicksort is ______ in the worst case.

A)O(n²)
B)O(n³)
C)O(n * log2ⁿ)
D)O(log2ⁿ)

Question 28

Low-order terms can be ignored in an algorithm's growth-rate function.

Question 29

The values of the growth-rate function O(log2ⁿ)grow faster than the values of the growth-rate function O(n).

Question 30

The mergesort is a recursive sorting algorithm.

Question 31

The ______ compares adjacent items and exchanges them if they are out of order.

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

Question 32

Given the following array: 4 15 8 3 28 21
Which of the following represents the array after the second swap of the selection sort?

A)4 3 8 15 21 28
B)4 15 8 3 21 28
C)3 4 8 15 21 28
D)21 4 3 8 15 28

Question 33

According to the following statements:
Algorithm A requires time proportional to n
Algorithm B requires time proportional to n²
algorithm B's time requirement - as a function of the problem size n - increases at a slower rate than algorithm A's time requirement.

Question 34

The recursive binary search algorithm is a logarithmic algorithm.

Question 35

Each merge step of the mergesort requires ______ major operations.

A)3 * n - 1
B)4 * n - 1
C)(n - 1)/2
D)n - 1

Question 36

In the worst case,the insertion sort's comparison occurs ______ times.

A)n
B)n - 1
C)(n - 1)/ 2
D)n * (n - 1)/2

Question 37

To sort numeric data,the radix sort treats a number as a character string.

Question 38

The analysis of an algorithm must take into consideration the computer that will be used to run a program that implements the algorithm.

Question 39

An algorithm's time requirements can be derived as a function of the problem size.

Question 40

The selection sort is continued until ______ of the n items in an array have been swapped.

A)n/2
B)n - 2
C)n - 1
D)n

Question 41

How does the quicksort partition an array?

Question 42

Compare the efficiencies of the quicksort and the mergesort in the worst case.

Question 43

What is determined by worst-case analysis?

Question 44

What is an external sort?

Question 45

What is the sort key of a record?

Question 46

What is the drawback of the mergesort with respect to storage?

Question 47

What is measured by an algorithm's growth rate?

Question 48

Suppose we have three algorithms,and their orders are O(n²),O(2ⁿ)and O(log2 n).Arrange these orders in increasing magnitude.

Question 49

Consider the following nested loop.What is the order of the algorithm?
for (int i = 0;i < n;++i)
for (int j = i;j < n;++j)
for (int k = 1;k < 100;++k)
…

Question 50

What measurements are parts of a program's efficiency?

Question 51

When choosing between two algorithms,under what conditions can the efficiencies of the algorithms be ignored?

Question 52

What is a growth-rate function?

Question 53

Suppose we wish to sort an array of 3-digit integers using radix sort.We will make three passes over the elements of the array.What occurs during the first pass?

Question 54

What does the area analysis of algorithms focus on?

Question 55

What is an internal sort?

Question 56

List the three factors which can cloud the comparison of algorithms performed by implementing the algorithms in Java and running the programs.

Question 57

If an algorithm requires 2ⁿ³ + 17n² + 54n + 512 operations to perform,where n is the size of the input data,then we say the order of the algorithm is O(_____).

Question 58

Consider the following nested loop.What is the order of the algorithm?
for (int i = 0;i < n;++i)
for (j = 1;j < n;j *= 2)
…

Question 59

What is determined by average-case analysis?

Question 60

In the worst case,how many comparisons are required in the bubble sort?