Wednesday, November 14, 2001                                                         Name:____________________

 

CSE 326 Autumn 2001

Quiz 3

 

  1. (3 points)  Define the heap order property for binary heaps (assume a min heap).

                                                            

 

 

  1. (3 points)  Define the structure property for binary heaps.

 

 

 

  1. Printing out all elements of a binary heap in sorted order.

 

a)       (3 points)  Write the function printAll(), to print out all of the elements of a binary heap in ascending sorted order.  (Assume the heap data type exposes the methods insert(), deleteMin(), isEmpty(), and that you also have available a helper function, print(), which accepts an element and prints it out.)

void printAll(BinaryHeap heap)

 

 

 

 

 

 

b)      (1 point)  What is the time complexity of extracting all N elements in sorted order from a binary heap?

 

 

  1. Time complexity of heap merging.

a)      (2 point)  What is the time complexity of merging two binary heaps whose sizes total N?  (Hint: concatenate the heap arrays, then run BuildHeap.)

 

b)      (2 point)  What is the time complexity of merging two leftist heaps whose sizes total N?

 

 

  1. (2 points)  Which expression most accurately bounds the number of disk accesses in a typical B-Tree operation?  (M represents the branching factor, L the leaf capacity, N the number of data items, and h the tree height.)

a)      O(M)

b)      O(L)

c)      O(N)

d)      O(h)

e)      O(M*L)

 

  1. (4 points)  Circle the data structure which best supports the given operation (i.e. enables the fastest possible runtime).  Assume the heaps are min heaps.  BST = binary search tree.

 

 

 

 

 

 

Operation

BST

B-Tree

binary heap

leftist heap

hash table

Find the maximum key value in an in-memory data set.

BST

B-Tree

binary heap

leftist heap

hash table

Find a given key value in constant time.

BST

B-Tree

binary heap

leftist heap

hash table

Merge two heaps.

BST

B-Tree

binary heap

leftist heap

hash table

Manage a large, disk-based data set.

 

  1. (6 points)  True or false?

 

True

False

The load factor l of a hash table must always be £ 1.

True

False

Separate chaining requires the use of a collision resolution function.

True

False

The expected cost of a successful search when using separate chaining is approximately 1 + l/2.

True

False

The expected cost of an unsuccessful search when using separate chaining is approximately 1/l.

True

False

Primary clustering is a problem which can occur with either linear probing or quadratic probing.

True

False

Double hashing avoids the problems of primary and secondary clustering.

 

  1. (2 points) Universal hashing is a mechanism for:

a)      Randomly choosing hash functions at runtime, in between insert, find and delete operations.

b)      Resolving collisions when using separate chaining.

c)      Guaranteeing that our chances of collision are no worse than if we get to choose hash table entries at random.

d)      Ensuring that the load factor l always remains within the range ½ £ l £ 1.

e)      Channeling web traffic to http://www.burgerking.com/jobs.

 

  1. (2 points) Double hashing is a mechanism for:

a)      Randomly choosing hash functions at runtime, in between insert, find and delete operations.

b)      Resolving collisions when using open addressing.

c)      Guaranteeing that our chances of collision are no worse than if we get to choose hash table entries at random.

d)      Ensuring that the load factor l always remains within the range ½ £ l £ 1.

e)      Moving elements into a new hash table when the original hash table gets too full.

 

  1. You are given the following hash table, hash function, and set of keys to insert.  (You are also given the look-up table, so you don’t have to calculate hash function values in your head :-)

q       Table size: 7

q       Hash function: ((4k + 3) mod 17) mod 7

q       Keys to insert: {16, 5, 17, 2, 4}

 

 

 

 

 

 

 

k

h(k)

 

 

 

 

 

 

1

0

 

 

 

 

 

 

2

4

 

 

 

 

 

 

3

1

 

 

 

 

 

 

4

2

 

(a)

 

 

(b)

 

5

6

0

 

 

0

 

 

6

3

1

 

 

1

 

 

7

0

2

 

 

2

 

 

8

1

3

 

 

3

 

 

9

5

4

 

 

4

 

 

10

2

5

 

 

5

 

 

11

6

6

 

 

6

 

 

12

0

 

 

 

 

 

 

13

4

 

 

 

 

 

 

14

1

 

 

 

 

 

 

15

5

 

 

 

 

 

 

16

2

 

 

 

 

 

 

17

3

 

 

 

 

 

 

18

0

 

 

 

 

 

 

19

4

 

 

 

 

 

 

20

1

 

 

 

 

 

 

21

2

 

 

 

 

 

 

22

6

 

 

 

 

 

 

23

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a)      (3 points)  Show the results of inserting all of the given keys in the stated order into hash table (a) using separate chaining.

 

b)      (3 points)  Show the results of inserting all of the given keys in the stated order into hash table (b) using open addressing with quadratic probing.

 

c)      (2 points)  If any of your insertions failed, state whether the failure(s) occurred in (a) or (b), and which key(s) failed to insert.  If none of your insertions failed, write None.

 

 

d)      (2 points)  If any of your insertions failed, suggest a different collision resolution technique that could prevent the specific failure(s) you encountered.  If none of your insertions failed, write N/A.

 

 

 

  1. (5 points Extra credit)  The total capacity of a B-Tree is the maximum number of data items which the B-Tree can store.  Write an expression for the total capacity of a B-Tree, N, as a function of the branching factor M, the leaf capacity L, and the tree height h.