Searching MCQ Quiz in मल्याळम - Objective Question with Answer for Searching - സൗജന്യ PDF ഡൗൺലോഡ് ചെയ്യുക
Last updated on Mar 19, 2025
Latest Searching MCQ Objective Questions
Top Searching MCQ Objective Questions
Searching Question 1:
Consider the following array:
A = {2, 5, 8, 17, 19, 34, 45, 67, 78, 87}
What is the time complexity of the binary search algorithm when 98 is searched?
Answer (Detailed Solution Below)
Searching Question 1 Detailed Solution
It is the worst case scenario of binary search.
The worst case for binary search is when the value x is not in the set L as then the algorithm has to perform the maximum possible number of recursive calls, and hence the maximum possible number of operations.
Therefore, the worst case time complexity of binary search is O(logn).
Searching Question 2:
The searching technique in which the there are no unnecessary comparisons is called.
Answer (Detailed Solution Below)
Searching Question 2 Detailed Solution
The correct answer is Hashing.
This question can be solved by some basic understanding of every type of search.
Let's go one by one -
Binary searching:- In binary searching, you have a sorted array, and you divide that array according to the mid element, Then either you have to go left or right and search till the end until you find the required element.
This involves unnecessary comparison. So, option 1 got eliminated.
Sequential searching:- Here, This searching technique involves Finding a particular value in a list that consists of Checking All of its elements, one at a time and in sequence until the desired element is found.
This involves unnecessary comparison, so, option 2 got eliminated.
Hashing-It is the best searching technique available with O(1) time complexity, it has a table consisting of key-value pairs, and directly with the help of key u can reach to value.
So, no unnecessary comparison is needed,
Refer to the below diagram to understand it better
So, option 3 will be the answer here
Searching Question 3:
Which of the following behaviour takes smallest time in linear serach ?
Answer (Detailed Solution Below)
Searching Question 3 Detailed Solution
The correct answer is option 1.
Concept:
Linear search:
A linear search, often known as a sequential search, is a technique for locating an element in a list. It systematically verifies each element of the list until a match is discovered or the entire list has been searched.
Algorithm:
linear_search(int a[], int n, int X)
{
for (int i = 0; i < n; i++)
{
if (a[i] == X)
return i+1;
}
}
Explanation:
Best case:
The best case in the Linear Search Algorithm happens when the item to be found is at the beginning of the Array. If the element is found at starting of the array the linear search successful and comes out from the loop. Hence this behavior takes less time when compared to other behaviors.
Worst-case:
In the Linear Search Algorithm, the worst-case scenario happens when the item to be found is at the end of the Array or the element is not present in the array. Hence the linear search compares each element till the end. So it takes maximum time behavior in linear search.
Average case:
In the Linear Search Algorithm, the average scenario happens when the item to be found is somewhere in the center of the Array.
Hence the correct answer is a searching element is at beginning of the array.
Searching Question 4:
The average number of comparisions performed in sequencial search on a list of n elements is
Answer (Detailed Solution Below)
Searching Question 4 Detailed Solution
The average number of comparisons in a sequential search is \({(N+1)} \over 2\) where N is the size of the array.
If the element is in the 1st position, the number of comparisons will be 1,
the element is in the 2nd position, the number of comparisons will be 2,
the element is in the 3rd position, the number of comparisons will be 3,
the element is in the 4th position, the number of comparisons will be 4, .....
if the element is in the last position, the number of comparisons will be N.
So Total number of comparisons are= (1+2+3+4+5+...+N)
The total number of comparisons are=\({N(N+1)} \over 2\)
The average number of comparisons in a sequential search is \({N(N+1)} \over 2 \times N\)
Hence the correct answer is \({(N+1)} \over 2\)
Searching Question 5:
Which collision resolution technique involves placing collided elements in the next available empty slot in the hash table?
Answer (Detailed Solution Below)
Searching Question 5 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 6:
In hashing, collision results when _______.
Answer (Detailed Solution Below)
Searching Question 6 Detailed Solution
Searching Question 7:
Consider the hashing table with ‘m’ slots and ‘n’ keys. If the expected number of probes in an unsuccessful search is 5, the expected number of probes in successful search is________
(Up to 2 decimals)Answer (Detailed Solution Below) 2.01 - 2.02
Searching Question 7 Detailed Solution
Formula:
Expected number of probes in unsuccessful search = \(\frac{1}{{1 - p}}\)
Expected number of probes in successful search = \(\frac{1}{p}\ln \left( {\frac{1}{{1 - p}}} \right)\)
\(p = \frac{n}{m}\)
where p is load factor.
Calculation:
\(\frac{1}{{1 - p}} = 5\)
1 = 5 – 5p
5p = 4
\(p = \frac{4}{5}\)
\(\frac{1}{p}\ln \left( {\frac{1}{{1 - p}}} \right) = \frac{5}{4}\ln \left( {\frac{1}{{1 - \frac{4}{5}\;}}} \right) = \frac{5}{4}\ln \left( 5 \right) = \frac{5}{4} \times 1.609 = 2.011\)
So, number of probes in successful search is 2.01
Searching Question 8:
In a hash table with 40 slots 60 records are inserted with collisions being resolved by chaining. What is the expected number of key comparisons in an unsuccessful search assuming uniform hashing?
Answer (Detailed Solution Below) 1.50
Searching Question 8 Detailed Solution
Answer: 1.5
Explanation:
In a hash-table with chaining and uniform hashing, the expected number of comparisons in an unsuccessful search is given by
α, where α is the load factor
\(\alpha = \frac{m}{n} = \frac{{60}}{{40}} = 1.5\)
Here, So, expected
number of comparisons for an unsuccessful search = 1.5
Searching Question 9:
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 9 Detailed Solution
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, \(\frac{{low + high}}{2}\) 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 = \(lo{g_2}31\) = 5Searching Question 10:
Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and has table size is 10. What is the order of elements(from index 0 to size-1) in the hash table?
Answer (Detailed Solution Below)
Searching Question 10 Detailed Solution
The correct answer is option 2.
Concept:
Hashing:
Hashing is the process of employing an algorithm to turn any length of input into a fixed-size string or integer. The principle behind hashing is to utilize a hash function to transform a given key to a smaller integer, which is then used as an index in a hash table.
A simple hash function that works with numeric values is known as the remainder method. It takes an element from a list and divides it by the size of the hash table. The remainder so generated is called the hash value.
h(element) = element % size(hash table)
Explanation:
The given data,
list of numbers (34, 16, 2, 93, 80, 77, 51) and has a table size is 10.
Element | Hash function | Index |
34 | 34%10 =4 | 4 |
16 | 16%10 =6 | 6 |
2 | 2%10 =2 | 2 |
93 | 93 % 10 = 3 | 3 |
80 | 80 %10 =0 | 0 |
77 | 77% 10= 7 | 7 |
51 | 51 % 10 = 1 | 1 |
The hash table is,
index | Value |
0 | 80 |
1 | 51 |
2 | 2 |
3 | 93 |
4 | 34 |
5 | |
6 | 16 |
7 | 77 |
8 | |
9 |
The remaining index stores the null values.
Hence the correct answer is 80, 51, 2, 93, 34, null, 16, 77, null, null.