Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to the same value ii) 1471, 6171 has to the same value iii) All elements hash to the same value iv) Each element hashes to a different value
Question 2
Consider the following, five binary strings of length 8. 01010010, 11011011, 10011010, 11111011, 01110010 A hash table of size M = 8 (0 to 7) is using open addressing for hashing the binary strings. Assume finding an empty slot directly without collision or after collision is also a probe. Calculate the total number of probes that occur while hashing five strings using linear probing. Assume hash function, h(x) = x mod 8.
Question 3
If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n < m, the expected number of collisions involving a particular key K is ?
Question 4
The mechanism involves in direct searching is:
Question 5
What is the number of swaps required to sort n elements using selection sort, in the worst case?
Question 6
Consider a hash table of size seven, with starting index zero, and a hash function(3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that − denotes an empty location in the table.
Question 7
The Keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially hash table of length 10 using open addressing with hash function h (K) = k mod 10 and linear probing. What is the resultant hash table?
Question 8
The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: “as bscsae ds ceesfs be de gseefehsge he”. Here, xs denotes the starting time and xe denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?
Question 9
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
Question 10
In a binary max heap containing nnumbers, the smallest element can be found in time
