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(log₂n)

n for linear time – O(n)

n² for quadratic time – O(n²)

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.