Analysis Of Algorithms Ch.11 Complete Test Bank Chase

Chapter 11: Analysis of Algorithms

Multiple Choice Questions:

1) _____________________ is one of the most important computer resources

a) The size of the computer monitor

b) The number of disk drives that a computer has

c) The CPU time needed by a running program

d) A wireless keyboard

e) A wireless mouse

2) A library employee takes 45 seconds to process a returned item. One morning there were 30 items in the book return bin. How long did it take the employee to process all of the returned items?

a) 22 ½ minutes

b) 30 minutes

c) 45 minutes

d) 135 minutes

e) 1350 minutes

3) A growth function that is O(n) is ____________________

a) constant

b) logarithmic

c) linear

d) quadratic

e) exponential

4) When evaluating an algorithm, which of the following most likely contributes to the efficiency of the algorithm?

a) The number of comparisons made to process each item

b) The name of the input file

c) The number of primitive variables in the program

d) The number of arrays in the program

e) All of these are likely to contribute to the efficiency of the algorithm

5) Big – Oh notation establishes a(n) ____________ on a growth function

a) lower bound

b) upper bound

c) average (or mean) bound

d) both a) and b)

e) all of a), b), and c)

6) An algorithm has liner time complexity and can process an input of size n in a certain amount of time. If the algorithm runs on a computer that has a processor that is 5 times as fast, how large of an input can be processed in the same amount of time?

a) n + 5

b) 5n

c) n / 5

d)

e)

7) Which of the following complexity measures is the most efficient?

a) O()

b) O()

c) O(n log n)

d) O(n)

e) O(1)

8) We need to examine _______________ when evaluating the order of an algorithm.

a) loops

b) nested loops

c) method calls

d) all of a), b), and c)

e) none of these is correct

9) Suppose that a loop executes n times. The loop contains a method call whose order is O(), and some other statements that are O(1). From a complexity standpoint, the order of the loop is

a) n

b)

c)

d)

e)

10) A loop body is controlled by the following statement:

for (int count = 2; count <= n; count +=2)

If the statements in the body of the loop are all O(1), what is the order of the loop?

a) O(1/2)

b) O(1)

c) O(n)

d) O()

e) O()

1) A program is more efficient if it uses more CPU time

2) One of the ways to express the size of a problem is in terms of the number of items to be processed.

3) If the growth function for an algorithm is expressed as a polynomial, then the asymptotic complexity of the algorithm is determined by the term with the smallest exponent of the variable.

4) The asymptotic complexity of an algorithm is also called the order of the algorithm.

5) All of the terms in a growth function contribute to the order of the function

6) A growth function shows the relationship between the size of a problem and the part of an algorithm that we are trying to optimize.

7) When comparing two growth functions, a larger exponent on the problem size in the growth function indicates greater efficiency.

8) If the problem size is fairly small, then there is little difference between the efficiencies of different algorithms.

9) When determining the complexity of a segment of code, simple print statements are generally O(1).

10) When evaluating the complexity of a loop, all statements in the loop body are considered to be O(1).

1) Why is the efficiency of an algorithm important?

2) There are two algorithms that perform a particular task. Algorithm 1 has a complexity function . Algorithm 2 has a complexity function . Which algorithm is more efficient when n = 5? Which is more efficient when n = 20?

3) What is a growth function? How does it relate to the efficiency of an algorithm?

4) Which is more efficient, an O() algorithm or an O() algorithm?

5) What term or terms of a growth function are considered when determining the order of an algorithm?

6) Why are faster computer processors not an adequate solution for inefficient algorithms?

7) What parts of the code of an algorithm contribute to its complexity?

8) What is the time complexity for the following segment of code?

for (int factor1 = 1; factor1 <= n; factor1++)

{

for (factor2 = 1; factor2 < n; factor2++)

System.out.print(factor1*factor2 + " ");

System.out.println();

}