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

The correct  answer is : option 2.

Key Points

Concept:

In Insertion Sort, the first pass (Pass 1) involves comparing the second element with the first element and swapping if needed to place it in the correct order.

Given List:

[9, 8, 14, 2, -8, 5]

Pass 1:

Only the first two elements are considered: 9 and 8

Since 8 < 9, a swap is required.

After Swap: [8, 9, 14, 2, -8, 5]

Number of Swaps in Pass 1: 1

Final Answer: 1

The correct answer is option 2.

Key PointsInitial Array:
7, 19, 18, 9, 23, 51, 12, 54, 73
Pass 1:
Compare 7 and 19: No swap (7 < 19)

Compare 19 and 18: Swap → 7, 18, 19, 9, 23, 51, 12, 54, 73

Compare 19 and 9: Swap → 7, 18, 9, 19, 23, 51, 12, 54, 73

Compare 19 and 23: No swap (19 < 23)

Compare 23 and 51: No swap (23 < 51)

Compare 51 and 12: Swap → 7, 18, 9, 19, 23, 12, 51, 54, 73

Compare 51 and 54: No swap (51 < 54)

Compare 54 and 73: No swap (54 < 73)

After Pass 1:
7, 18, 9, 19, 23, 12, 51, 54, 73
Pass 2:
Compare 7 and 18: No swap (7 < 18)

Compare 18 and 9: Swap → 7, 9, 18, 19, 23, 12, 51, 54, 73

Compare 18 and 19: No swap (18 < 19)

Compare 19 and 23: No swap (19 < 23)

Compare 23 and 12: Swap → 7, 9, 18, 19, 12, 23, 51, 54, 73

Compare 23 and 51: No swap (23 < 51)

Compare 51 and 54: No swap (51 < 54)

(No need to compare 54 and 73 again, as the largest elements are already being placed at the end in each pass)

After Pass 2:
7, 9, 18, 19, 12, 23, 51, 54, 73
Matching with Options:
Option 1: 7, 18, 19, 9, 23, 12, 51, 54, 73 → Incorrect (this is after Pass 1)

Option 2: 7, 9, 18, 19, 12, 23, 51, 54, 73 → Correct (matches our Pass 2 result)

Option 3: 7, 9, 19, 18, 12, 23, 51, 54, 73 → Incorrect (18 and 19 are out of order)

Option 4: 7, 9, 18, 19, 23, 51, 12, 54, 73 → Incorrect (12 is not in the correct position)

Final Answer:
Option 2) 7, 9, 18, 19, 12, 23, 51, 54, 73 is the correct result after pass 2.

Additional Information

• Bubble Sort has a time complexity of O(n^2) in the average and worst case.
• It is not suitable for large data sets due to its poor performance.
• However, it is simple to understand and implement.
• Bubble Sort is a stable sorting algorithm, meaning it maintains the relative order of equal elements.

The correct answer is 1.

Key Points

• Linear Search is a simple search algorithm that checks every element in the list sequentially until the desired element is found or the list ends.
• The minimum number of comparisons required to find an element in a list of 'n' elements using Linear Search is 1 if the element to be searched is at the first position.
• In the worst case, the element is not found or is the last element, requiring 'n' comparisons.
• Linear Search does not require the data to be sorted.
• This algorithm is best suited for small datasets or when the list is unsorted.

Additional Information

• Time complexity of Linear Search is O(n) in the worst case, where 'n' is the number of elements in the list.
• Linear Search is easy to implement but not efficient for large datasets compared to other search algorithms like Binary Search.
• Linear Search can be used on both arrays and linked lists.
• This algorithm does not require additional memory space, making it a space-efficient search method.

The correct answer is option 4.

Key Points

We are given four scenarios and need to arrange them in ascending order of their time complexity (i.e., from fastest to slowest).

Time Complexities:

• (A) Worst Case of Linear Search: O(n)
• (B) Best Case of Binary Search: O(1)
• (C) Worst Case of Binary Search: O(log n)
• (D) Worst Case of Bubble Sort: O(n²)

Arranging in ascending order:

1. (B) Best Case of Binary Search – O(1)
2. (C) Worst Case of Binary Search – O(log n)
3. (A) Worst Case of Linear Search – O(n)
4. (D) Worst Case of Bubble Sort – O(n²)

