Name _____________________________
CPTR247 Fall '09
(100 points) Exam
1
1. Matching: Select the word that best fits the description given. Each word should be used exactly once. (1 point each)
A. binary search
B. calling object
C. constant
D. container
E. The Heap
F. intractable
G. linear
H. logarithmic
I. method interface (aka prototype or header)
J. quadratic
K. preconditions
L. postconditions
M. queue
N. sequential search
O. stack
P. The Stack
____ When a variable is defined using the new operator, memory for that variable is taken from here.
____ Every time a function or method is called, memory for its activation record that holds (among other things) local variables for that invocation of the function is taken from here.
____ Describes the worstTime(n) for a function whose smallest upper bound is O(1).
____ Describes the worstTime(n) for a function whose smallest upper bound is O(log n).
____ Describes the worstTime(n) for a function whose smallest upper bound is O(n).
____ Describes the worstTime(n) for a function whose smallest upper bound is O(n^{2}).
____ Describes a problem for which the most efficient known algorithm to solve it is O(2^{n}).
____ The O(log n) method of finding an item in a sorted array.
____ The O(n) method for finding an item in an array (sorted or unsorted).
____ Those things that must be true in order to call a method, generally coded as comments underneath the method header.
____ Those things that will be true after a method is called, generally coded as comments underneath the method header.
____ In the code “account.setRate(newValue)”,
account
is best described as a(n) ____________
____ Gives the explicit information that the user needs to invoke (or call) a method (i.e. return type, method name, number and type of parameters).
____ A variable that consists of a collection of items.
____ A FIFO data structure.
____ A LIFO data structure.
2. Complete the following table by entering the algorithmic complexity for each method. (1 point each)
Enter one of the following for each:
O(1) O(log_{2}n) O(n) O(n^{2})
Data Type 
Implementations 
Methods 
averageTime(n) 
worstTime(n) 
vector 
dynamically allocated array with pointers start, finish, and endofstorage 
push_back 


pop_back 



insert 



begin 



operator [ ] 



list 
doubly linked list with a dummy header node, node (a pointer to the dummy node), and length 
erase 


pop_front 



push_back 



size 



deque 
dynamically allocated blocks (arraybased) with a map array, start, and finish 
push_front 


pop_front 



operator [ ] 



erase 


Short Answer:
3. Enter
the elements in the box into the hierarchy
of order so as to make the following statement true. (10 points)
______ Ě ______ Ě
______ Ě ______ Ě______ Ě______ Ě______ Ě______ Ě______
Ě______
4. There is only one method of the stack class (which is implemented as a deque) whose worstTime(n) is O(n). Which one is it (of push, pop, top, size, or empty) ? (2 points)
Why is it O(n)? (2 points)
5. Let’s compare arrays to the vector and list classes.
a. What is the main disadvantage of arrays that is not a problem with vectors and lists? (2 points)
b. What is the operation that arrays and vectors have that lists do not, thereby making them attractive data structures for some applications? (1 point)
Why doesn’t the list class have that operation? (2 points)
Multiple Choice: Circle the letter of the best answer for each of the following questions. (2 points each)
6. You
are solving a problem that requires the use of a container where objects will
be removed from the container in the same order in which they were
entered. Which container is best to use?
a) array
b) vector
c) stack
d) queue
7. You
are solving a problem that requires the use of a container where objects may be
added at any location in the container and you must have direct access to the
items in the container. Which container
is best to use?
a) list
b) vector
c) stack
d) queue
8. You
are solving a problem that requires the use of a container where objects will
be inserted and removed from the front of the contain
and also inserted and removed from the back of the container. Which container is best to use?
a) array
b) vector
c) deque
d) stack
e) queue
9. We used recursion to solve problems that
required backtracking, such as finding our way out of a maze and figuring out
how to place queens on a chessboard (or was that chickens?). Explain
how recursion is used to solve problems requiring backtracking. I’m not looking for code here but rather an
explanation of how recursion and The Stack work and how they are used for
backtracking. If drawing diagrams helps,
feel free to do so. (4 points)
10. Complete
the following definition of BigO
notation. (3 points)
Let f(n) be a function of n. We say that “f is O(g)” if …
11. 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. (4 points each)
a. _{}
b. _{}
12. Determine the worstTime(n) in BigO notation for each of the following snippets of
code. (3 points each)
a. (computing
the sum of the numbers from 1 to n)
int n;
cout << “Enter n: “;
cin >> n;
cout << (n * (n + 1)) / 2 << endl;
b. (value is an array with n elements)
int total = 0;
for (int i = 0; i < n; i++)
cin >> value[i];
cout << “Computed values are:” << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0;
j < n; j++)
{
cout
<< setw(4) << value[i] * value[j] << “ “;
}
cout <<
endl;
}
c.
(computing a value based on n)
int computedValue = 1;
for (int i = (n * n); i >= 1; i)
computedValue *=
i;
cout << “n = ” << n << endl;
cout << “computed value = ” << computedValue <<
endl;
d. (computing
another value based on n)
int computedValue = 1;
for (int i = n; i > 1; i = i/2)
computedValue *=
i;
cout << “n = ” << n << endl;
cout << “computed value = ” << computedValue <<
endl;
13. Give
a description of each of the following classic problems. Describe
the setup and explain what
the “answer” is that we’re searching for. (3 points each)
a. nQueens
b. permutations