Name  _____________________________

 

CPTR247  Fall '08  (100 points)                                                                                          Exam 2

 

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

insert

 

 

find

 

 

begin

 

 

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

 

 

balanced binary search tree

insert

 

 

find

 

 

erase

 

 

Priority Queue

 

 

heap (complete binary tree implemented with a vector)

push

 

 

pop

 

 

top

 

 

make_heap

 

 

Hashing

double hashing (quotient-offset collision)

insert

 

 

find

 

 

 

 

2.       Explain why the size and empty methods for all containers that we’ve studied are O(1).  (4 points)


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

 

 

 

 

 

 

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

 

 

 

 

 

 

5.       What is the smallest number of nodes in a full tree of height 3?  (2 points)

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

7.       Explain how the [ ] operator for the map class works and why its averageTime(n) and worstTime(n) is O(log n).  Include in your description what the [ ] operator returns.  (5 points)

 

 

 


8.       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

 

 

 

 

 

                                                                                52                           ____

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                29                           ____

 

 


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

 

9.       Your relatives and friends will be calling soon to find out what you would like for Christmas, so you need to put together your Christmas wish list.  You have decided that you need to write a computer program to manage the information. You’re going to come up with one gift suggestion to give each person, and when they call, you want to enter their name into your program and have it display the gift suggestion you’re going to give them.  What data structure is best to hold the necessary information?  (3 points)

a.       set

b.       multiset

c.        map

d.       multimap

 

10.    Consider the following code:

typedef map< int, string > mymap;

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

 

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

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

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

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

 

for (itr = mymap.begin(); itr != mymap.end(); itr++)

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

 

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

a.       Fred Ethel Ricky Lucy

b.       Ethel Fred Lucy Ricky

c.        Lucy Ethel Ricky Fred

d.       Lucy Ricky Ethel Fred

 

11.    The default underlying data structure for a set is a _______.  (3 points)

a.       vector

b.       binary search tree

c.        red-black tree

d.       linked list

 

12.    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

 

13.    Which of the following statements is false?  (3 points)

a.       A full tree is a complete tree.

b.       A complete tree is a full tree.

c.        A full tree is a two tree.

d.       None of the above.

 

14.    Why are AVL trees and red-black tress better than arbitrary binary search trees?  (3 points)

a.       their height is always logarithmic in n (the number of nodes)

b.       the insert method does not need to reach the leaf level before the node can be inserted

c.        they avoid the “bushy-ness” of arbitrary binary search trees

d.       all of the above

 

15.    The defining characteristic of an AVL tree is which of the following?  (3 points)

a.       the value at every node is greater than the values of its children

b.       for every node, all nodes in its left subtree are greater than that of the node and all nodes in its right subtree are less than or equal to it

c.        the height of the subtrees of every node differ by at most one

d.       the number of nodes in the subtrees of every node differ by at most one


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

 

49

 

46

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

49

 

46

 
     

 

 

 

 

 

 

 


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)

 

14

17

26

15

44

42

89

47

28

49

60

 

 

Tree form:  (Show your work for possible partial credit if your answer is incorrect.)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Vector form:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


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

 

a: 90                    (Show your work for possible partial credit if your answer is incorrect.)

e: 140

h: 75

n: 125

p: 60

y: 50

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

a: ______________

e: ______________

h: ______________

n: ______________

p: ______________

y: ______________

 

21.    Using the Huffman Tree that you created in the previous question, encode the word “happy”.  (2 points)

 

 

 

 


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

 

15  42  41  37  68  39  29  48

 

Here are the relevant remainders and quotients:

 

key

key % 13

key / 13

15

2

1

42

3

3

41

2

3

37

11

2

68

3

5

3

3

0

29

3

2

63

11

4

 

 

Hash table:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

2

3

4

5

6

7

8

9

10

11

12