Name _____________________________
CPTR247
Fall '05 (100 points) Exam
3
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) 
AVL trees 
balanced binary search tree 
insert 


find 



Redblack trees (and therefore sets, multisets, maps, multimaps) 
balanced binary search tree 
insert 


find 



begin 



[ ] (map class only) 



Priority Queue 
Heap (complete binary tree implemented with a vector) 
push 


pop 



make_heap 



Sorts 
vector (values are already in the vector) 
insertion sort 


tree sort 



heap sort 



quicksort 



Hashing 
fixed size vector of buckets 
insert 


find 


2. Give the definition of an AVL tree. (5 points)
3. Below is psuedocode for inserting items into an AVL tree:
 inserted as for a normal binary search tree and its balance factor is set to ‘=’
 ancestor points to the closest ancestor whose balance factor is not ‘=’
Case 1: ancestor is null: no rotations are necessary, adjust balance factors from inserted node to root.
Case 2: ancestor’s balance factor is ‘L’ and insertion was made in the ancestor’s right subtree, or ancestor’s balance factor is ‘R’ and insertion was made to the ancestor’s left subtree: no rotations are necessary, change ancestor’s balance factor to ‘=’ and adjust the balance factors of the nodes between ancestor and inserted node.
Case 3: ancestor’s balance factor is ‘R; and the inserted node is in the right subtree of the right subtree of the ancestor node: do a left rotation around the ancestor node, adjust the balance factors as necessary.
Case 4: ancestor’s balance factor is ‘L’ and the inserted node is in the left subtree of the left subtree of the ancestor node: do a right rotation around the ancestor node, adjust the balance factors as necessary.
Case 5: ancestor’s balance factor is ‘L’ and the inserted node is in the right subtree of the left subtree of the ancestor node: do a left rotation around the ancestor’s left child, and then a right rotation around the ancestor node, adjust balance factors as necessary.
Case 6: ancestor’s balance factor is ‘R; and the inserted node is in the left subtree of the right subtree of the ancestor node: do a right rotation around the ancestor’s right child and then a left rotation around the ancestor, adjust balance factors as necessary.
For each of the following trees, the number indicated is to be inserted into the given tree. State the case number that is applicable and draw the tree as it would be after the insert is complete. (10 points)
Tree Insert Case # Resulting Tree
100
65
4. Give the definition of a heap. (5 points)
5. Insert (push) the value 98 into the following heap. Draw the resulting heap. (4 points)
6. Pop the following heap. Draw the resulting heap. (4 points)
Multiple Choice: Circle the letter of the best answer for each question.
7. Why are AVL trees and redblack trees better than arbitrary binary search trees? (3 points)
a. they avoid the “bushyness” of arbitrary binary search trees
b. the insert method does not need to reach the leaf level before the node can be inserted
c. their height is always logarithmic in n (the number of nodes)
d. all of the above
8. The underlying data structure for the set, multiset, map, and multimap classes is which of the following? (3 points)
a. vector
b. redblack tree
c. heap
d. priority queue
9. You’re putting together a computer lab and want to give a unique name to each workstation. As you and your friends come up with names, you want to collect them into a data structure. Since each workstation must have a unique name, you don’t want to have names stored more than once. Which of the following STL data structures would be most appropriate to hold the strings? (3 points)
a. set
b. multiset
c. map
d. multimap
10. You are writing a program for an automatic teller machine (ATM). You have a structure defined for each customer, each of which has a unique account number. When a customer inserts his/her card into an ATM, you want to locate their balance information by using the account number that’s on the card. Which of the following STL data structures would be most appropriate to hold the customer information? (3 points)
a. set
b. multiset
c. map
d. multimap
11. We saw several sample programs illustrating the various sorting algorithms. When sorting structures, we need to overload the less than (<) operator so that the sort function in the Standard Template Library could be used. Which of the following functions properly overloads the less than operator if we want to sort student structures by id within name? (That is, if we have two John Does, the one with the lower id number would appear first.) (3 points)
a.
bool
operator < (student s1, student s2)
{
return
((s1.name < s2.name) && (s1.id < s2.id));
}
b.
bool
operator < (student s1, student s2)
{
return
((s1.name < s2.name)  (s1.id < s2.id));
}
c.
bool
operator < (student s1, student s2)
{
return
((s1.name < s2.name)  (s1.name == s2.name && s1.id < s2.id));
}
d.
bool
operator < (student s1, student s2)
{
return ((s1.name
< s2.name && s1.id < s2.id)  (s1.name == s2.name));
}
12. To implement tree sort using the Standard Template Library, we can use the _______ class. (3 points)
a.
set
b.
multiset
c.
map
d.
multimap
e. All of the above.
f. None of the above.
13. Heap sort uses the following process to sort a vector already loaded with n integers: (3 points)
a. pushes the items into a redblack tree, then uses an inorder traversal
b. iteratively compares vector entries, performing rotations on those that are out of order
c. performs make_heap on the vector followed by sort_heap
d. none of the above, because we cannot use heapsort to sort a vector, only heaps
14. Perform 2 iterations of quicksort on the following vector. (5 points)
10 
50 
20 
70 
80 
60 
17 
15 
90 
35 
After 1^{st} iteration:










After 2^{nd} iteration:










15. Given the following character frequencies, create the Huffman Tree. (6 points)
a: 900
c: 400
e: 1100
n: 800
r: 300
t: 500
16. Using the Huffman Tree that you created in the previous question, encode the word ‘rent’. (4 points)
17. In openaddressing, with the quotientoffset collision handler, insert the following keys into a hash table of size 11: (6 points)
20 33 49 26 42 27 40 51
Here are the relevant remainders and quotients:
key 
key % 11 
key / 11 
20 
9 
1 
33 
0 
3 
49 
5 
4 
26 
4 
2 
42 
9 
3 
27 
5 
2 
40 
7 
3 
51 
7 
4 
Hash table:











0
1
2
3
4
5
6
7
8
9
10