Questions Chapter 11

Question 1

Using big O notation, how long does it take (ideally) to find an item in a hash table

Answer 1

O(1)

Question 2

A ______ ______ transforms a range of key values into a range of index values

Answer 2

hash function

Question 3

Using the next available position after an unsuccessful probe is called:

Answer 3

linear probing

Question 4

What are the first five step sizes in quadratic probing?

Answer 4

x+1^2, x+2^2, x+3^2, x+4^2, x+5^2

Question 5

Secondary clustering occurs because:

a. many keys hast to the same location
b. the sequence of step lengths is always the same
c. too many items with the same key are inserted
d. the hash function is not perfect

Answer 5

b. the sequence of step lengths is always the same

Question 6

Separate chaining involves a _________ at each location in the hash table.

Answer 6

linked list at each location in the hash table

Question 7

A reasonable load factor in separate chaining is:

Answer 7

1

Question 8

True or False: A possible hash function for strings involves multiplying each character by an ever-increasing power

Answer 8

True

Question 9

The best technique when the amount of data is not well-known is:

a. linear probing
b. quadratic probing
c. double hashing
d. separate chaining

Answer 9

d. separate chaining

Question 10

If digit folding is used in a hash function, the number of digits in each group should reflect:

Answer 10

the size of the array

Question 11

True or False: In linear probing, an unsuccessful search takes longer than a successful search

Answer 11

True

Question 12

In separate chaining, the time to insert a new item

a. increases linearly with the load factor
b. is proportional to the number of items in the table
c. is proportional to the number of lists
d. is proportional to the percentage of full cells in the array

Answer 12

a. increases linearly with the load factor

Question 13

True or False: In external hashing, it’s important that the blocks don’t become full.

Answer 13

False

Question 14

In external hashing, all records with keys that hash to the same value are located in _________________

Answer 14

the same block

Question 15

The hashing of a key to an already filled array-cell is called:

Answer 15

a collision

Question 16

collisions can be handled in two major ways:

Answer 16

open addressing and separate chaining

Question 17

Three kinds of open addressing for hash tables:

Answer 17

linear probing, quadratic probing, double hashing

Question 18

In linear probing, the step size is always __, so if x is the array index calculated by the hash function, the probe goes to _____

Answer 18

x, x+1, x+2…

Question 19

In linear probing, contiguous sequences of filled cells appear. They are called _______ ________ and reduce performance

Answer 19

primary clusters

Question 20

In quadratic probing, the offset from x is the square of the step number, so the probe goes to x, ____, ____, ____…

Answer 20

x+1, x+4, x+9

Question 21

If the secondary hash function returns a value of s in double hashing, the probe goes to x, ____, ____, ____…

Answer 21

x+s, x+2s, x+3s

Question 22

The load factor of a hash table is:

Answer 22

the ratio of data items to array size