line

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

n for linear time – O(n)

n² for quadratic time – O(n²)

Data Type	Implementations	Methods	averageTime(n)	worstTime(n)
AVL trees	balanced binary search tree	insert
AVL trees	balanced binary search tree	find
Red-black 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
Hashing	fixed size vector of buckets	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

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 red-black trees better than arbitrary binary search trees? (3 points)

a. they avoid the “bushy-ness” 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. red-black 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 red-black 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)

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 open-addressing, with the quotient-offset 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: