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_{2}n)
n for linear time – O(n)
n^{2} for quadratic time – O(n^{2})
Data Type 
Implementations 
Methods 
averageTime(n) 
worstTime(n) 
vector 
dynamically allocated array with pointers start, finish, and endofstorage 
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 (arraybased) 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 breadthfirst 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 twotree that is not complete. (2 points)
10. Construct a complete tree that is not a twotree. (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)