Name  _____________________________

 

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

 

 

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

 

 

balanced binary search tree

insert

 

 

find

 

 

begin

 

 

[ ]  (map class only)

 

 

Priority Queue

 

 

Heap (complete binary tree implemented with a vector)

push

 

 

pop

 

 

make_heap

 

 

Sorts

vector  (values are already in the vector)

insertion sort

 

 

tree sort

 

 

heap sort

 

 

quicksort

 

 

Hashing

fixed size vector of buckets

insert

 

 

find

 

 

 

 

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


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

 

                                Tree                                    Insert                      Case #                        Resulting Tree

 

 

 

 

 

                                                                               100

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                65

 

 


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

 

 

 

 

 

 

 

 

 

 

 

 

5.        Insert (push) the value 98 into the following heap.  Draw the resulting heap.  (4 points)

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 




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

 

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

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

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

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

d.       all of the above

 

8.        The underlying data structure for the set, multiset, map, and multimap classes is which of the following?  (3 points)

a.        vector

b.       red-black tree

c.        heap

d.       priority queue

 

9.        You’re putting together a computer lab and want to give a unique name to each workstation.  As you and your friends come up with names, you want to collect them into a data structure.  Since each workstation must have a unique name, you don’t want to have names stored more than once.  Which of the following STL data structures would be most appropriate to hold the strings?  (3 points)

a.        set

b.       multiset

c.        map

d.       multimap

 

10.     You are writing a program for an automatic teller machine (ATM).  You have a structure defined for each customer, each of which has a unique account number.  When a customer inserts his/her card into an ATM, you want to locate their balance information by using the account number that’s on the card.  Which of the following STL data structures would be most appropriate to hold the customer information?   (3 points)

a.        set

b.       multiset

c.        map

d.       multimap

 

11.     We saw several sample programs illustrating the various sorting algorithms.  When sorting structures, we need to overload the less than (<) operator so that the sort function in the Standard Template Library could be used.  Which of the following functions properly overloads the less than operator if we want to sort student structures by id within name?  (That is, if we have two John Does, the one with the lower id number would appear first.)  (3 points)

a.        bool operator < (student s1, student s2)

{

   return ((s1.name < s2.name) && (s1.id < s2.id));

}

b.     bool operator < (student s1, student s2)

{

   return ((s1.name < s2.name) || (s1.id < s2.id));

}

c.        bool operator < (student s1, student s2)

{

   return ((s1.name < s2.name) || (s1.name == s2.name && s1.id < s2.id));

}

d.        bool operator < (student s1, student s2)

{

   return ((s1.name < s2.name && s1.id < s2.id) || (s1.name == s2.name));

}

 


12.     To implement tree sort using the Standard Template Library, we can use the _______ class.  (3 points)

a.       set

b.       multiset

c.        map

d.       multimap

e.        All of the above.

f.         None of the above.

 

 

13.     Heap sort uses the following process to sort a vector already loaded with n integers:  (3 points)

a.        pushes the items into a red-black tree, then uses an inorder traversal

b.       iteratively compares vector entries, performing rotations on those that are out of order

c.        performs make_heap on the vector followed by sort_heap

d.       none of the above, because we cannot use heapsort to sort a vector, only heaps

 

 

14.     Perform 2 iterations of quicksort on the following vector.  (5 points)

 

10

50

20

70

80

60

17

15

90

35

 

 

 

 

 

After 1st iteration:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

After 2nd iteration:

 

 

 

 

 

 

 

 

 

 

 

 

 


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

 

a: 900

c: 400

e: 1100

n: 800

r: 300

t: 500

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

16.     Using the Huffman Tree that you created in the previous question, encode the word ‘rent’.  (4 points)

 

 

 

 


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

 

20  33  49  26  42  27  40  51

 

Here are the relevant remainders and quotients:

 

key

key % 11

key / 11

20

9

1

33

0

3

49

5

4

26

4

2

42

9

3

27

5

2

40

7

3

51

7

4

 

 

Hash table:

 

 

 

 

 

 

 

 

 

 

 

 

0

1

2

3

4

5

6

7

8

9

10