Correct Sequence: (B), (C), (A), (D)

Hence, the correct answer is: option 4

The correct answer is Option 1.

Key Points

• (A) For Binary Search, all the elements have to be sorted.
  • Binary Search is a searching algorithm that works on a sorted array. It divides the array into two halves and eliminates one half of the array in each step, making the search process more efficient.

Additional Information

• (B) For Linear Search, all the elements do not have to be sorted.
  • Linear Search is a simple searching algorithm that checks each element in the list sequentially until the desired element is found or the list ends. The elements do not need to be sorted.
• (C) Linear Search takes more time for searching in the worst case than binary search's worst case.
  • In the worst case, Linear Search has a time complexity of O(n), whereas Binary Search has a time complexity of O(log n), making Binary Search more efficient for larger datasets.
• (D) Linear Search does not always give fast results whether elements are sorted or not.
  • Linear Search can be slow for large lists as it checks each element sequentially. Sorting does not affect the performance of Linear Search.

The correct option is Dictionary

CONCEPT:

Hash Table is a data structure that stores data in an associative way that has a key-value pair and in which the address or the index value of the data element is generated from a hash function.

So Hash-based searching and insertion require 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 as the key values themselves become the index of the list which stores the data.

In Python, the Dictionary data type is an unordered collection of data values, used to store data values like a map representing the implementation of hash tables.

Keys of the dictionary are generated by hashing function which generates unique results for each unique value supplied to the hash function.

Example

dict = {'Name': 'Testbook', 'Course':'Hashing', 'Language': 'Python'}

We can use keys() mthod to get all the keys of dictionary "dict" as shown

dict.keys()
dict_keys(['Name', 'Course', 'Language'])

In Bubble Sort, the largest element should move to the extreme right position in every pass. 

So, to count the number of the swap, u need to count the right side smaller element of a particular element, Add all of them to find out the number of swaps. 

Swapping is done in bubble sort when a smaller element is found on the right side. 

For the List A - [5,12,2,34,40,32]  - 

For 5 right side smaller element - 1 (2)
For 12 right side smaller element - 1 (2)
For 2 right side smaller element - 0 
For 34 right side smaller element - 1 (32)   , For 40 right hand side smaller element - 1 (32) 
32 is the last element, so no need to check for that. Total number of swap - 1+1+1+1 = 4 swap required for List A .
 
For List B - [4,7,12,6,24,18]- 

For 4 right side smaller element - 0   For 7 right side smaller element - 1 (6)  
For 12 right side smaller element - 1 (6)     For 6 right side smaller element - 0 
For 24 , right hand side smaller element - 1 (18)  
18 is the last element , so, no need to check for that . 
Total number of swap - 1+1+1 = 3 swaps Required for List B 

So, List B requires the lowest swap using bubble sort. 

option 2 turns out to be the correct answer. 

The correct option is Given a list with sorted elements.

CONCEPT:

Binary search is a searching technique that makes use of the ordering of elements in the list to search a key quickly.

The key to be searched is compared with the element in the middle of a sorted list, this could result in any of the three possibilities:

i) If the element at the middle position matches the key the search is successful

ii) If the element at the middle position is greater than the key then the key element may be present in the left part of the list

iii) If the element at the middle position 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 to use binary search the given list must be sorted.

The correct answer is option 4.

Concept:

Selection sort:

The selection sort algorithm sorts an array by continually picking the smallest member from the unsorted segment and placing it at the beginning (in ascending order). In a given array, the method keeps two subarrays.

• This is the subarray that has previously been sorted.
• The remaining unsorted subarray.

Explanation:

Selection Sort has an O(n²) time complexity in the worst scenario if we have n values in our array. We now have a sorted array in the best scenario, but we still need to run over it O(n2) times to be sure! As a result, the time complexity of Selection Sort is the same in the best and worst cases.

• Selection sort in worst and best case take same time i.e., O(n²). So all the input takes the same time.

Hence the correct answer is All of the above take the same amount of time.

The correct option is None of the above.

CONCEPT:

Binary search is a searching technique that makes use of the ordering of elements in the list to search a key quickly.

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:

