Name  _____________________________

 

CPTR247  Fall '12  (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(n2).

 

____     Describes a problem for which the most efficient known algorithm to solve it is O(2n).

 

____     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(log2n)     O(n)    O(n2)

 

Data Type

Implementations

Methods

averageTime(n)

worstTime(n)

vector

dynamically allocated array with pointers start, finish, and end-of-storage

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 (array-based) 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 container 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 Big-O 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 Big-O 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 set-up and explain what the “answer” is that we’re searching for.  (3 points each)

 

a.       n-Queens

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.       permutations