Short Answers Short Answers Section 11.1 Serial Search and Binary Search Here is

Question

Short Answers

Short Answers
Section 11.1
Serial Search and
Binary Search Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Suppose that we are doing a serial search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Suppose that we are doing a binary search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.Suppose that an open-address hash table has a capacity of 811 and it contains 81 elements. What is the table's load factor? (An appoximation is fine.)

Multiple Choice

Multiple Choice
Section 11.1
Serial Search and
Binary Search What is the worst-case time for serial search finding a single item in an array?

• A. Constant time
• B. Logarithmic time
• C. Linear time
• D. Quadratic time

What is the worst-case time for binary search finding a single item in an array?

• A. Constant time
• B. Logarithmic time
• C. Linear time
• D. Quadratic time

What additional requirement is placed on an array, so that binary search may be used to locate an entry?

• A. The array elements must form a heap.
• B. The array must have at least 2 entries.
• C. The array must be sorted.
• D. The array's size must be a power of two.

Multiple Choice
Section 11.2
Open-Address
Hashing What is the best definition of a collision in a hash table?

• A. Two entries are identical except for their keys.
• B. Two entries with different data have the exact same key.
• C. Two entries with different keys have the same exact hash value.
• D. Two entries with the exact same key have different hash values.

Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:

• A. Hash table size should be the product of two primes.
• B. Hash table size should be the upper of a pair of twin primes.
• C. Hash table size should have the form 4K+3 for some K.
• D. Hash table size should not be too near a power of two.

In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which method has a better implementation because of this difference?

• A. put
• B. containsKey
• C. remove
• D. size
• E. Two or more of the above methods

What kind of initialization needs to be done for an open-address hash table?

• A. None.
• B. The key at each array location must be initialized.
• C. The head pointer of each chain must be set to null.
• D. Both B and C must be carried out.

Multiple Choice
Section 11.3
Chained
Hashing What kind of initialization needs to be done for an chained hash table?

• A. None.
• B. The key at each array location must be initialized.
• C. The head pointer of each chain must be set to null.
• D. Both B and C must be carried out.

A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

• A. 256
• B. 511
• C. 512
• D. 1024
• E. There is no maximum.

Multiple Choice
Section 11.4
Time Analysis
of Hashing Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

• A. s + m
• B. s - m
• C. m - s
• D. m * s
• E. m / s

Multiple Choice

Multiple Choice
Section 11.1
Serial Search and
Binary Search What is the worst-case time for serial search finding a single item in an array?

• A. Constant time
• B. Logarithmic time
• C. Linear time
• D. Quadratic time

What is the worst-case time for binary search finding a single item in an array?

• A. Constant time
• B. Logarithmic time
• C. Linear time
• D. Quadratic time

What additional requirement is placed on an array, so that binary search may be used to locate an entry?

• A. The array elements must form a heap.
• B. The array must have at least 2 entries.
• C. The array must be sorted.
• D. The array's size must be a power of two.

Multiple Choice
Section 11.2
Open-Address
Hashing What is the best definition of a collision in a hash table?

• A. Two entries are identical except for their keys.
• B. Two entries with different data have the exact same key.
• C. Two entries with different keys have the same exact hash value.
• D. Two entries with the exact same key have different hash values.

Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:

• A. Hash table size should be the product of two primes.
• B. Hash table size should be the upper of a pair of twin primes.
• C. Hash table size should have the form 4K+3 for some K.
• D. Hash table size should not be too near a power of two.

In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which method has a better implementation because of this difference?

• A. put
• B. containsKey
• C. remove
• D. size
• E. Two or more of the above methods

What kind of initialization needs to be done for an open-address hash table?

• A. None.
• B. The key at each array location must be initialized.
• C. The head pointer of each chain must be set to null.
• D. Both B and C must be carried out.

Multiple Choice
Section 11.3
Chained
Hashing What kind of initialization needs to be done for an chained hash table?

• A. None.
• B. The key at each array location must be initialized.
• C. The head pointer of each chain must be set to null.
• D. Both B and C must be carried out.

A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

• A. 256
• B. 511
• C. 512
• D. 1024
• E. There is no maximum.

Multiple Choice
Section 11.4
Time Analysis
of Hashing Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

• A. s + m
• B. s - m
• C. m - s
• D. m * s
• E. m / s

Short Answers
Section 11.1
Serial Search and
Binary Search

Explanation / Answer

1, 2 element will be found by by examining two or fewer numbers from the array. if we are seaching element from array index 0 onwords forward seaching

14, 15 element will be found by by examining two or fewer numbers from the array.

1. What is the worst-case time for serial search finding a single item in an array?

Linear time since we are searching the element one by one.

2. What is the worst-case time for binary search finding a single item in an array?

Logarithmic time since each time we dividind the array into half.

3. What additional requirement is placed on an array, so that binary search may be used to locate an entry?

The array must be sorted.

4. What is the best definition of a collision in a hash table?

Two entries with different keys have the same exact hash value.

5. Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:

Hash table size should not be too near a power of two.

6. In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which method has a better implementation because of this difference?

remove since we deleting the item which is not used.

7. What kind of initialization needs to be done for an open-address hash table?

None

8. What kind of initialization needs to be done for an chained hash table?

Both B and C must be carried out.

9. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

There is no maximum.

10. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

m / s

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.