Name  _____________________________

 

CPTR247  Fall '12  (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:

                            for constant time – O(1)

                            for logarithmic time – O(log2n)

                            for linear time – O(n)

                            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

size

 

 

find

 

 

 

 

 

AVL trees

 

 

balanced binary search tree

insert

 

 

height

 

 

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

 

 

balanced binary search tree

insert

 

 

begin

 

 

erase

 

 

[ ]  (map class only)

 

 

Priority Queue

 

 

Heap (complete binary tree implemented with a vector)

push

 

 

pop

 

 

make_heap

 

 

Hashing

fixed size vector of buckets – linked list implementation

insert

 

 

find

 

 

 

 

2.       True/False  Circle T is the statement is always true, F otherwise.  (8 points - 1 point each)

 

T  F  The smallest number of nodes for a two tree of height 3 is 5.

T  F  The largest number of nodes for a complete binary tree of height 3 is 15.

T  F  The largest value in a binary search tree will be found at the rightmost leaf.

T  F  The underlying data structure for a multimap is a complete binary tree.

T  F  The number of nodes in a binary tree is equal to the number of nodes in the root’s left subtree plus the number of nodes in the root’s right subtree plus one.

T  F  The efficiency of a hash data structure may be improved by increasing the number of buckets it has.

T  F  The value of the postfix expression “ 10 2 2 / +” is 7.

T  F  The value of the postfix expression “ 10 2 / 2 +” is 7.


3.       Give the two key features that distinguish arbitrary binary search trees from trees in general.  (3 points) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Explain how the insert method works in arbitrary binary search trees and why worstTime(n) is O(n).

 

        how (4 points):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

        why (2 points):

 

 

 

 

 

 

 

 

 

 

 

 

 


4.       Define AVL tree.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

5.       Why are AVL trees and Red-black trees better than arbitrary binary search trees.  Give a complete an answer as possible.  (2 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.       Define heap.  (4 points)

 

 

 


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

 

 

 

 

                                                                                85                        _______

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                 8                         _______

 

 


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

 

8.       Your local take-out pizza place has decided that it will become more profitable if it can add a “personal touch” to its customer service.  In particular, they’ve observed that a lot of people place the same order every time they call, so they’ve decided that when a customer calls, the order-taking person should ask, “Do you want the usual?”  To support this, we need to write a program that will take the customer’s phone number (available because of caller id) and determine the last order placed from this phone number.  If the phone number has never been used to place an order before, the program should indicate so.  What data structure is best to hold this information?  (3 points)

 

a.       set

b.       multiset

c.        map

d.       multimap

 

 

9.       The largest possible number of nodes in a binary tree of height h is _____.  (2 points)

 

a.       2h

b.       2h - 1

c.        2h-1 + 1

d.       2h+1 - 1

 

 

10.    The smallest possible number of nodes in a binary tree of height h is _____.  (2 points)

 

a.       1

b.       h

c.        h + 1

d.       h  - 1

 

 

11.    Consider the following code:

typedef map< int, string > mymap;

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

 

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

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

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

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

 

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

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

 

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

a.       Ethel Lucy Ricky Fred

b.       Fred Ethel Ricky Lucy

c.        Ethel Fred Lucy Ricky

d.       none of the above

 

 

12.    The AVL tree of height h with the minimum number of nodes possible has two subtrees.  Which of the following best describes the heights of those subtrees.  (3 points)

 

a.       h-1 for both

b.       h-1 for one and h-2 for the other

c.        h-1 for one and either h-1 or h-2 for the other

d.       there’s no way to know


13.    If the pop method is called on the following heap, what value would be removed?  _______________. (1 point)   

 

Draw the resulting heap in the open area to the right.  (3 points)

 

 

 

 

 

 

 

 

 

 

14.    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)

 

67

24

8

25

19

54

68

80

43

62

78

56

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Vector form:

 

 

 

 

 

 

 

 

 

 

 

 

 

 


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

 

a: 400

d: 750

e: 1000

r: 600

s: 100

t: 350

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

a: ______________

d: ______________

e: ______________

r: ______________

s: ______________

t: ______________

 

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

 

 

 

 


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

 

42  38  27  99  121  58  86

 

Here are the relevant remainders and quotients:

key

key % 11

key / 11

42

9

3

38

5

3

27

5

2

99

0

9

121

0

11

58

3

5

86

9

7

 

 

 

Hash table:

 

 

 

 

 

 

 

 

 

 

 

 

0

1

2

3

4

5

6

7

8

9

10