Two Marks Questions with Answers

Two Marks Questions with Answers

 

Q.1 What is hashing?

AU: May-16

Ans. :

Hashing is a technique of storing the elements directly at the specific location in the hash table. The hashing makes use of hash function to place the record at its position. Using the same hash function the data can be retrieved directly from the hash table.

 

Q.2 List out the various techniques of hashing.

Ans. :

Various techniques of hashing are -

1. Division method 2. Mid square method 3. Multiplicative hash function

4. Digit folding 5. Digit analysis.

 

Q.3 What is uniform hash function ?

Ans. : An uniform hash function is one that equally distributes data items over the whole hash table data structure.

 

Q.4 What is rehashing ?

AU: Dec.-15

Ans. :

Rehashing is a technique in which the table is resized. That means the size of the table is doubled by creating a new table. The total size of the table is usually a prime number. Following are the situations in which the rehashing is required -

1. When table is completely full.

2. With quadratic probing the table is filled half.

3. When insertions fail due to overflow.

 

Q.5 What is collision in hashing ?

Ans. :  The situation in which the hash function returns the same hash key for more than one record is called collision.

 

Q.6 What is overflow in hashing?

Ans. : The situation in which there is no room for a new pair in the hash table is called overflow.

 

Q.7 What are the characteristics of good hashing function?

Ans. : Refer section 6.3

 

Q.8 What is the major problem in linear probing ?

Ans. : One major problem in linear probing is primary clustering. Primary clustering is the process in which a block of data is formed in the hash table when collision is resolved.

 

Q.9 What are the advantages of rehashing ?

Ans. : Following are the advantages -

1. This technique provides the programmer a flexibility to enlarge the table size if required.

2. Only the space gets doubled with simple hash function which avoids occurrence of collisions.

 

Q.10 What is the advantage of chained hash table over open addressing scheme ?

Ans. : The deletion of particular record from the hash function becomes easier.

 

Q.11 State some major drawback of chaining.

Ans. : Requirement of additional data structure is the major drawback of chaining.

 

Q.12 Specify the hashing technique in which the table size can be changed.

Ans. : The rehashing is a hashing technique in which the table size can be changed.

 

Q.13 What will be the position of the number 3111 in a hash table, when the mid square method is applied ? (The table size is 1000)

Ans. : The position will be 783 because (3111)² = 9678321.

 

Q.14 Which hash function maintains the record in order of hash field values ?

Ans. : The folding method maintains the record in order of hash field values.

 

Q.15 Enlist the conditions in which the rehashing is required.

Ans. : The rehashing is required in following conditions -

1. Table is completely full.

2. Insertion fails due to overflowing.

3. When there is a need to transfer the contents from old hash table to new hash table.

 

Q.16 What do you understand by collision resolution by chaining ?

Ans. : When collision happens we create a new memory location outside the existing table and use a chain to link to the new memory location.

 

Q.17 Use of pointer is in ----- hashing technique.

Ans. : chaining.

 

Q.18 What are the advantages and disadvantages of separate chaining and linear probing?

Ans. : 1) Separate chaining:

Advantages:

i) It is simple to implement.

ii) Hash table never fills and we can add elements in the linked list fashion.

 iii) The meaning of hash function can be preserved.

Disadvantages:

i) It requires extra space to maintain links.

ii) If the chain becomes too long then it takes more time to search an element.

iii) There may be wastage of space as some parts of hash table are never used.

2) Linear probing:

Advantage:

1) It is faster due to locality of references.

Disadvantage:

1) It forms primary clustering. Hence only some part of hash table remain occupied bim and other part remains vaccant.