[Solved] Hashing MCQ [Free PDF] - Objective Question Answer for Hashing Quiz - Download Now! (2024)

1. 5
2. 6
3. 7
4. 4

To insert a key into a hash table using open addressing with linear probing, we follow these steps:

1. Calculate the hash value of the key using the hash function.
2. If the calculated index is empty, insert the key at that index.
3. If the calculated index is occupied, probe linearly until an empty slot is found and insert the key at that slot.

Using the given hash function h(k) = k mod 9, we can calculate the hash value of each key as follows:

• h(22) = 22 mod 9 = 4
• h(28) = 28 mod 9 = 1
• h(23) = 23 mod 9 = 5
• h(12) = 12 mod 9 = 3
• h(13) = 13 mod 9 = 4

Steps -

• To insert the keys into the hash table using linear probing, we start by inserting key 22 at index 4.
• The next key, 28, is inserted at index 1 since index 4 is already occupied.
• The third key, 23, is inserted at index 5 since index 1 is occupied and index 4 is already occupied by key 22.
• The fourth key, 12, is inserted at index 3 since index 5 is occupied, index 1 is occupied by key 28, and index 4 is already occupied by key 22.
• Finally, when we try to insert the key 13, we calculate its hash value as h(13) = 4, which is the same as the hash value of key 22.
• Since index 4 is already occupied by key 22, we need to probe linearly to find the next available slot.
• We start at index 5 (next index after 4) and find that it is occupied by key 23.
• We continue probing linearly and find that the next available slot is index 6.Therefore, the key 13 is inserted at index 6.
• So the key 13 is inserted at index 6 in the hash table.

Get Started for Free

Trusted by 4.9 Crore+ Students

1. 4
2. 5
3. 6
4. 3

Linear Probing:In this technique, a hash table is searched for an element linearly. If the position is already occupied, it will check the next position for the element.

• The searching can start from any of the indexes, so we have to consider the index which will cover the maximum number of elements.
• If we consider index 8, we can see that we can cover indices 8, 9, 0, and 1.
• Linear probing will search for all these 4 indices which will need a comparison.
• Then it will compare the next index, where it will find the position to be empty.
• Hence, total 4 + 1 = 5 comparisons are needed.

Get Started for Free

Trusted by 4.9 Crore+ Students

1. Division method
2. Multiplication method
3. Folding method
4. Mid - square method

The correct solution is 'option 1'.

Key Points

The method of division is unfavorable because the hash table maps the consecutive keys to consecutive hash values. This results in poor efficiency.

Hence, the correct answer is theDivision method.

Additional Information

Mid - square method:

The key is squared and the address is selected from the middle of the result.

Folding method:

The key is divided into parts whose sizes match the size of the required address. Then the parts are added to obtain the address.

Multiplication method:

A hash function that uses the first p bits of the key times an irrational number.

Get Started for Free

Trusted by 4.9 Crore+ Students

1. B – Tree file
2. Hashed File
3. Indexed File
4. sequential File

Concept:

Hashing is file organization method which provides very fast access to records under certain search conditions. The organization is usually called a hash file. A hash function is used to derive the physical location of a record.

Explanation:

Search condition in this is a equality condition on a single field called hash field. Hash field is a key field of the file in which case it is called hash key. The idea behind hashing is to provide a function h called hash function which is applied to the hash field value of record and yields the address of the disk block in which record is stored.

A search for the record within the block can be carries out in a main memory buffer.

Hash function for a record will be as : h(k) = k mod m where k is the field value.

Two types of hashing:

1) Internal hashing: It is used whenever a group of record is accessed exclusively by using the value of one field. It is implemented by using a hash table through the use of array of records and a hash function.

2) External hashing: It is used for dynamically growing files. Hashing for disk files is called as external hashing. In this, target address is made of buckets each of which holds multiple records.

Get Started for Free

Trusted by 4.9 Crore+ Students

1. Collision
2. Root
3. Foreign Key
4. Records

Concept:

A data model is a collection of concepts that can be used to describe the structure of a database and provides the necessary means to achieve the abstraction. Types of data model are : hierarchical data model, network data model and relational model.

