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

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.

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.

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.

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

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.

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 2^nd

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

Search: 2

In first comparison, 2 is found

Best case time complexity is O(1)

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

50 > 32

50

matched

T(n) = O(log n)

Also, for average case:

T(n) = O(log n)

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

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.

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

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.

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

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.

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.