HASHING

1) The function that transforms a key into a table index is called a _________

1. Hash function
2. Key function
3. Transformation function
4. Table function

Ans) A ,

Function that transforms key to table index is called hash function

2) One of the techniques of dealing with the hash collision is

1. Chaining
2. Addressing
3. Resolving
4. Probing

Ans) A

3) ________ builds a linked list of all items whose keys hash to the same values.

1. Chaining
2. Addressing
3. Resolving
4. Probing

Ans) A

4) Hashing allows direct access to the _______

1. Link
2. Tuple
3. Data
4. Table

Ans) D

5) One way to eliminate all clustering is

1. Quadratic rehash
2. Rehashing
3. Hashing
4. Double hashing

Ans) D

6) Mark the statement(s) that is/are true

a.       Attempt made to insert a record K2 in the position where K1 is already placed

             is defined as Hash collision

b.      Transforming a key into a table index is called hash function

c.       Attempt made to insert a record K2 in the position where K1 is already placed

               is defined as Hash function

       d.   Transforming a key into a table index is called Hash collision

Ans) A, B

7) If the ________ of the item is found to be occupied during a search the rehash function is again used to locate the item.

1. Proper position
2. Hash position
3. Search position
4. Key position

Ans) B

8) The larger the range of the hash functions the less likely it is that the two keys yield the same _________.

1. Hash value.
2. Key value
3. Table value
4. Tuple value

Ans) A

9) Different keys that hash to the same value follow the same rehash path. This is called

1. Secondary clustering
2. Primary clustering
3. Double hashing
4. Quadratic rehash

Ans) A

10) __________ permits a hash table to expand and shrink dynamically

       without requiring an index.

1. Linear hashing
2. Linear rehashing
3. Extendible hashing
4. Dynamic hashing

Ans) A

11) The function that transforms a key into a __________ is called a hash function.

1. Key index
2. Data table
3. Table index
4. Record

Ans) C

12) __________ involves using a secondary hash function on the hash key of the item.

1. Probing
2. Addressing
3. Resolving
4. Rehashing

Ans)D

13) All items whose keys hash to the same values is built into a linked list, this is called

1. Addressing
2. Resolving
3. Chaining
4. Probing

Ans) C

14) Two keys that hash into different values compete with each other in _________

       is called primary clustering.

1. Hash table
2. Successive rehashes
3. Link table
4. Secondary hash

Ans) B

15) The _______of a hashing method is usually measured by the average number of table positions that must be examined in searching for a particular item.

1. Accuracy
2. Efficiency
3. Complexity
4. Easiness

Ans) B

16) If r is the record whose key hashes into hr, hr is called

1. Function of r
2. Hash key of r.
3. Function key of r
4. Key of r

Ans) B

17) Rehashing involves using a secondary hash function on the __________ of the item.

1. Hash Key
2. Data Key
3. Table Key
4. Index Key

Ans) A

18) A good hash function is one that

1. Spreads the records uniformly throughout the table
2. Minimizes duplication
3. Reduces link fields
4. Reduces duplication

Ans) A,B

19) One way of eliminating _________is to allow the rehash function to depend on the number of times that the function is applied to a particular hash value.

1. Secondary clustering
2. Primary clustering
3. Double hashing
4. Quadratic rehash

Ans) B

20) ________is defined as any hashing scheme in which any newly inserted element is equally likely to be placed at any of the empty positions of the hash table.

1. Quadratic rehash
2. Double hashing
3. Uniform hashing
4. Rehashing

Ans) C

21) The function that transforms a ______ into a table index is called a hash function.

1. Key
2. Data
3. Table
4. Index

Ans) A

22) Hash collision can be dealt with techniques like

1. Resolving and addressing
2. Probing
3. Rehashing and chaining
4. Hashing

Ans) C

23) Chaining builds __________of all items whose keys hash to the same values

1. An index
2. A linked list
3. A collection
4. A grouping

Ans) B

24) The phenomenon, where two keys that hash into different values compete with each other in successive rehashes is called _____________.

1. Double hashing
2. Quadratic rehash
3. Primary clustering
4. Secondary clustering

Ans) C

25) It is difficult to delete items from the hash table that uses ________for search and insertion.

1. Rehashing
2. Addressing
3. Probing
4. Linking

Ans) A

26) If h is a hash and key is key______ is called the hash of key.

1. h-key
2. key(h)
3. h(k)
4. h(key)

Ans) D

27) Rehashing involves using a secondary ________ on the hash key of the item.

1. Hash function
2. Key function
3. Transformation function
4. Table function

Ans) A

28) A good hash function is one that minimizes ___________.

1. Collisions
2. Duplication
3. Creation
4. Link fields

Ans) A

29) Any __________ that depends solely on the index to be rehashed causes

        primary clustering.

1. Rehash function
2. Key function
3. Hash function
4. Table function

 Ans) A

30) The Efficiency of a hashing method is usually measured by the average number of

________ that must be examined in searching for a particular item.

