Name  _____________________________

 

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

                    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

 

 

end

 

 

AVL trees

 

 

balanced binary search tree

insert

 

 

height

 

 

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

 

 

balanced binary search tree

insert

 

 

find

 

 

[ ]  (map class only)

 

 

Priority Queue

 

 

Heap (complete binary tree implemented with a vector)

push

 

 

pop

 

 

make_heap

 

 

Hashing

double hashing

insert

 

 

find

 

 

 

 

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

 

T  F  The default underlying data structure for a map is a set.

T  F  The default underlying data structure for a heap is a vector.

T  F  The height of a binary tree with three nodes is 1.

T  F  The largest value in a binary search tree may be found at the root.

T  F  The node at the root of a heap contains the largest value.

T  F  A full tree is also a complete tree.

T  F  The efficiency of a hash data structure relies solely on the number of buckets it has.

T  F  The value of the postfix expression “ 8 2 4 + -” is 6.

T  F  Every non-empty binary tree has at least one leaf.


3.        Answer the following questions regarding this arbitrary binary tree: 

 

 

                

                       

 

 

List the nodes as they would be processed in a breadth-first search: (2 points)

 

 

 

 

 

 

List the nodes as they would be processed in a preorder traversal: (2 points)

 

 

 

 

 

 

List the nodes as they would be processed in an inorder traversal: (2 points)

 

 

 

 

 

 

List the nodes as they would be processed in a postorder traversal: (2 points)


4.        Explain how the find method of the binary search tree class works.  (4 points) 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Explain why the averageTime(n) for the find method of the binary search tree is different from the worstTime(n).  (4 points)

 

 

 


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

 

 

 

 

 

                                                                                10

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                75

 

 


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

 

6.        Santa is getting ready for Christmas Eve.  He’s making his list, made up of the children’s names, each with an accompanying string that says either “naughty” or “nice.”  He wants to be able to enter a child’s name into the computer, and then have the children with that name (there may be duplicates) come up on the screen, each with the word “naughty” or “nice” next to it.  He’s hired you as his CIE (chief information elf) to write the program.  What data structure is best to hold this information?  (3 points)

 

a.        set

b.       multiset

c.        map

d.       multimap

 

 

7.        Mrs. Claus is busy baking cookies, and she makes a huge variety of cookies, each with a unique name.  The problem is that her memory isn’t what it used to be.  She wants to be able to enter the name of the cookie that she is about to make into her computer.  If she’s already made that kind, it should say so, at which point she’ll stop and make a different kind.  If she hasn’t already made that kind, she’ll go ahead and make them, and the computer should remember that.  What data structure is best to hold this information?  (3 points)

 

a.        set

b.       multiset

c.        map

d.       multimap

 

 

8.        Hermey the Elf is in charge of packing the sleigh.  He needs to keep a count of how many of each toy he has already placed into the sleigh.  Each toy has a unique name.  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 is h is _____.  (3 points)

 

a.        2h

b.       2h - 1

c.        2h-1 + 1

d.       2h+1 - 1

 

 

10.     The AVL tree of height h with the minimum number of nodes possible has two subtrees.  The height of those subtrees is _____.  (3 points)

 

a.        h-1 for both

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

c.        h-1 for one and at most that for the other

d.       none of the above


11.     Insert (push) the value 89 into the following heap.  Draw the resulting heap.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

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

 

50

43

88

16

24

44

78

12

67

79

10

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Vector form:

 

 

 

 

 

 

 

 

 

 

 

 

 


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

 

a: 300

c: 600

e: 1000

n: 800

r: 200

t: 900

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

a: ______________

c: ______________

e: ______________

n: ______________

r: ______________

t: ______________

 

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

 

 

 

 


16.     In open-addressing, with the offset-by-1 collision handler, insert the following keys into a hash table of size 11:  (6 points)

 

20  33  49  26  42  27  40  51 99 37

 

Here are the relevant remainders:

 

key

key % 11

20

9

33

0

49

5

26

4

42

9

27

5

40

7

51

7

99

0

37

4

 

 

Hash table:

 

 

 

 

 

 

 

 

 

 

 

 

0

1

2

3

4

5

6

7

8

9

10