Explanation:

Hierarchical data model: In this data model, data is organized in the form of tree in which nodes represent the records and branches of tree represent the fields. Parent node or root of three have connection with its child nodes.

During search operation in this data model, search takes place from root and then moves to the children to reach the specific record. That means, searching always starts from root. If we use hashing function for the search operation than hashing function will locate the root of the model.

Diagram for hierarchical database model:

Get Started for Free

Trusted by 4.9 Crore+ Students

Hashing Question 6

Hashing Question 6 Detailed Solution

Data:

number of slots = 25

number of elements = 2000

Formula:

\({\rm{Load\;factor}}\left( {\rm{\alpha }} \right) = \frac{{{\rm{number\;of\;elements}}}}{{{\rm{number\;of\;slots}}}}{\rm{\;}}\)

Calculation:

\({\rm{Load\;factor}}\left( {\rm{\alpha }} \right) = \frac{{2000}}{{25}} = 80{\rm{\;}}\)

Get Started for Free

Trusted by 4.9 Crore+ Students

Hashing Question 7

1. 4
2. 5
3. 6
4. 3

Hashing Question 7 Detailed Solution

Linear Probing:In this technique, a hash table is searched for an element linearly. If the position is already occupied, it will check the next position for the element.

• The searching can start from any of the indexes, so we have to consider the index which will cover the maximum number of elements.
• If we consider index 8, we can see that we can cover indices 8, 9, 0, and 1.
• Linear probing will search for all these 4 indices which will need a comparison.
• Then it will compare the next index, where it will find the position to be empty.
• Hence, total 4 + 1 = 5 comparisons are needed.

Get Started for Free

Trusted by 4.9 Crore+ Students

Hashing Question 8

1. Collision
2. Root
3. Foreign Key
4. Records

Hashing Question 8 Detailed Solution

Concept:

A data model is a collection of concepts that can be used to describe the structure of a database and provides the necessary means to achieve the abstraction. Types of data model are : hierarchical data model, network data model and relational model.

Explanation:

Hierarchical data model: In this data model, data is organized in the form of tree in which nodes represent the records and branches of tree represent the fields. Parent node or root of three have connection with its child nodes.

During search operation in this data model, search takes place from root and then moves to the children to reach the specific record. That means, searching always starts from root. If we use hashing function for the search operation than hashing function will locate the root of the model.

Diagram for hierarchical database model:

Get Started for Free

Trusted by 4.9 Crore+ Students

Hashing Question 9

1. Division method
2. Multiplication method
3. Folding method
4. Mid - square method

Hashing Question 9 Detailed Solution

The correct solution is 'option 1'.

Key Points

The method of division is unfavorable because the hash table maps the consecutive keys to consecutive hash values. This results in poor efficiency.

Hence, the correct answer is theDivision method.

Additional Information

Mid - square method:

The key is squared and the address is selected from the middle of the result.

Folding method:

The key is divided into parts whose sizes match the size of the required address. Then the parts are added to obtain the address.

Multiplication method:

A hash function that uses the first p bits of the key times an irrational number.

Get Started for Free

Trusted by 4.9 Crore+ Students

Hashing Question 10

1. B – Tree file
2. Hashed File
3. Indexed File
4. sequential File

Hashing Question 10 Detailed Solution

Concept:

Hashing is file organization method which provides very fast access to records under certain search conditions. The organization is usually called a hash file. A hash function is used to derive the physical location of a record.

Explanation:

Search condition in this is a equality condition on a single field called hash field. Hash field is a key field of the file in which case it is called hash key. The idea behind hashing is to provide a function h called hash function which is applied to the hash field value of record and yields the address of the disk block in which record is stored.

A search for the record within the block can be carries out in a main memory buffer.

Hash function for a record will be as : h(k) = k mod m where k is the field value.

Two types of hashing:

1) Internal hashing: It is used whenever a group of record is accessed exclusively by using the value of one field. It is implemented by using a hash table through the use of array of records and a hash function.

2) External hashing: It is used for dynamically growing files. Hashing for disk files is called as external hashing. In this, target address is made of buckets each of which holds multiple records.

