Chapter 10 Questions
Multiple Choice Questions
1. Which of the following is NOT part of the human cost of developing a computer program?
a. efficiency of a program
b. the the readability of a program
c. the modifiability of a program
d. the maintainability a program
2. 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
3. An algorithm’s execution time is related to the number of ______ it requires.
a. parameters
b. test data sets
c. data fields
d. operations
4. Assuming a linked list of n nodes, the C++ statements
Node *cur = head;
while (cur != null)
{ cout << curr->item << endl;
cur = cur->next;
} // end while
require ______ assignment(s).
a. n
b. n – 1
c. n + 1
d. 1
5. Assuming a linked list of n nodes, the C++ statements
Node *cur = head;
while (cur != null)
{ cout << curr->item << endl;
cur = cur->next;
} // end while
require ______ comparison(s).
a. n
b. n – 1
c. n + 1
d. 1
6. Assuming a linked list of n nodes, the C++ statements
Node *cur = head;
while (cur != null) {
cout << curr->item << endl;
cur = cur->next;
} // end while
perform ______ write operations.
Chapter 10 Questions
a. n
b. n – 1
c. n + 1
d. 1
7. The solution to the Towers of Hanoi problem with n disks requires 2n – 1 moves. If each move requires the
same time m, the solution requires ______ time units.
a. 2n – 1
b. (2n – 1) + m
c. (2n – 1) / m
d. (2n – 1) * m
8. Consider an algorithm that contains loops of this form:
for (i = 1 through n)
{ for (j = 1 through i)
{ for (k = 1 through 10)
{ Task T
}
}
}
If task T requires t time units, the innermost loop on k requires ______ time units.
a. j
b. 10
c. k * t
d. 10 * t
9. Consider an algorithm that contains loops of this form:
for (i = 1 through n )
{ for (j = 1 through i)
{ for (k = 1 through 10)
{ Task T
}
}
}
If task T requires t time units, the loop on j requires ______ time units.
a. 10 * t
b. (10 * t) + i
c. 10 * t * i
d. t * i
10. 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
11. 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
Chapter 10 Questions
12. 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(n2)
d. O(log2 n)
13. Which of the following growth-rate functions grows the fastest in value?
a. 1
b. n
c. n2
d. log2 n
14. Which of the following growth-rate functions grows the slowest in value?
a. 1
b. n
c. n2
d. log2 n
15. Which of the following growth-rate functions indicates a problem whose time requirement is constant?
a. 1
b. n
c. 2n
d. log2 n
16. Which of the following growth-rate functions indicates a problem whose time requirement is independent of the
size of the problem?
a. 1
b. n
c. 2n
d. log2 n
17. A linear algorithm has the growth-rate function ______.
a. 1
b. n
c. 2n
d. log2 n
18. A quadratic algorithm is ______.
a. O(n2)
b. O(n3)
c. O(2n)
d. O(log2 n)
19. An exponential algorithm is ______.
a. O(n2)
b. O(n3)
c. O(2n)
d. O(log2 n)
Chapter 10 Questions
Chapter 10 Questions
True/False Questions
1. The analysis of an algorithm must take into consideration the computer that will be used to run a program that
implements the algorithm.
2. For a problem of size n, if Algorithm A requires time proportional to n, and Algorithm B requires time
proportional to n2, B’s time requirement increases at a slower rate than A’s time requirement.
3. The values of the growth-rate function O(log2 n) grow faster than the values of the growth-rate function O(n).
4. Low-order terms in an algorithm’s growth–rate function can be ignored.
5. Function f(n) is O( g(n) ) if f(n)>g(n) for all n>0.
Chapter 10 Questions
Short Answer Questions
1. What measurements indicate a program’s efficiency?
2. The analysis of algorithms—as an area of study—provides what tools for the computer scientist?
3. List three reasons why you should not write and run C++ programs to compare the time efficiency of
algorithms.
4. What does an algorithm’s growth rate measure?
5. What is a growth-rate function?
6. What is measured by a worst-case analysis?
7. What is measured by an average-case analysis?
8. When choosing between two algorithms, under what conditions can the efficiencies of the algorithms be
ignored?