Name  _____________________________

 

CPTR247  Fall '04  (100 points)                                                                                            Exam 2

 

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

 

 

insert

 

 

pop_back

 

 

erase

 

 

size

 

 

empty

 

 

operator [ ]

 

 

end

 

 

list

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

 

push_front

 

 

push_back

 

 

insert

 

 

pop_front

 

 

pop_back

 

 

erase

 

 

size

 

 

empty

 

 

begin

 

 

end

 

 

operator =

 

 

splice

 

 

binary search tree

doubly linked tree with dummy header node, pointer to header, node_count

size

 

 

find

 

 

insert

 

 

erase

 

 

begin

 

 

end

 

 

 


2.        Give two reasons why vectors are a better choice to use than arrays. (6 points)

 

a.         

 

 

 

 

 

 

b.        

 

 

 

 

 

 

 

 

 

3.        What “operator” does the vector class use to provide “direct access”?  (Hint:  It’s the same “operator” that is used for arrays.)  (2 points)

 

 

 

 

 

 

 

 

4.        Explain the statement, “The list class does not support direct access.” (3 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.        What is the primary advantage that the deque class has over the vector class.  What is it about the implementation of the deque that allows this?   (4 points)

 


 

6.        Explain how the insert method of the binary search tree class works.  (4 points) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Explain why the averageTime(n) for the insert method of the binary search tree is O(log n) while the worstTime(n) is linear.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.        What does it mean that our binary trees are “doubly linked”?  (3 points)

 

 

 

 

 

 

 

 

 


8.        Explain why the worstTime(n) for the push_front method of the deque class is linear while the averageTime(n) is constant. ( Recall that the deque class is implemented with dynamically allocated blocks (array-based) with a map array, start, and finish.)  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9.        Consider the following complete binary search tree.  This type of tree can be implemented with an array.  Fill in the array with the node values.  (3 points)

 

                                                                                                 

 

 

 

 

 

 

 

For the node located at position i of the array, where i is the subscript relative to 0, what is the subscript of the following:  (3 points)

 

parent ____________

 

left-child _____________

 

right-child ______________

 

 


10.     For each of the following binary search trees, indicate if they are two-trees, full, and complete. (6 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 



11.     Do the specified rotations on the trees given.  (6 points)

 

a.        Do a right rotation around 50.

 

 

 

 

 

 

 

 

 

b.       Do a left rotation around 10 followed by a right rotation around 20.