Name  _____________________________

 

CPTR247  Fall '07  (100 points)                                                                                          Exam 2

 

1.       Complete the following table by entering the algorithmic complexity for each method.  (26 points - 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)

                nlog    for n*log(n) – O(n log2n)

                    n2    for quadratic time – O(n2)

Data Type

Implementations

Methods

averageTime(n)

worstTime(n)

(arbitrary) Binary search tree

doubly linked tree with dummy header node, pointer to header, node_count

find

 

 

insert

 

 

erase

 

 

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

 

 

balanced binary search tree

begin

 

 

insert

 

 

erase

 

 

[ ]  (map class only)

 

 

Priority Queue

 

 

heap (complete binary tree implemented with a vector)

push

 

 

pop

 

 

size

 

 

make_heap

 

 

Hashing

fixed size vector of buckets – linked list implementation

insert

 

 

find

 

 

 

 

2.       What is the smallest number of nodes in an arbitrary binary search tree of height 3?  (2 points)

 

 

 

 

3.       What is the largest number of nodes in an arbitrary binary search tree of height 3? (2 points)

 

 

 

 

4.       What is the smallest number of nodes in an AVL tree of height 3?  (2 points)

 

 

 

 

5.       What is the largest number of nodes in an AVL tree of height 3? (2 points)

 


For the trees in questions 6-8, label the vertices with integers.

 

6.        Construct a binary search tree that is not a two-tree.  (2 points) 

 

 

 

 

 

 

 

 

 

 

7.       Construct a binary search tree that is a two-tree but is not a complete tree.  (2 points)

 

 

 

 

 

 

 

 

 

 

 

8.       Construct a binary search tree that is a complete tree but is not a two-tree.  (2 points)

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 


10.    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.  (8 points)

 

                                Tree                                    Insert                      Case #                                        Resulting Tree

 

 

 

 

 

                                                                                25                           ____

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                75                           ____

 

 


Multiple Choice:  Circle the letter of the BEST answer for each question.

 

11.    There was an old lady who lived in a shoe.  She had so many children she didn’t know what to do.  In particular, after a while she began to worry that, as each new child came along, she might accidently give him/her the same name as a child already running around the shoe.  To help her out, we’re going to create a program to keep track of the names of her children.  Before she fills out the birth certificate for a new child, she will enter the chosen name into our program, and if it is a duplicate, we’ll give her an error message and allow her to pick another name.  What data structure is best to hold the necessary information?  (3 points)

 

a.       set

b.       multiset

c.        map

d.       multimap

 

12.    The old lady liked our program from question 11 so much that she’s asked us to write another program to help her plan for birthday parties.  She has asked us to write a program that allows her to enter a month and day combination and the program is to list the names of all of the children who have birthdays on that day.  What data structure is best to hold the necessary information?  (3 points)

 

a.       set <int>

b.       multiset <string>

c.        map <int, string >

d.       multimap <int, string>

 

13.    Consider the following code:

 

typedef map<string, int> mymap;

typedef map<string, int>::iterator itr;

 

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

 

itr = mymap.begin();

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

 

What will be displayed on the screen?  (3 points)

 

a.       Fred 59

b.       Ethel 57

c.        Ricky 45

d.       Lucy 42

 

14.    The default underlying data structure for a multiset is a _______.  (3 points)

 

a.       vector

b.       binary search tree

c.        red-black tree

d.       linked list

 

15.    The default underlying data structure for a priority queue is a _______.  (3 points)

 

a.       vector

b.       binary search tree

c.        red-black tree

d.       linked list


16.    Insert (push) the value 85 into the following heap.  Draw the resulting heap.  (4 points)

 

49

 

56

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

17.    Pop the following heap.  Draw the resulting heap.  (4 points)

 

49

 

56

 

 

 

 

 

 

 

 

 

 

 


18.    Perform the make-heap algorithm on the following vector.  Give the resulting heap in tree form (4 points) and in vector form (2 points).  (6 points total)

 

20

97

19

61

27

40

92

80

28

49

60

 

 

Tree form:  (use scratch paper to work this out – turn it in for possible partial credit if you answer is incorrect.)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Vector form:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

19.    Consider a complete binary tree.  This type of tree can be implemented with an array (or a vector).  For the node located at position i of the array (or vector), where i is the subscript relative to 0, what is the subscript of the following:  (3 points)

 

parent ____________

 

left-child _____________

 

right-child ______________

 

0


20.     Given the following character frequencies, create the Huffman Tree. (6 points)

 

a: 100

e: 600

i: 75

n: 500

r: 200

t: 50

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

21.    Given the Huffman code for each character. (2 points)

 

a: ______________

e: ______________

i: ______________

n: ______________

r: ______________

t: ______________

 

22.    Using the Huffman Tree that you created in the previous question, encode the word ‘train’.  (2 points)

 

 

 

 


23.    In open-address hashing, with the quotient-offset collision handler, insert the following keys into a hash table of size 11:  (6 points)

 

15  12  48  92  68  33  41  11

 

Here are the relevant remainders and quotients:

 

key

key % 11

key / 11

15

4

1

12

1

1

48

4

4

92

4

8

68

2

6

33

0

3

41

8

3

121

0

11

 

 

Hash table:

 

 

 

 

 

 

 

 

 

 

 

 

0

1

2

3

4

5

6

7

8

9

10