Name _____________________________

CPTR247 Fall '05 (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
		erase
		size
		operator [ ]
array	unsorted	find
array	sorted	find
list	doubly linked list with a dummy header node, node (a pointer to the dummy node), and length	push_front
		push_back
		size
		operator =
deque	dynamically allocated blocks (array-based) with a map array, start, and finish	push_back
		operator [ ]
		begin
		end
		push_front
stack	deque	empty
		size
		push
		top
		pop
binary search tree	doubly linked tree with dummy header node, pointer to header, node_count	size
		find
		erase

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

3. Explain how insert works for the vector class and why the averageTime(n) and worseTime(n) are as you stated in question 1. (4 points)

4. Let’s compare the vector and list classes.

a. Explain why the insert method is more efficient in the list class than in the vector class. (3 points)

b. What O(1) operation does the vector class have that the list class does not, thereby making it an attractive data structure for some applications? Why doesn’t the list class have that operation? (3 points)

5. What is meant when we say a data structure is LIFO or FIFO? For each, give an example of a data structure that falls into each category. (4 points)

LIFO -

FIFO -

6. Evaluate the following postfix expressions: (2 points)

12 2 1 + /

12 2 + 1 /

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

8. Answer the following questions regarding this tree:

Is this a binary search tree? (yes or no) (1 point)

What is the root? (1 point)

How many nodes are in the tree? (1 point)

What is the height of the tree? (1 point)

List the leaves in the tree. (2 points)

Name the children of node 25: (1 points)

Name the parent of node 16: (1 points)

List the nodes as they would be processed in a breadth-first search: (2 points)

List the nodes as they would be processed in a preorder traversal: (2 points)

List the nodes as they would be processed in an inorder traversal: (2 points)

List the nodes as they would be processed in a postorder traversal: (2 points)

9. Construct a two-tree that is not complete. (2 points)

10. Construct a complete tree that is not a two-tree. (2 points)

11. Construct a binary tree of height 3 with 8 nodes. (2 points)

12. What is the largest number of nodes possible in a binary tree of height 3? (1 point)

13. What is the smallest number of nodes possible in a binary tree of height 3? (1 point)