Searching MCQ Quiz - Objective Question with Answer for Searching - Download Free PDF

Last updated on Jun 10, 2025

Latest Searching MCQ Objective Questions

Searching Question 1:

Which data structure often results in a time-space tradeoff by using extra memory to speed up operations?

  1. Arrays 
  2. Linked lists
  3. Hash tables
  4. Stacks
  5. None of the above

Answer (Detailed Solution Below)

Option 3 : Hash tables

Searching Question 1 Detailed Solution

The correct answer is Hash tables

Key Points

  • Hash tables:
    • Hash tables use extra memory to achieve faster access times for certain operations.
    • They employ a hash function to map keys to indices in an array, providing constant time average-case access for search, insertion, and deletion.
    • However, there's a tradeoff in terms of space because collisions (two keys hashing to the same index) may occur, leading to the need for additional structures like linked lists or open addressing.

Additional Information

  • Arrays:
    • Arrays provide constant time access to elements using an index.
    • They have a fixed size, which can lead to memory wastage if the array is larger than the actual number of elements it holds.
    • No extra memory is used to speed up operations, and access time is already efficient.
  • Linked lists:
    • Linked lists provide dynamic memory allocation, allowing for efficient insertion and deletion of elements.
    • However, accessing an element at a specific index takes linear time, as you need to traverse the list from the beginning.
    • Linked lists do not use extra memory to speed up operations.
  • Stacks:
    • Stacks follow the Last-In-First-Out (LIFO) principle and allow efficient insertion and deletion of elements at one end.
    • They are typically implemented using arrays or linked lists.
    • Stacks do not use extra memory to speed up operations; their efficiency comes from the nature of the LIFO structure.

Searching Question 2:

Which collision resolution technique involves placing collided elements in the next available empty slot in the hash table? 

  1. Linear probing
  2. Quadratic probing 
  3. Separate chaining
  4. Double hashing 
  5. None of the above

Answer (Detailed Solution Below)

Option 1 : Linear probing

Searching Question 2 Detailed Solution

The correct answer is Linear probing

Key Points

  • Linear Probing:
    • When a collision occurs (two elements hash to the same location), linear probing involves placing the collided element in the next available (unoccupied) slot in the hash table.
    • If that slot is also occupied, it continues to search for the next empty slot in a linear fashion (moving one slot at a time) until an empty slot is found.
    • Linear probing can lead to clustering, where consecutive elements form clusters in the hash table.

Additional Information

  • Quadratic Probing:
    • Similar to linear probing, but instead of moving one slot at a time, quadratic probing uses a quadratic function to determine the next position to check.
    • If the slot at the hash index is occupied, it checks slots at positions incremented by successive squares.
    • Quadratic probing helps to reduce clustering compared to linear probing.
  • Separate Chaining:
    • Instead of placing collided elements in the next available slot in the hash table, separate chaining involves maintaining a linked list at each slot in the hash table.
    • When a collision occurs, the collided elements are added to the linked list at that slot.
    • Each slot contains a separate data structure (like a linked list or a tree) to handle collisions.
  • Double Hashing:
    • In double hashing, a secondary hash function is used to determine the step size between probe attempts.
    • If a collision occurs, the algorithm uses the secondary hash function to calculate a new index to probe.
    • This helps to avoid clustering and provides a more systematic way to find an empty slot.

Searching Question 3:

Which of the following searching technique does not get affected on increasing the size of search list.

  1. Binary Search
  2. Linear Search
  3. Search by Hashing
  4. More than one of the above
  5. None of the above

Answer (Detailed Solution Below)

Option 3 : Search by Hashing

Searching Question 3 Detailed Solution

The correct option is Search by Hashing.

CONCEPT:

In linear search, every element of a given list is compared one by one with the given key without skipping any element.

It is useful when we need to search for an item in a small unsorted list, but the time taken to search the list increases as the size of the list increases.

For example, consider a list of length 5 and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 5

If we increase the size of the same list (say 15) and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 15

 

In binary search, the key to be searched is compared with the middle element of a sorted list, If the element at the middle position:

i)  Matches the key the search is successful

ii) Is greater than the key then the key element may be present in the left part of the list

iii) Is smaller than the key, then the key element may be present in the right part of the list

This process continues till the element is found or the list is traversed completely.

Thus the time taken to search the list increases as the size of the list increases. But it will not be as large as the time required by linear search

 

Hash-based searching requires only one key comparison to find the position of a key, provided every element is present at its designated position decided by a hash function. 

For example, consider a list of length 5 and the hash function: h(element) = element % size(list)

A hashing function is a mathematical function that generates unique results for each unique value supplied to the hash function in constant time.

For example: Consider a list of length 5 and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 2  and requires only one key comparison to find the key at that index

Similarly increasing the size of the list (say 15) and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 12  and requires only one key comparison to find the key at that index

Thus it is independent of the length of the list.

Searching Question 4:

Which open addressing technique is free from Clustering problems?

  1. Linear probing
  2. Quadratic probing
  3. Double hashing
  4. More than one of the above
  5. None of the above