1. Table positions
2. Tuple
3. Data
4. Links

Ans) A

31) Hash collision is defined as

1. An attempt made to insert a record K2 in the position where K1 is already placed
2. Transforming a key into a table index
3. Inserting an already existing record
4. Inserting a record into the wrong position

Ans) A

32) The hash function is applied successfully until ________is found where the items can be inserted.

1. Proper position
2. Hash position
3. Empty position
4. Key position

Ans) C

33) The _________ the range of the Hash function, the less likely it is that the two keys yield the same hash value.

1. Smaller
2. Larger
3. Closer
4. Farther

Ans) B

34) One way of eliminating primary clustering is to allow there hash function to depend on the number of times that the function is applied to a particular ________.

1. Data
2. Table Key
3. Hash value
4. Index value

Ans) C

35) Uniform hashing is defined as any newly inserted element is equally likely to be placed at any of the empty positions of the____________.

1. Index table
2. Hash table
3. Sorted list
4. Grouped elements

Ans) B

36) If h is a hash and key is key, h(key) is called the

1. Key of hash
2. Hash of key
3. Function key
4. Key function

Ans) B

37) Rehashing involves using __________hash function on the hash key of the item.

1. Primary
2. First
3. Second
4. Secondary

Ans) D

38) The chaining technique involves adding an extra_________ to each table position.

1. Series of data
2. Line
3. Tuple
4. Link field

Ans) D

39) Any rehash function that depends solely on the index to be rehashed causes __________.

1. Double hashing
2. Quadratic rehash
3. Primary clustering
4. Secondary clustering

Ans) C

40) The Efficiency of a________ is usually measured by the average number of table positions that must be examined in searching for a particular item

1. Rehash method
2. Linking method
3. Hashing method
4. Searching method

Ans) C

41) One of the techniques of dealing with the hash collision is

1. Probing
2. Addressing
3. Resolving
4. Rehashing

Ans) D

42) If the Hash function of the item is found to be occupied during a search the _______ is again used to locate the item.

1. Key function
2. Hash function
3. Transformation function
4. Rehash function

Ans) D

43) ___________ allows direct access to the table.

1. Probing
2. Rehashing
3. Hashing
4. Addressing

Ans) C

44) Secondary clustering is the phenomenon where different keys that hash to the same      value follow ___________

1. Different rehash path
2. Same rehash path
3. Selected path
4. Ideal path

Ans) B

45) Linear hashing permits a________ to expand and shrink dynamically

       without requiring an index.

1. Index table
2. Hash table
3. Sorted list
4. Grouped elements

Ans) B

46) If an attempt is made to insert a record k2 in the position where k1 is already placed

The situation that results is called

1. Hash collision
2. Probing
3. Hash clash
4. Invalid insertion

Ans) A, C

47) The _________is applied successfully until an empty position is found where the items can be inserted.

1. Key function
2. Hash function
3. Transformation function
4. Table function

Ans) B

48) The larger the range of the _________ the less likely it is that the two keys yield the same hash value.

1. Key function
2. Hash function
3. Transformation function
4. Table function

Ans) B

49) One way of eliminating primary clustering is to allow the ________ to depend on the number of times that the function is applied to a particular hash value.

1. Key function
2. Hash function
3. Table function
4. Rehash function

Ans) A

50) Uniform hashing is defined as any___________ in which any newly inserted element is equally likely to be placed at any of the empty positions of the hash table

1. Sorting scheme
2. Hashing scheme
3. Searching scheme
4. Linking scheme

Ans) B

51)  The following paragraph is connected with hashing:

The process of mapping large amounts of data into a smaller table is called …… (i) ……. A good hash function should satisfy two criteria, namely quickness to compute and minimisation of the number of   …… (ii) ……. Minimization of …… (iii) …… can be achieved by choosing a hash function that spreads the incoming data as evenly as possible over the hash table.

Correct terms for the blanks positions are:

(a)  (i) indexing   (ii) collisions    (iii) couplings

(b)  (i) hashing      (ii) collisions    (iii) couplings

(c)  (i) hashing    (ii) collisions     (iii) collisions

(d)  (i) indexing     (ii) collisions    (iii) collisions  

(e)  (i) hashing    (ii) couplings     (iii) couplings

Ans :c

52. Consider the following five (v) terms:

                 (i)   Coupling

                 (ii)  Double hashing

                 (iii) Collision

                 (iv) Linear probing

                (v) Quadratic probing

Which of the above is a/are hashing method(s)?

(a)   (ii) only

(b)   (ii) and (iv) only

(c)   (ii),(iv) and (v) only

(d)   (ii) and (iii) only

(e)   All of these

Ans :c

53. Which of the following is a /are hash function(s)?

(a) Shortest path

(b) Folding

(c) Mid-square

(d)Extraction

(e)Binary

Ans : b, c, e

54. Which of the following are not hash functions?

(a) division

 (b) folding

(c) coupling

(d) mid square

(e) extraction

Ans : c