Data Structure教学课件（华南理工）Tutorial06 ans.pdfVIP

Data Structure (Semester 1, 2014-2015) Tutorial 06 - Answer Prepared by Dr. Patrick Chan Date: October-2014 1. For each of the following self-organization list heuristics, describe e a series of record accesses for which it would require the greatest number of comparisons of the three. i) move-to-front ii) count iii) transpose Answer: i) For Move-to-Front, again visit in reverse order. ii) For count, visit each record in turn in the order that will visit the last element each time. For example, if for the values 0 to 7 stored in ascending order initially, visit them in reverse order (from 7 down to 0). iii) For Transpose, alternately visit the last two elements, as described in the book. Data Structure – Tutorial 6 1 2. Assume that you are hashing key K to a hash table of n slots (index from 0 to n-1). For each of the following functions h(K), is the function acceptable as a hash function (i.e., would the hash program work correctly for both insertions and searches), and if so, is it a good hash function? i) h(k) = 1 ii) h(k) = k/n k and n are integers iii) h(k) = (k + Random(n)) mod n Function Random(n) returns a random integer between 0 and n-1, inclusive iv) h(k) = k mod n n is a prime number Answer: i) Yes But is the worst possible hash function since all values hash to the same location. ii) No 2 if K ≥ n then the result will be out of the range of the hash table iii) No it is not possible to recover the location of the element once