Answer (Detailed Solution Below)

Option 3 : Double hashing

Searching Question 4 Detailed Solution

Primary clustering:

  • It is one of two major failure modes of open addressing based hash tables, especially those using linear probing.
  • It occurs after a hash collision causes two of the records in the hash table to hash to the same position, and causes one of the records to be moved to the next location in its probe sequence.

Secondary clustering:

Secondary clustering occurs more generally with open addressing modes including linear probing and quadratic probing in which the probe sequence is independent of the key, as well as in hash chaining.

Double hashing:

Double hashing is a computer programming technique used in conjunction with open-addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs.

Double hashing technique is free from Clustering problems

Searching Question 5:

For which of the following tasks, stack is not suitable data structure?

(a) Binary search in an array

(b) Breadth first search

(c) Implementing function calls

(d) Process scheduling

  1. (b) and (d)
  2. (b) and (c)
  3. (a) and (c)
  4. More than one of the above
  5. None of the above

Answer (Detailed Solution Below)

Option 1 : (b) and (d)

Searching Question 5 Detailed Solution

Concept :

Stack is a data structure in which elements can be inserted and deleted only from one end i.e. top of the stack. It follows the LIFO property i.e. last in first out.

Explanation:

(a) Binary search in an array

Binary search in an array can be performed with the help of stack.  Binary search works on the divide and conquer approach and finds the middle element and then perform the search in the left side if element is smaller than the middle element otherwise search proceed in the right of middle element.

(b) Breadth first search

Breadth first search is graph traversal algorithm. It uses queue data structure to traverse the graph or the tree. It is also used to find the connected components in a graph.

(c) Implementing function calls

Function calls are implemented using the stack data structure. As, when a function call arrives then the state or the data currently operated on is stored on the stack where it is resumed after the execution of function call.

(d) Process scheduling

Process scheduling is implemented using the queue data structure . Ready queue is maintained for the processes which are ready for the execution.

Top Searching MCQ Objective Questions

Consider a hash table of size 7, with hash function H (k) = k % 7, and pseudo random i = (i + 5) % 7. We want to insert the following keys one by one from left to right.

15, 11, 25, 16, 9, 8, 12

What will be the position of the key 25, if we use random probing?

  1. 4
  2. 5
  3. 1
  4. 2

Answer (Detailed Solution Below)

Option 4 : 2

Searching Question 6 Detailed Solution

Download Solution PDF

Since we are using random probing:

Insert 15:

(15)%7 = 1

Insert 11:

(11)%7 = 4

Insert 25:

(25)%7 = 4 / collision:

i = 4

 i = (i + 5) % 7    / using random function

i = (4 + 5)%7 = 2

Hence 25 position is 2nd

What is the best-case time complexity of the Linear search?

  1. O(n)
  2. O(1)
  3. O(n log n)
  4. O(n2)

Answer (Detailed Solution Below)

Option 2 : O(1)

Searching Question 7 Detailed Solution

Download Solution PDF

Concept:

  • A linear search or sequential search is a method for finding an element within an array or linked list or any data structure.

  • It sequentially checks each element of the list until a match is found or the whole list has been searched.


Explanation:

int A[ ] = {2, 1, 4, 5 , 6, 7}

Array name: A

index

0

1

2

3

4

5

element

2

1

4

5

6

7

 

Search: 2

In first comparison, 2 is found

Best case time complexity is O(1)

What is the worst-case and average-case time complexity of the Binary search?

  1. O(n2)
  2. O(1)
  3. O(n log n)
  4. O(log n)

Answer (Detailed Solution Below)

Option 4 : O(log n)

Searching Question 8 Detailed Solution

Download Solution PDF

Binary search algorithm:

Binary search algorithm is used to find an element in an already sorted array.

STEPS 1:

It finds the middle element of the array and compare the element with the element to be searched, if it matches then return true.

STEPS 2:

If not, then divide the array into two halves in which if element to be search is less than middle element then search takes place in left part otherwise search in right half.

STEP 3:

Repeat this process, until you get the element.

Explanation:

For worst case 52

Worst Case: Search 50 in below give array

11

12

15

24

35

50

51

63

 

50 > 32

50

matched

T(n) = O(log n)

Also, for average case:

T(n) = O(log n)

Finding the location of the element with a given value is:

  1. Traversal
  2. Search
  3. Sort
  4. None of the options

Answer (Detailed Solution Below)

Option 2 : Search

Searching Question 9 Detailed Solution

Download Solution PDF

Searching: 

Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Therefore finding the location of the element with a given value is Search.

  • Sequential Search: In this, the list or array is traversed sequentially and every element is checked.
  • Binary Search: These algorithms are specifically designed for searching in sorted data-structures

Therefore option 2 is correct

Important Point:

The sorting algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.

Traversal is a process to visit all the nodes of a tree and may print their values too. Because all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree −

  • In-order Traversal
  • Post-Order Traversal
  • Pre-Order Traversal

