Deck 14: Multi-Way Search Trees

Question 1

In hashing, elements are stored in a hash table, with their _________ in the table determined by a hashing function.

A) Order
B) Location
C) Precedence
D) None of the above

Answer 1

Location

Question 2

The situation where two elements or keys map to the same location in the table is called a __________.

A) Collision
B) Tie
C) Chaining
D) None of the above

Answer 2

Collision

Question 3

A hashing function that maps each element to a unique position in the table is said to be a _________ hashing function.

A) Good
B) Practical
C) Perfect
D) None of the above

Answer 3

Perfect

Question 4

Extraction involves using _________ of the element's value or key to compute the location at which to store the element.

A) All
B) Only a part
C) None
D) None of the above

Question 5

The __________ method is very effective when dealing with an unknown set of key values.

A) Division
B) Extraction
C) Shift Folding
D) Length Dependent

Question 6

In the shift folding method, the parts of the key are _______ together to create the index.

A) Added
B) Subtracted
C) Multiplied
D) None of the above

Question 7

The _____________ method and the mid-square method may also be effectively used with strings by manipulating the binary representations of the characters in the string.

A) Division
B) Extraction
C) Shift Folding
D) Length Dependent

Question 8

The chaining method for handling __________ simply treats the hash table conceptually as a table of collections rather than as a table of individual cells.

A) Division
B) Extraction
C) Collisions
D) Chaining

Question 9

The open addressing method for handling collisions looks for another open position in the table other than the one to which the element is originally hashed.

A) Chained
B) Hashed
C) Extracted
D) Added

Question 10

The ____________ is the maximum percentage occupancy allowed in the hash table before it is resized.

A) Load Factor
B) Hashing Factor
C) Thrashing Limit
D) None of the above

Question 11

In hashing, elements are stored in a hash table, with their location in the table determined by a ______.

Question 12

The situation where two elements or keys map to the same location in the table is called a ______.

Question 13

A hashing function that maps each element to a ______ in the table is said to be a perfect hashing function.

Question 14

______ involves using only a part of the element's value or key to compute the location at which to store the element.

Question 15

The division method is very effective when dealing with an ______ set of key values.

Question 16

In the ______ method, the parts of the key are added together to create the index.

Question 17

The ______ method for handling collisions simply treats the hash table conceptually as a table of collections rather than as a table of individual cells.

Question 18

The ______ method for handling collisions looks for another open position in the table other than the one to which the element is originally hashed.

Question 19

The load factor is the ______ percentage occupancy allowed in the hash table before it is resized.

Question 20

In hashing, elements are stored in a hash table, with their location in the table determined by a hashing function.

Question 21

The situation where two elements or keys map to the same location in the table is called a collision.

Question 22

A hashing function that maps each element to a unique position in the table is said to be an ideal hashing function.

Question 23

Extraction involves using only a part of the element's value or key to compute the location at which to store the element.

Question 24

The division method is not very effective when dealing with an unknown set of key values.

Question 25

In the shift folding method, the parts of the key are added together to create the index.

Question 26

The length-dependent method and the mid-square method must not be used with strings.

Question 27

Java provides a hashcode method for all objects.

Question 28

The chaining method for handling collisions simply treats the hash table conceptually as a table of individual cells rather than as a table of collections.

Question 29

The open addressing method for handling collisions looks for another open position in the table other than the one to which the element is originally hashed.

Question 30

The load factor is the minimum percentage occupancy allowed in the hash table before it is resized.

Question 31

What is the difference between a hash table and the other collections we have discussed?

Question 32

What is a collision in a hash table?

Question 33

What is our goal for a hashing function?

Question 34

What is the consequence of not having a good hashing function?

Question 35

What is the extraction method?

Question 36

What is the division method?

Question 37

What is the shift folding method?

Question 38

What is the boundary folding method?

Question 39

What is the mid-square method?

Question 40

What is the radix transformation method?

Question 41

What is the digit analysis method?

Question 42

What is the length-dependent method?

Question 43

What is chaining?

Question 44

What is open addressing?

Question 45

What are linear probing, quadratic probing, and double hashing?

Question 46

Why is deletion from an open addressing implementation a problem?

Question 47

What is the load factor and how does it affect table size?