Data Structure And Algorithm II

What is a hash table?

• a) A structure that maps values to keys

• b) A structure that maps keys to values

• c) A structure used for storage

• d) A structure used to implement stack and queue

If several elements are competing for the same bucket in the hash table, what is it called?

• a) Diffusion

• b) Replication

• c) Collision

• d) Duplication

Which of the following is not a technique to avoid a collision?

• a) Make the hash function appear random

• b) Use the chaining method

• c) Use uniform hashing

• d) Increasing hash table size

A technique for direct search is

• a) Binary Search

• b) Linear Search

• c) Tree Search

• d) Hashing

The goal of hashing is to produce a search that takes

• a) O(1) time

• b) O(n2 )time

• c) O(log n ) time

• d) O(n log n ) time

Which of the following statement(s) is TRUE?

I. A hash function takes a message of arbitrary length and generates a fixed length code.

II. A hash function takes a message of fixed length and generates a code of variable length.

III. A hash function may give the same hash value for distinct messages.

• I only

• II and III only

• I and III only

• II only

What is direct addressing?

• A. Distinct array position for every possible key

• B. Fewer array positions than keys

• C. Fewer keys than array positions

• D. None of the mentioned

What can be the techniques to avoid collision?

• A. Make the hash function appear random

• B. Use the chaining method

• C. Use uniform hashing

• D. All of the mentioned

In linear probing, the cost of an unsuccessful search can be used to compute the average cost of a successful search.

• True

• False

Which of the following algorithms solves the all-pair shortest path problem?

• a. Floyd's algorithm

• b. Prim's algorithm

• c. Dijkstra's algorithm

• d. Warshall's algorithm