Consider a hash table with 9 slots. The hash function is ℎ(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

  1. 3, 0, and 1
  2. 3, 3 and 3
  3. 4, 0, and 1
  4. 3, 0, and 2

Answer (Detailed Solution Below)

Option 1 : 3, 0, and 1

Searching Question 10 Detailed Solution

Download Solution PDF

Concept:

Keys: 5, 28, 19, 15, 20, 33, 12, 17,

10.

ℎ(k) = k mod 9

Chaining

Maximum chain length = 3 (28 -> 19 -> 10)

Minimum chain length = 0 (0, 4, 7 slot doesn’t have any element)

Hence option 1 is the correct answer.

Which open addressing technique is free from Clustering problems?

  1. Linear probing
  2. Quadratic probing
  3. Double hashing
  4. Rehashing

Answer (Detailed Solution Below)

Option 3 : Double hashing

Searching Question 11 Detailed Solution

Download Solution PDF

Primary clustering:

  • It is one of two major failure modes of open addressing based hash tables, especially those using linear probing.
  • It occurs after a hash collision causes two of the records in the hash table to hash to the same position, and causes one of the records to be moved to the next location in its probe sequence.

Secondary clustering:

Secondary clustering occurs more generally with open addressing modes including linear probing and quadratic probing in which the probe sequence is independent of the key, as well as in hash chaining.

Double hashing:

Double hashing is a computer programming technique used in conjunction with open-addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs.

Double hashing technique is free from Clustering problems

A _______ is an ordered collection of finite, homogeneous data elements.

  1. Linked List
  2. Graph
  3. Tree
  4. Hash Table

Answer (Detailed Solution Below)

Option 4 : Hash Table

Searching Question 12 Detailed Solution

Download Solution PDF

Concept:

Homogeneous data structure (HDS):

  • HDS that contains only similar type of data like only integers or only float values.

  • Basic example of Homogeneous data structure is Array.


Explanation

In question we required ordered finite HDS which is nothing but Array but Array is not present in the

Options so we have to choose best option among them Let’s take option wise.

Option 1:  Linked list

Linked list is HDS but not finite because linked list size is decided on Run time.

Option 2: Graph

Graph is HDS but not finite because Graph size is decided on Run time.

Option 3:  Tree

Tree is HDS but not finite because Tree size is decided on Run time.

Option 4:  Hash Table

Hash table is ordered and finite data structure (Size is decided on Compile time ).

Hence option 4 is the Best option to choose for the answer.

Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst-case number of probes performed by an optimal algorithm is _____.

Answer (Detailed Solution Below) 5

Searching Question 13 Detailed Solution

Download Solution PDF

Worst case of the given problem is when a single 0 is followed by all 1’s i.e.

0111111111111……

Also, worst case can also be considered as when all 0’s are followed by single 1.

000000000………………1

Since, in both the cases there is a sorted sequence of 0 and 1 and for sorted sequence binary search is preferred.

At each stage,  element index is compared and if it is 1, search towards left and if it is 0 search towards right.

Total worst-case number of probes performed by an optimal algorithm is =  = 5

Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further, suppose our hashing scheme uses hfor the odd keys and h2 for the even keys. What is the expected number of keys in a slot? 

  1. m/n
  2. n/m
  3. 2n/m
  4. n/2m

Answer (Detailed Solution Below)

Option 2 : n/m

Searching Question 14 Detailed Solution

Download Solution PDF

The correct answer is option 2.

Concept:

Hashing is the method or practice of employing a hash function to map keys and values into a hash table. It is done so that items may be accessed more quickly. The effectiveness of the hash function employed determines the efficiency of mapping.

Explanation:

The given data,

Number of keys = n

Number of slots = m

According to the question, we must determine the number of expected keys in each slot, i.e. how many keys are feasible in each slot.

Analysis:

The performance of hashing can be evaluated under the assumption that each key is equally likely to be hashed to any slot of the table (simple uniform hashing). The average number of keys in a slot will be the total number of events that occur to the number of sample spaces i.e total number of slots.

Expected number of keys in a slot = Number of even keys / Total slots.

Expected number of keys in a slot = n/m.

So, each slot expected key should be n/m.

Hence the correct answer is n/m.

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

  1. (97 × 97 × 97) / 1003
  2. (99 × 98 × 97) / 1003
  3. (97 × 96 × 95) / 1003
  4. (97 × 96 × 95) / (3! × 1003)

Answer (Detailed Solution Below)

Option 1 : (97 × 97 × 97) / 1003

Searching Question 15 Detailed Solution

Download Solution PDF

Chaining:

  • Each slot may contain a chain of elements but in linear probing, we can insert only one element in every slot.

 

  • In order to insert element 1, we have 4 to 100 = 97 slots out of 100 slots
  • In order to insert second element, we have 4 to 100 = 97 slots out of 100 slots
  • In order to insert third element, we have 4 to 100 = 97 slots out of 100 slots
  • Required probability 


Hence option 1 is the correct option.

Hot Links: teen patti master gold download teen patti gold download teen patti royal real teen patti teen patti master downloadable content