Get Started for Free

Trusted by 4.9 Crore+ Students

Data:

number of slots = 25

number of elements = 2000

Formula:

\({\rm{Load\;factor}}\left( {\rm{\alpha }} \right) = \frac{{{\rm{number\;of\;elements}}}}{{{\rm{number\;of\;slots}}}}{\rm{\;}}\)

Calculation:

\({\rm{Load\;factor}}\left( {\rm{\alpha }} \right) = \frac{{2000}}{{25}} = 80{\rm{\;}}\)

Get Started for Free

Trusted by 4.9 Crore+ Students

1. 4
2. 5
3. 6
4. 3

Linear Probing:In this technique, a hash table is searched for an element linearly. If the position is already occupied, it will check the next position for the element.

• The searching can start from any of the indexes, so we have to consider the index which will cover the maximum number of elements.
• If we consider index 8, we can see that we can cover indices 8, 9, 0, and 1.
• Linear probing will search for all these 4 indices which will need a comparison.
• Then it will compare the next index, where it will find the position to be empty.
• Hence, total 4 + 1 = 5 comparisons are needed.

Get Started for Free

Trusted by 4.9 Crore+ Students

1. Collision
2. Root
3. Foreign Key
4. Records

Concept:

A data model is a collection of concepts that can be used to describe the structure of a database and provides the necessary means to achieve the abstraction. Types of data model are : hierarchical data model, network data model and relational model.

Explanation:

Hierarchical data model: In this data model, data is organized in the form of tree in which nodes represent the records and branches of tree represent the fields. Parent node or root of three have connection with its child nodes.

During search operation in this data model, search takes place from root and then moves to the children to reach the specific record. That means, searching always starts from root. If we use hashing function for the search operation than hashing function will locate the root of the model.

Diagram for hierarchical database model:

Get Started for Free

Trusted by 4.9 Crore+ Students

1. 5
2. 6
3. 7
4. 4

To insert a key into a hash table using open addressing with linear probing, we follow these steps:

1. Calculate the hash value of the key using the hash function.
2. If the calculated index is empty, insert the key at that index.
3. If the calculated index is occupied, probe linearly until an empty slot is found and insert the key at that slot.

Using the given hash function h(k) = k mod 9, we can calculate the hash value of each key as follows:

• h(22) = 22 mod 9 = 4
• h(28) = 28 mod 9 = 1
• h(23) = 23 mod 9 = 5
• h(12) = 12 mod 9 = 3
• h(13) = 13 mod 9 = 4

Steps -

• To insert the keys into the hash table using linear probing, we start by inserting key 22 at index 4.
• The next key, 28, is inserted at index 1 since index 4 is already occupied.
• The third key, 23, is inserted at index 5 since index 1 is occupied and index 4 is already occupied by key 22.
• The fourth key, 12, is inserted at index 3 since index 5 is occupied, index 1 is occupied by key 28, and index 4 is already occupied by key 22.
• Finally, when we try to insert the key 13, we calculate its hash value as h(13) = 4, which is the same as the hash value of key 22.
• Since index 4 is already occupied by key 22, we need to probe linearly to find the next available slot.
• We start at index 5 (next index after 4) and find that it is occupied by key 23.
• We continue probing linearly and find that the next available slot is index 6.Therefore, the key 13 is inserted at index 6.
• So the key 13 is inserted at index 6 in the hash table.

Get Started for Free

Trusted by 4.9 Crore+ Students

1. Division method
2. Multiplication method
3. Folding method
4. Mid - square method

The correct solution is 'option 1'.

Key Points

The method of division is unfavorable because the hash table maps the consecutive keys to consecutive hash values. This results in poor efficiency.

Hence, the correct answer is theDivision method.

Additional Information

Mid - square method:

The key is squared and the address is selected from the middle of the result.

Folding method:

The key is divided into parts whose sizes match the size of the required address. Then the parts are added to obtain the address.

Multiplication method:

A hash function that uses the first p bits of the key times an irrational number.

Get Started for Free

Trusted by 4.9 Crore+ Students