Name _____________________________
CPTR247
Fall '05 (100 points) Exam
1
Multiple Choice: Circle the letter of the best answer for each of the following questions. (3 points each)
1.
Provides the user of a class with the
explicit information that the user needs to invoke (or call) a method:
a) class
instance
b) method
interface
c) overriding
method
d) calling
object
2.
The code “account.setRate(newValue)” is
best described as a
a) class
b) message
c) calling
object
d) parameter
3.
In the code “account.setRate(newValue)”, account is
best described as a
a)
class
b) message
c) calling
object
d) parameter
4.
The separation of what a class provides to programmers from how the class is defined:
a) overriding
methods
b) generic
algorithms
c) derived
classes
d) data
abstraction
5.
If an object of class X is one of class Y’s
fields (aka instance variables or data members), we say that
a) X is-a Y
b) Y is-a X
c) X has-a Y
d) Y has-a X
6.
If the worstTime(n) of a function is quadratic, its smallest upper bound is
a) O(n2)
b) O(log2n)
c) O(2n)
d) O(n)
7.
If a problem is intractable, then the most efficient known algorithm that solves it
is at best
a) O(n2)
b) O(log2n)
c) O(2n)
d) O(n)
8.
When a variable is defined using the new operator, memory for that variable
is taken from
a) The
Stack
b) The
Heap
c) The
Standard Template Library
d) None
of the above. The new operator only gets a pointer.
SHORT ANSWER:
9.
Enter the elements in the box into the hierarchy of order so as to make the
following statement true. (10 points)
______ Ì ______ Ì
______ Ì ______ Ì______ Ì______ Ì______ Ì______ Ì______
Ì______
10. Give
the complexity (smallest upper bound) for each of these common operations on arbitrary
arrays and linked lists of size n. (10 points)
|
Operation |
Arbitrary
arrays |
Linked
lists |
|
find by value |
O( ) |
O( ) |
|
find by location |
O( ) |
O( ) |
|
insert at head |
O( ) |
O( ) |
|
insert at tail |
O( ) |
O( ) |
|
insert by position |
O( ) |
O( ) |
11. Describe
the O(log 2 n) algorithm for finding a
value in a sorted array. (4 points)
12. Complete
the following definition of Big-O
notation. (5 points)
Let f(n) be a function
of n.
We say that “f is O(g)” if …
13. For
each of the following functions f,
where n = 0, 1, 2, …, find a function
g such that O(g) is the smallest upper bound of f. You are to use the
definition in the previous question to prove
your answer. (8 points each)
a.
b. 
14. Prove
that 
. (10 points)
15. Determine
the worstTime(n) in Big-O notation for
each of the following snippets of code.
(4 points each)
a.
(value is an array with n elements)
int
total = 0;
for
(int i = 0; i < n; i++)
total = total + value[i];
cout
<< “The array contains:” << endl;
for
(int i = 0; i < n; i++)
{
cout
<< value[i];
}
cout
<< endl << “Total: ” << total << endl;;
b. (value is a
2-dimensional array with n rows and n columns)
for
(int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
value [i][j] = value[j][i];
}
}
c.
int
computedValue = 0;
for
(int i = n; i > 1; i = i/2)
computedValue *= i;
16. Give
a brief description of each of the following classic problems. (3 points each)
a.
Knight’s Tour
b. Towers
of
c.
n-Queens problem