Data Structure Multiple Choice Questions – Linear Search

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Linear Search”.

1. Where is linear searching used?
a) When the list has only a few elements
b) When performing a single search in an unordered list
c) Used all the time
d) When the list has only a few elements and When performing a single search in an unordered list
View Answer

Answer: d
Explanation: It is practical to implement linear search in the situations mentioned in When the list has only a few elements and When performing a single search in an unordered list, but for larger elements the complexity becomes larger and it makes sense to sort the list and employ binary search or hashing.

2. Select the code snippet which performs unordered linear search iteratively?
a)

int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}

b)

advertisement
advertisement
int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == data)
        {
            break;
        }
    }
    return index;
}

c)

Note: Join free Sanfoundry classes at Telegram or Youtube
int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i <= size; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}

d)

advertisement
int unorderedLinearSearch(int arr[], int size, int data)
{
    int index;
    for(int i = 0; i < size-1; i++)
    {
        if(arr[i] == data)
        {
            index = i;
            break;
        }
    }
    return index;
}
View Answer
Answer: a
Explanation: Unordered term refers to the given array, that is, the elements need not be ordered. To search for an element in such an array, we need to loop through the elements until the desired element is found.
 
 

3. What is the best case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
View Answer

Answer: d
Explanation: The element is at the head of the array, hence O(1).
advertisement

4. What is the worst case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
View Answer

Answer: c
Explanation: Worst case is when the desired element is at the tail of the array or not present at all, in this case you have to traverse till the end of the array, hence the complexity is O(n).

5. Select the code snippet which performs ordered linear search iteratively?
a)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		  index = i;
             }
             if(data[i] > key)) 
             {
		 index = i;
                 break;
             }
             i++;
       }
       return index;
}

b)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		  index = i;
             }
             if(data[i] > key)) 
             {
                  break;
             }
             i++;
       }
       return index;
}

c)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		break;
             }
             if(data[i] > key)) 
             {
                 index = i;
             }
             i++;
        }
        return index;
}

d)

public int linearSearch(int arr[],int key,int size) 
{
       int index = -1;
	   int i = 0;
       while(size > 0) 
       {
             if(data[i] == key) 
             {
		break;
             }
             if(data[i] > key)) 
             {
                 break;
                 index=i; 
             }
             i++;
        }
        return index;
}
View Answer
Answer: b
Explanation: The term ordered refers to the items in the array being sorted(here we assume ascending order). So traverse through the array until the element, if at any time the value at i exceeds key value, it means the element is not present in the array. This provides a slightly better efficiency than unordered linear search.
 
 

6. What is the best case and worst case complexity of ordered linear search?
a) O(nlogn), O(logn)
b) O(logn), O(nlogn)
c) O(n), O(1)
d) O(1), O(n)
View Answer

Answer: d
Explanation: Although ordered linear search is better than unordered when the element is not present in the array, the best and worst cases still remain the same, with the key element being found at first position or at last position.

7. Choose the code snippet which uses recursion for linear search.
a)

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

b)

      public void linSearch(int[] arr, int first, int last, int key)
      {
		if(first == last)
                {
			System.out.print("-1");
		}
		else
                {
			if(arr[first] == key)
                        {
				System.out.print(first);
			}
			else
                        {
				linSearch(arr, first+1, last-1, key);
			}
		}
      }

c)

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(last);
		}
		else
                {
			linSearch(arr, first+1, last, key);
		}
	}
}

d)

public void linSearch(int[] arr, int first, int last, int key)
{
	if(first == last)
        {
		System.out.print("-1");
	}
	else
        {
		if(arr[first] == key)
                {
			System.out.print(first);
		}
		else
                {
			linSearch(arr, first+1, last+1, key);
		}
	}
}
View Answer
Answer: a
Explanation: Every time check the key with the array value at first index, if it is not equal then call the function again with an incremented first index.
 
 

8. What does the following piece of code do?

for (int i = 0; i < arr.length-1; i++)
{
    for (int j = i+1; j < arr.length; j++)
    {
        if( (arr[i].equals(arr[j])) && (i != j) )
        {
            System.out.println(arr[i]);
        }
    }
}

a) Print the duplicate elements in the array
b) Print the element with maximum frequency
c) Print the unique elements in the array
d) Prints the element with minimum frequnecy
View Answer

Answer: a
Explanation: The print statement is executed only when the items are equal and their indices are not.

9. Select the code snippet which prints the element with maximum frequency.
a)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++)
        {
		if (a[i] == previous)
		count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
		previous = a[i];
		count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

b)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

c)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i+1] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}

d)

public int findPopular(int[] a) 
{
	if (a == null || a.length == 0)
		return 0;
	Arrays.sort(a);
	int previous = a[0];
	int popular = a[0];
	int count = 1;
	int maxCount = 1;
	for (int i = 1; i < a.length; i++) 
        {
		if (a[i+2] == previous)
			count++;
		else 
                {
			if (count > maxCount) 
                        {
				popular = a[i-1];
				maxCount = count;
			}
			previous = a[i];
			count = 1;
		}
	}
	return count > maxCount ? a[a.length-1] : popular;
}
View Answer
Answer: a
Explanation: Traverse through the array and see if it is equal to the previous element, since the array is sorted this method works with a time complexity of O(nlogn), without sorting a Brute force technique must be applied for which the time complexity will be O(n2).

10. Which of the following is a disadvantage of linear search?
a) Requires more space
b) Greater time complexities compared to other searching algorithms
c) Not easy to understand
d) Not easy to implement
View Answer

Answer: b
Explanation: The complexity of linear search as the name suggests is O(n) which is much greater than other searching techniques like binary search(O(logn)). Linear search is easy to implement and understand than other searching techniques.

More MCQs on Linear Search:

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.