QUESTIONS on Dictionaries

QUESTIONS:

1.(a)Define  Hashing, Hash Function  ,Collisions.

    (b)Explain  the different methods  that  are  used to  calculate   Hash Function.

2.Define  Collisions. Explain  the  different techniques  that  are  used  to  resolve  collsion.

3.What  is  Dictionaries  ,state  different  types of dictionaries ,operations  and  ADT(Operations  on   dictionary).

4.With  an  example  explain different types of  Hash Function  .

5.Perform  the  insertion operations   using  double  hashing  for  the  following  list:

      12,54,62,45,37,78,89,28,61,49.Where table size is 10.

6.(a)List  any  four to  five  advantages  and disadvantages of   separate  chaining.

   (b)Explain open  addressing  and  write  the  algorithm  to  insert  an  item  into  the  table.

7.(a)Explain  with  an example  about  linear  probing  ,quadratic  probing.

   (b)Provide  draw backs  of  separate chaining .

8.(a)Write  the  characteristics of  good  hashing   function.

   (b)Explain  separate  chaining  and  its  operations.

9.(a)Write  an   algorithm  of  insertion  and search on  double  hashing .

   (b)Applications  of  hash  tables.

FILL IN  THE  BLANKS:

1.Dictionaries  is  a  collection  of  pair of  keys  and  values.

2.Dictionaries  are  divided into  Ordered Dictionary  and  Unordered  Dictionary.

3.Accessing  randomly  pairs  of  keys and  values is  called   Unordered  Dictionary.

4.Accesssing   sequentially  pair  of  keys  and  values  is  called  Ordered Dictionary.

5.Operations  on   dictionary  are   insertion ,deletion and  searching.

6.The   Dictionaries  can  be   represented  as  a linear  list.

7.Two  methods   for   Linear  List  Representation  is  sorted  array  and   sorted  chain.

8.An   array   Data structures   is  used  to  implement  the  Dictionaries  is  called  as  sorted  array.

9.An   Linked list  data  structure   is  used  to  implement  the  Dictionaries  is  called   as  sorted  chain.

10.The  integer  returned  by  the  Hash Function  is  called  as   hash  key.

11.Simply  Hash Function is  calculated as  H(key)=key% tablesize

12.In   the  multiplicative  Hash Function  ,the   scientist  Donald  Knuth  use  constant  ‘A’, value  of  ‘A’ is 0.61803398987.

13.Ideally  if  no  of  Collisions  occurs   then  such  a  function  is called  perfect Hash Function.

14.The   two  Collision resolution techniques  are  Separate chaining  and  Open addressing.

15.The  Separate chaining  is  also  known  as  open hashing.

16.In   the  Open addressing  the  location   of the  hash  table  termed  as bucket.

17.The  function   of  Linear probing  is  h(x)=(h(x)+i)modn

18.One  major  problem  with  Linear probing  os  primary  clustering.

19.The    functions   of  Quadratic probing  is   h(x)=(h(x)+i²)modn.

20.The   function   of  double  hashing   is  H₁(key)=key mod  table size  and   H₂(key)=M-(key mod m).

CHOOSE  THE  CORRECT  ANSWERS:           

1. Mid  Square  method  is  calculated  by   [b]

(a)H(key)=key% table size

(b)(key)²=Result (mid part of result)

(c)H(key)=floor(p*(fractional part of key*A))

(d)H(key)=key/ table size

2.Division  Method  is  calculated  by [a]

(a)H(key)=key% table size

(b)H(key)=key/table size

(c)(key)²=Result (mid part of result)

(d)H(key)=floor(p*(fractional part of key*A))

3.Multiplicative   Hash   Functon  is  calculated by [d]

(a)H(key)=key% table size

(b)H(key)=key/table size

(c)(key)²=Result(mid part  of result)

(d)H(key)=floor(p*(fractional part  of key *A))

4.Find   Extraction  hash  function of   a  given  number   5798643  [a]

(a)5798

(b)14355

(c)99812

(d)none

  5.When  a  Hash Function  maps  two  different   keys  to  same  location  then  [b]

(a)overflow occurs

(b)Collisions occurs

(c)insertion occurs

(d)deletion occurs

6.When  the  hash  table  is  filled  if  there is a situation  to insert  a new  pair  in  the  same  hash  table then  [a]

(a)overflow occurs

(b)Collisions occurs

(c)insertion occurs

(d)both b&c

7.The  best  time  complexity  of  search  operation  is  [c]

(a)O(n)

(b)O(n log n)

(c)O(1)

(d)O(log n)

8The  worst  time  complexity  of  insertion operation  is [a]

(a)O(n)

(b)O(n log n)

(c)O(1)

(d)O(log n)

TRUE  (or)  FALSE:

1.Is  Collisions   occurs  for  the  given  values   23,13,21,14  and  the  given  table size  is  7 [T].

2.Is  the  digit  folding  is  a  Collision resolution techniques   [F].

3.Is  the  Extraction  is  a  Hash Function  [T].

4.Is  Open addressing  &  Separate chaining  are  Collision resolution techniques   [T].

MATCH  THE  FOLLOWING:

1.Hash Function                                    [a]          (a)h(x)=(h(x)+i)mod n

2 Mid  Square  method                             [b]          (b)h(x)=(h(x)+i²)mod n

3Multiplicative   Hash   Functon            [l]          (c)Collisions

 4 Linear probing                                   [a]         (d)pair(key,values)

5.Quadratic probing                              [b]         (e)table size  is  resolved                          

6.Rehashing                                            [e]        (f)O(1)

7.16,18,9,36  when  table  size  is          [c]         (g)table size  need not  be  prime  number. 

10  by   Division  Method

8.Advantages  of  separate  chaining     [g]        (h)O(n)

9.Best  time  complexity                        [f]         (i)(key)²=result(mid part of result)

10. Dictionaries                                         [d]        (j)H(key)=key%table size

                                                                            (k)pair(rows,columns)

                                                                            (l)H(key)=floor(p*(fractional part of  key  *A))

                                                      

         

      Dictionaries