1.  matches the key. Thus the search is successful
2.  is smaller than the key, then the key element may be present in the right part of the list. Thus first=mid +1, to search the right half part only.
3.  is greater than the key, then the key element may be present in the left part of the list. Thus last=mid -1, to search the left half part only.

In the above question, the given list  L=[7,3,9,15,-6,11] is unordered/unsorted thus binary search cannot be applied to the given list.

The correct option is (1)

Concept:-

A simple approach is to do a linear search, i.e.

• Start from the leftmost element of arr[ ] and one by one compare X with each element of arr[ ]
• If X matches with an element, return the index
• If X does not match with any of the elements, return -1.

For example,

L=[2, 83, 63, 23, 96, 55, 12, 34, 24, 44]

X = 12

Element 12 is present at index 7,

Additional InformationLinear search:- Linear search is a sequential searching strategy in which we start at one end of the list and check each element until we find the target element. It is the most basic search algorithm.

Binary search:- A binary search is a search that finds the middle element is matched with a searched element.

In Bubble Sort, the largest element should move to the extreme right position in every pass. 

So, to count the number of the swap, u need to count the right side smaller element of a particular element, Add all of them to find out the number of swaps. 

Swapping is done in bubble sort when a smaller element is found on the right side. 

For the List A - [5,12,2,34,40,32]  - 

For 5 right side smaller element - 1 (2)
For 12 right side smaller element - 1 (2)
For 2 right side smaller element - 0 
For 34 right side smaller element - 1 (32)   , For 40 right hand side smaller element - 1 (32) 
32 is the last element, so no need to check for that. Total number of swap - 1+1+1+1 = 4 swap required for List A .
 
For List B - [4,7,12,6,24,18]- 

For 4 right side smaller element - 0   For 7 right side smaller element - 1 (6)  
For 12 right side smaller element - 1 (6)     For 6 right side smaller element - 0 
For 24 , right hand side smaller element - 1 (18)  
18 is the last element , so, no need to check for that . 
Total number of swap - 1+1+1 = 3 swaps Required for List B 

So, List B requires the lowest swap using bubble sort. 

option 2 turns out to be the correct answer. 

Correct option is first = mid + 1 ,  last = mid - 1

CONCEPT:

Binary search is a searching technique that makes use of the ordering of elements in the list to search a key quickly.

The key to be searched is compared with the element in the middle of a sorted list, this could result in any of the three possibilities.

If the element at the middle position:

1.  matches the key. Thus the search is successful
2.  is smaller than the key, then the key element may be present in the right part of the list. Thus first=mid +1, to search the right half part only.
3.  is greater than the key, then the key element may be present in the left part of the list. Thus last=mid -1, to search the left half part only.

This splitting and reduction in list size continue till the key is found or the remaining list consists of only one item.

The correct option is Dictionary

CONCEPT:

Hash Table is a data structure that stores data in an associative way that has a key-value pair and in which the address or the index value of the data element is generated from a hash function.

So Hash-based searching and insertion require 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 as the key values themselves become the index of the list which stores the data.

In Python, the Dictionary data type is an unordered collection of data values, used to store data values like a map representing the implementation of hash tables.

Keys of the dictionary are generated by hashing function which generates unique results for each unique value supplied to the hash function.

Example

dict = {'Name': 'Testbook', 'Course':'Hashing', 'Language': 'Python'}

We can use keys() mthod to get all the keys of dictionary "dict" as shown

dict.keys()
dict_keys(['Name', 'Course', 'Language'])

Correct answer: Option 2

Explanation:

• The binary search method works on sorted arrays only. It checks the middle element with the search element. If it matches, the index is returned. Otherwise, if the search element is lesser than the middle element then the algorithm repeats the process in the left half of the array. Else, it searches in the right half of the array.
• The loop for the program runs as long as the value of first is less than or equal to the value of last. So, the error lies in statement 2.
• In statement 1, the last index of the array is being determined. Since the array indexes start from 0, the last index is one less than the total length of the array. So, this statement is correct.
• Statement 3 returns the index value where the element is found, if it exists in the array. So, this statement is correct too.
• Statement 4 is a return statement in case the element does not exist in the array. The first return statement is inside an if-block. Hence, this second return statement, is not an erroneous statement.

Important points:

The correct statement 2 should be ‘while(first <= last):’ for the program to run correctly.