Name  _____________________________

 

CPTR247  Fall '07  (100 points)                                                                                          Exam 1

 

Multiple Choice:  Circle the letter of the best answer for each of the following questions.  (2 points each)

 

1.       Every time a function or method call is made during the execution of a C++ program, an activation record is put on

a)       The Stack

b)       The Heap

c)       The Standard Template Library

d)       One of the above, whichever has been accessed most recently

 

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

 

3.       An algorithm for which the least upper bound on worstTime(n) is O(2n) is said to be

a)       logarithmic

b)       linear

c)       quadratic

d)       exponential

 

4.       An algorithm for which the least upper bound on worstTime(n) is O(n2) is said to be

a)       logarithmic

b)       linear

c)       quadratic

d)       exponential

 

5.       If a problem is intractable, then the most efficient known algorithm to solve it is at best

a)       O(n) 

b)       O(n2)

c)       O(log2n)

d)       O(2n)

 

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)       array

b)       vector

c)       stack

d)       queue

 

8.       Which of the following does the user of a class NOT need to know in order to use a method properly?

a)       method interface

b)       preconditions

c)       postconditions

d)       None of the above.  The user needs to know all of these in order to use a method properly.

 


9.       Which of the following containers does NOT support the direct access operator [ ]?

a)       vector

b)       deque

c)       list

d)       None of the above.  All support the direct access operator [ ].

 

10.    There is only one method of the queue class (which is implemented as a deque) whose worstTime(n) is O(n). Which one is it?

a)       push

b)       pop

c)       size

d)       empty

 

SHORT ANSWER: 

11.    Enter the elements in the box into the hierarchy of order so as to make the following statement true.  (6 points)

 

 

         ______ ̀ ______ ̀ ______ ̀ ______  ̀______  ̀______  ̀______  ̀______  ̀______  ̀______   

 

                          

 

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

 

 

erase

 

 

operator [ ]

 

 

empty

 

 

list

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

 

insert

 

 

push_front

 

 

pop_back

 

 

size

 

 

deque

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

 

operator [ ]

 

 

insert

 

 

erase

 

 

stack

deque

push

 

 

pop

 

 

13.    Explain how the insert method works for the vector class and why the averageTime(n) and worseTime(n) are both O(n).  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

14.    Explain how push_back works for the vector class and why the averageTime(n) is constant and worseTime(n) is linear.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15.    What is the primary advantage that the deque class has over the vector class?   (3 points)

 

 

 

 

 

 


16.    Give two advantages that the vector class has over arrays.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

17.    We used recursion to solve problems that required backtracking, such as finding our way off of a sinking ship, moving the knight around the chess board, displaying patterns and permutations, and figuring out how to move the open square in the 15-puzzle.  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.  (5 points)


18.    Complete the following definition of Big-O notation.  (2 points)

 

Let f(n) be a function of n.  We say that “f is O(g)” if …

 

 

 

 

 

 

19.    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.  (3 points each)

 

a.      

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.      


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

 

a.        

int sum;

int n;

 

cout << “Enter n: “;

cin >> n;

 

sum = (n * (n + 1)) / 2;

 

 

 

b.        

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

{

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

       {

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

       }

       cout << endl;

}

 

 

c.         (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;;

 

 

d.       (value is a sorted array with n elements)

 

int high = n-1;

int low = 0;

int middle;

int find;

 

cout << “Enter value to find: “;

cin >> find;

 

while (low <= high)

{

       middle = (high + low) / 2;

       if (find == value[middle])

              return true;

       if (find < value[middle])

              high = middle - 1;

       else

              low = middle + 1;   

}

return false;

 

 

 

 

 


21.    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.       Permutations

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.       n-Queens