ADS tut 2

In simple chaining, what data structure is appropriate?

• Singly linked list

• Doubly linked list

• Circular linked list

• Binary trees

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown above.

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

• 46, 42, 34, 52, 23, 33

• 34, 42, 23, 52, 33, 46

• 46, 34, 42, 23, 52, 33

• 42, 46, 33, 23, 34, 52

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

• h(i) =i^2 mod 10

• h(i) =i^3 mod 10

• h(i) = (11 ∗ i^2) mod 10

• h(i) = (12 ∗ i) mod 10

What is the time complexity improvement of skip lists from linked lists in insertion and deletion?

• O(n) to O(logn) where n is number of elements

• O(n) to O(1) where n is number of elements

• no change

• O(n) to O(n²) where n is number of elements

The nodes in a skip list may have many forward references. their number is determined

• probabilistically

• randomly

• sequentially

• orthogonally

The size of the hash table is 12. Double hashing is used to resolve collisions. The hash function used is H(k) = k mod 12 The second hash function is: H2(k) = 7 – (k mod 7). What value will be in the hash table at location 4 after the following sequence of insertions 33, 10, 9, 13, 12, 45, 26?

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 hash to the same value 

iii. All elements hash to the same value

 iv. Each element hashes to a different value 

• i only 

• ii only 

• i and ii only 

• iii or iv 

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

• h(i) =i^2 mod 10

• h(i) =i^3 mod 10 

• h(i) = (11 ∗ i^2) mod 10 

• h(i) = (12 ∗ i) mod 10 

Insert the keys 27, 43, 692, 72 into the Hash Table of size 7. where first hash-function is h1​(k) = k mod 7 and second hash-function is h2(k) = 1 + (k mod 5). The number 692 is stored at location?