/* */ Click to Join Live Class with Shankar sir Call 9798158723

Data Structure MCQ - Linear Search


Q1.Is there any difference in the speed of execution between linear serach(recursive) vs linear search(lterative)?
  1. Both execute at same speed
  2. Linear search(recursive) is faster
  3. Linear search(Iterative) is faster
  4. Cant be said

Answer:- (C).
Explanations :The Iterative algorithm is faster than the latter as recursive algorithm has overheads like calling function and registering stacks repeatedly.
Q2. Is there any difference in the speed of execution between linear serach(recursive) vs linear search(lterative)?
  1. Both execute at same speed
  2. Linear search(recursive) is faster
  3. Linear search(Iterative) is faster
  4. Cant be said

Answer:- (C).
Explanations :The Iterative algorithm is faster than the latter as recursive algorithm has overheads like calling function and registering stacks repeatedly.
Q3.What is the output of following program? 
#include 
 
 void print(int n, int j)
 {
	if (j >= n)
	   return;
	if (n-j > 0 && n-j >= j)
		printf("%d %dn", j, n-j);
	print(n, j+1);
 }
  
 int main()
 {
	 int n = 8;
	 print(n, 1);
 }
  1. 1 7
    2 6
    3 5
    4 4
    4 4
  2. 1 7
    2 6
    3 5
    4 4
  3. 1 7
    2 6
    3 5
  4. 1 2
    3 4
    5 6
    7 8

Answer:- (B).
Explanations :For a given number n, the program prints all distinct pairs of positive integers with sum equal to n.
Q4.For a given number n, the program prints all distinct pairs of positive integers with sum equal to n.
  1. 14
  2. 2
  3. 6
  4. 3

Answer:- (b).
Q5.What is the worst case for linear search?
  1. O(nlogn)
  2. O(logn)
  3. O(n)
  4. O(1)

Answer:- (C).
Explanations : 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).
Q6.Is the space consumed by the linear search(recursive) and linear search(iterative) same?
  1. No, recursive algorithm consumes more space
  2. No, recursive algorithm consumes less space
  3. yes
  4. Nothing can be said

Answer:- (A).
Explanations :The recursive algorithm consumes more space as it involves the usage the stack space(calls the function numerous times).
Q7.Linear search(recursive) algorithm used in _____________
  1. When the size of the dataset is low
  2. When the size of the dataset is large
  3. When the dataset is unordered
  4. Never used

Answer:- (A).
Explanations :It is used when the size of the dataset is low as its runtime is O(n) which is more when compared to the binary search O(logn).
Q8.The array is as follows: 1,2,3,6,8,10. At what time the element 6 is found? (By using linear search(recursive) algorithm)
  1. 4th call
  2. 3th call
  3. 6th call
  4. 5th call

Answer:- (A).
Explanations :Provided that the search starts from the first element, the function calls itself till the element is found. In this case, the element is found in 4th call.
Q9.Given a sorted array of integers, what can be the minimum worst case time complexity to find ceiling of a number x in given array? Ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then output should be 100.
  1. O(LogLogn)
  2. O(n)
  3. O(Logn)
  4. O(Logn * Logn)

Answer:- (C).
Explanations :We modify standard binary search to find ceiling. The time complexity T(n) can be written as T(n) <= T(n/2) + O(1) Solution of above recurrence can be obtained by Master Method. It falls in case 2 of Master Method. Solution is O(Logn). [sourcecode language="C"] #include /* Function to get index of ceiling of x in arr[low..high]*/ int ceilSearch(int arr[], int low, int high, int x) { int mid; /* If x is smaller than or equal to the first element, then return the first element */ if(x <= arr[low]) return low; /* If x is greater than the last element, then return -1 */ if(x > arr[high]) return -1; /* get the index of middle element of arr[low..high]*/ mid = (low + high)/2; /* low + (high - low)/2 */ /* If x is same as middle element, then return mid */ if(arr[mid] == x) return mid; /* If x is greater than arr[mid], then either arr[mid + 1] is ceiling of x or ceiling lies in arr[mid+1...high] */ else if(arr[mid] < x) { if(mid + 1 <= high && x <= arr[mid+1]) return mid + 1; else return ceilSearch(arr, mid+1, high, x); } /* If x is smaller than arr[mid], then either arr[mid] is ceiling of x or ceiling lies in arr[mid-1...high] */ else { if(mid - 1 >= low && x > arr[mid-1]) return mid; else return ceilSearch(arr, low, mid - 1, x); } } /* Driver program to check above functions */ int main() { int arr[] = {1, 2, 8, 10, 10, 12, 19}; int n = sizeof(arr)/sizeof(arr[0]); int x = 20; int index = ceilSearch(arr, 0, n-1, x); if(index == -1) printf("Ceiling of %d doesn't exist in array ", x); else printf("ceiling of %d is %d", x, arr[index]); getchar(); return 0; } [/sourcecode]
Q10.What is the best case runtime of linear search(recursive) algorithm on an ordered set of elements?
  1. O(1)
  2. O(n)
  3. O(logn)
  4. O(nx)

Answer:- (A).


«  PREVIOUS PAGE NEXT PAGE »

Copyright © 2022 Shineskill Software Pvt. Ltd., All rights reserved.