Solution for NPTEL, Introduction to Algorithm and Analysis Week 5 MCQs

1.A collision in hash function means

A). Two keys match to same slot

B). Two keys match to two consecutive slots

C). Both A) and B).

D). None of the above

 Ans:  A). Two keys match to same slot

2.In chaining, we put all those elements into same linked list which

A). Hash to consecutive slots

B). Hash to same slots

C). Both A) and B).

D). None of the above.

Ans: B). Hash to same slots

3.For a hash table T with n slots and m elements, load factor for T is defined by:

A). n/m

B). m/n

C). 1/(nm)

D). nm

Ans:B). m/n

4.The hash function to map a key k into one of the m slots using division method is given by:

A). h(k) = k/m

B). h(k) = k mod m

C). h(k) = m/k

D). h(k) = m mod k

Ans:  B). h(k) = k mod m

5. For a given ordinary hash function h’ : U –> {0,1,2,…,m-1} the method of linear probing uses the hash function:

A). h(k,i) = (h'(k) + i) mod m , for i= 0,1,2,…,m-1

B). h(k,i) = (h'(i) + k) mod m , for i= 0,1,2,…,m-1

C). h(k,i) = (h'(m) + i) mod k , for i= 0,1,2,…,m-1

D). h(k,i) = (h'(m) + k) mod k , for i= 0,1,2,…,m-1

Ans: A). h(k,i) = (h'(k) + i) mod m  , for i= 0,1,2,...,m-1

6.Let k be a node in a binary search tree. Let x be a node in right sub-tree of k and y be a node in the left sub-tree of k then

A). y.key > x.key

B). y.key <= x.key

C). y.key has no relation with x.key

D). None of the above.

Ans: B). y.key <= x.key

7.The worst case time complexity of insert operations in a Binary Search Tree containing n nodes is:

A). O(1)

B). O(log n)

C). O(n)

D). O(log(log n))

Ans: C). O(n)

8.The worst case time complexity of search operation in a Binary Search Tree containing n nodes is:

A). O(1)

B). O(n)

C). O(logn)

D). O(log(logn))

Ans:  B). O(n)

9.Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function: h(x)=x mod 10, which of the following statements are true?
9679, 1989, 4199 hash to the same value
1471, 6171 has to the same value
All elements hash to the same value
Each element hashes to a different value

A). 1 only

B). 2 only

C). 1 and 2 both

D). None of the above

Ans: C). 1 and 2 both

10.The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. At which level would 5 be inserted? Assume that root has level 1.

A). 2

B). 8

C). 7

D). none of the above

Ans:D). none of the above

Stay Hackademic , Be Hackademic(Subcribe Hackademic)