Category: Data Structure Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Hash Tables Chaining using Linked Lists”.

1. The case in which a key other than the desired one is kept at the identified location is called?
a) Hashing
b) Collision
c) Chaining
d) Open addressing

Answer: b
Clarification: When some other value is placed at a specified location other than the desired key, it is said to be a collision.

2. What data organization method is used in hash tables?
a) Stack
b) Array
c) Linked list
d) Queue

Answer: c
Clarification: The data structure used to organize data for hash tables is linked list. It contains a data field and a pointer field.

3. The task of generating alternative indices for a node is called?
a) Collision handling
b) Collision detection
c) Collision recovery
d) Closed hashing

Answer: a
Clarification: Collision handling involves the process of formulating alternative indices for a key.

4. Which of the following is not a collision resolution technique?
a) Separate chaining
b) Linear probing
c) Quadratic probing
d) Hashing

Answer: d
Clarification: Hashing is a technique of placing data items in specific locations. Collision may occur in hashing but hashing is not a collision resolution technique.

5. Hashing is the problem of finding an appropriate mapping of keys into addresses.
a) True
b) False

Answer: a
Clarification: Hashing is a data structure which is used to locate data in a table based on a key value.

6. In a hash table of size 10, where is element 7 placed?
a) 6
b) 7
c) 17
d) 16

Answer: b
Clarification: The hash location is defined as hash(f)= key mod table_size.
7 mod 10 gives 7. It is placed in 7^th position.

7. What should be the load factor for separate chaining hashing?
a) 0.5
b) 1
c) 1.5
d) 2

Answer: b
Clarification: For hashing using separate chaining method, the load factor should be maintained as 1. For open addressing method, it should not exceed 0.5.

8. Which of the following operations are done in a hash table?
a) Insert only
b) Search only
c) Insert and search
d) Replace

Answer: c
Clarification: Hash tables are used to implement Insert and Find operations in constant average time. This is the prime purpose of hashing.

9. Which of the following is identical to that of a separate chaining hash node?
a) Linked list
b) Array
c) Stack
d) Queue

Answer: a
Clarification: The hash node in separate chaining is similar to that of a linked list. The separate chaining hash table is an array of linked lists.

10. Which of the following is the hashing function for separate chaining?
a) H(x)=(hash(x)+f(i)) mod table size
b) H(x)=hash(x)+i² mod table size
c) H(x)=x mod table size
d) H(x)=x mod (table size * 2)

Answer: c
Clarification: The hashing function for separate chaining is given by H(x)= key mod table size. H(x)=hash(x)+i2 mod table size defines quadratic probing.

11. What is the correct notation for a load factor?
a) Ω
b) ∞
c) ∑
d) ⅄

Answer: d
Clarification: In general, load factor is denoted as ⅄. In separate chaining method, load factor is maintained as 1.0.

12. In hash tables, how many traversal of links does a successful search require?
a) 1+⅄
b) 1+⅄²
c) 1+ (⅄/2)
d) ⅄³

Answer: c
Clarification: A successful search requires about 1+ (⅄/2) links to be traversed. There is a guarantee that at least one link must be traversed.

13. Which of the following is a disadvantage of using separate chaining using linked lists?
a) It requires many pointers
b) It requires linked lists
c) It uses array
d) It does not resolve collision

Answer: a
Clarification: One of the major disadvantages of using separate chaining is the requirement of pointers. If the number of elements are more, it requires more pointers.

14. What is the worst case search time of a hashing using separate chaining algorithm?
a) O(N log N)
b) O(N)
c) O(N²)
d) O(N³)

Answer: b
Clarification: The worst case search time of separate chaining algorithm using linked lists is mathematically found to be O(N).

Data Structure Multiple Choice Questions on “Directed Graph”.

1. Dijkstra’s Algorithm will work for both negative and positive weights?
a) True
b) False
Answer: b
Clarification: Dijkstra’s Algorithm assumes all weights to be non-negative.

2. A graph having an edge from each vertex to every other vertex is called a ___________
a) Tightly Connected
b) Strongly Connected
c) Weakly Connected
d) Loosely Connected
Answer: a
Clarification: This is a part of the nomenclature followed in Graph Theory.

3. What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?
a) 2
b) 4
c) 5
d) 9
Answer: b
Clarification:

#include 
#define INF 1000000
int graph[V][V] = {   {0,   7,  INF, 4},
                      {INF, 0,   13, INF},
                      {INF, INF, 0,   12},
                      {INF, INF, INF, 0}
                  };
 
int distance[V][V], i, j, k;
 
for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
    	distance[i][j] = graph[i][j];
 
for (k = 0; k < V; k++)
	for (i = 0; i < V; i++)
        	for (j = 0; j < V; j++)
                {
            		if (distance[i][k] + distance[k][j] < distance[i][j])
                		distance[i][j] = distance[i][k] + distance[k][j];
 
                           return 0;
                }

{            
    {0,   7,  INF, 4},
    {INF, 0,   13, INF},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
};

{            
    {0,   7,  20, 24},
    {INF, 0,   13, 25},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
};

{ 
    {0,   INF,  20, 24},
    {INF, INF,   13, 25},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
    {INF, 0,   13, 25},
    {INF, INF, 0,   12},
    {24, INF, INF, 0}
};