Name  _____________________________

 

CPTR247  Fall '06  (100 points)                                                                                            Exam 1

 

1.        Matching:  Select the word that best fits the description given.  Not every word will be used.  (1 point each)

 


A.      binary search

B.       calling object

C.       constant

D.      container

E.       The Heap

F.       linear

G.       logarithmic

H.      memory leak

I.         message

J.        method interface

K.      quadratic

L.       preconditions

M.     postconditions

N.      queue

O.      robust

P.       sequential search

Q.      stack

R.       The Stack

S.       STL (Standard Template Library)

T.       template classes


 

____     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.

 

____     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 generic name for a call to a method in a class.

 

 

____     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).

 

 

____     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).

 

 

____     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:

                     C    for constant time – O(1)

                  log    for logarithmic time – O(log2n)

                      n    for linear time – O(n)

                    n2    for quadratic time – 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

 

insert

 

 

pop_front

 

 

pop_back

 

 

empty

 

 

deque

dynamically allocated blocks (array-based) with a map array, start, and finish

 

push_front

 

 

push_back

 

 

operator [ ]

 

 

insert

 

 

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)

 

 

 

 

 

 

5.        Explain how push_back works for the vector class and why the averageTime(n) and worseTime(n) are as you stated in question 2.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.        Explain how pop_front works for the list class and why the averageTime(n) and worseTime(n) are as you stated in question 2.  (4 points)

 


7.        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 structure for some applications?  Why doesn’t the list class have that operation?  (3 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


8.         We used recursion to solve problems that required backtracking, such as finding our way off of a sinking ship and figuring out how to move the pegs in the dreaded Triangle problem.  Explain how recursion was 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.  (5 points)


9.        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 …

 

 

 

 

 

 

10.     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.  (5 points each)

 

a.       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.      


11.      Determine the worstTime(n) in Big-O notation for each of the following snippets of code.  (3 points each)

 

a.         

for (int i = 0; i < n; i++)

{

       for (int j = 0; j < n; j++)

       {

              cout << setw(4) << i * j << “ “;

       }

       cout << endl;

}

 

 

 

 

 

 

 

b.        (value is an array with n elements)

 

int total = 0;

 

for (int i = 0; i < n; i++)

    cin >> value[i];

 

cout << “The array contains:” << endl;

for (int i = 0; i < n; i++)

{

   cout << value[i] << endl;

   total = total + value[i];

}

 

cout << endl << “Total: ” << total << endl;;

 

 

 

 

 

 

 

 

 

c.         

int computedValue = 1;

 

for (int i = (n * n * n); i >= 1; i--)

       computedValue *= i;

 

 


12.     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.        Knight’s Tour

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.       Towers of Hanoi