Name  _____________________________

 

CPTR247  Fall '04  (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(log2n)

                      n    for linear time – O(n)

                    n2    for quadratic time – O(n2)

 

Data Type

Implementations

Methods

averageTime(n)

worstTime(n)

AVL trees

 

balanced binary search tree

insert

 

 

find

 

 

height

 

 

Red-black trees (and therefore sets, multisets, maps, multimaps)

 

balanced binary search tree

insert

 

 

find

 

 

erase

 

 

begin

 

 

end

 

 

size

 

 

empty

 

 

[ ]  (map class only)

 

 

Priority Queue

Heap (complete binary tree)

size

 

 

empty

 

 

push

 

 

pop

 

 

top

 

 

make_heap

 

 

 

 

 

2.        Give the definition of an AVL tree. (5 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


3.        Explain why AVL trees and Red-black trees are “better” than arbitrary binary search trees.  (5 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.        Do the specified rotations on the trees given.  (8 points)  

 

a.        Do a right rotation around 50.

 

 

 

 

 

 

 

 

 

b.       Do a right rotation around 17 followed by a left rotation around 10.

 

 


5.        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 subree 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 subgtree 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

 

 

 

 

 

                                                                                 3

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                25

 

 


6.        Fill in the table below with the container class that is described.  Select from set, multiset, map, and multimap.  (8 points)

 

___________      contains key-item combinations, but the key must be unique

 

___________      contains key-item combinations, and you can have more than one item with the same key

 

___________      a collection of individual items, and there may be duplicates

 

___________      a collection of individual items, all of which are unique

 

 

7.        Consider the following code:

 

typedef map<string, int> themap;

 

themap mymap;

 

mymap.insert(pair <string, int> (“Fred”, 59));

mymap.insert(pair <string, int> (“Ethel”, 57));

mymap.insert(pair <string, int> (“Ricky”, 45));

mymap.insert(pair <string, int> (“Lucy”, 42));

 

  1. What is the output of the following:  (3 points)

 

cout << mymap[“Lucy”] << endl;

 

 

 

  1. Explain why the following code produces the given output in alphabetical order.  (3 points)

 

themap::iterator itr;

 

itr = mymap.begin();

 

cout << itr->first << “ “ << itr->second << endl;

 

 

 

 

 

8.        Give the definition of a heap.  (5 points) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9.        For the following heap, fill in the underlying vector with the node values as it would be laid out in memory. (5 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10.     The value 95 is to be inserted into the heap in question 9.  Draw the resulting heap (in tree form).  (5 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


11.     The following vector is to be converted into a heap.   Give the contents of the vector after it is heapified.  (HINT:  Construct the “tree version” corresponding to the vector and then go through the heapifying process.) (5 points)

 

57

43

55

73

99

60

45

30

90

78

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12.     Draw the contents of the following priority queue (implemented as a heap) after the pop method has been called.  (5 points)

 

                                                                                                

 

 


13.     Given the following character frequencies, create the Huffman Tree. (5 points)

 

a: 1800

c: 50

e: 600

n: 800

r: 300

S: 500

t: 900

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

14.      Using the Huffman Tree that you created in the previous question, encode the word Santa  (5 points)


EXTRA CREDIT:  (10 points)

 

Let minh be the minimum number of items in an AVL tree of height h.  Prove by induction that

 

minh = fib(h + 3) - 1

 

where fib(n) is the function for the Fibonacci numbers.