CUET Computer Science MCQs Chapter 4 Searching

Question. Linear search is also called------
a) Random Search
b) Sequential search
c) Perfect search
d) None

Answer : B

Question. Which of the following is the correct recurrence for the worst case of Ternary Search?
a) T(n) = T(n/3) + 4, T(1) = 1
b) T(n) = T(n/2) + 2, T(1) = 1
c) T(n) = T(n + 2) + 2, T(1) = 1
d) T(n) = T(n - 2) + 2, T(1) = 1

Answer : A

Question. Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n-1;
do
{
k = (i+j)/2;
if (x <= listA[k])
j = k-1;
if (listA[k] <= x)
i = k+1;
}
while (i <= j);
if (listA[k] == x)
return(k);
else
return -1;
}
Which one of the following statements about the function ProcessArray is CORRECT?
a) It will run into an infinite loop when x is not in listA.
b) It is an implementation of binary search.
c) It will always find the maximum element in listA.
d) It will return −1 even when x is present in listA.

Answer : B

Question. What is wrong with the below algorithm for searching the missing number from 1 to n?
int getMissingNo(int a[], int n)
{
int i, total;
total = (n + 1) * (n + 2) / 2;
for (i = 0; i < n; i++)
total += a[i];
return total;
}
a) variable 'total' can not be modified.
b) Infinite loop
c) Run time error
d) we are using Add("+") operation instead of subtraction("-").

Answer : D

Question. The time taken by binary search algorithm to search a key in a sorted array of n elements is
a) O ( log2n )
b) O ( n )
c) O ( n log2n )
d) O ( n^2)

Answer : A

Question. Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 
1. f(int Y[10], int x) {
2. int i, j, k;
3. i = 0; j = 9;
4. do {
5. k = (i + j) /2;
6. if( Y[k] < x) i = k; else j = k;
7. } while(Y[k] != x && i < j);
8. if(Y[k] == x) printf (\"x is in the array \") ;
9. else printf (\" x is not in the array \") ;
10. }
On which of the following contents of Y and x does the program fail?
a) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
b) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
c) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
d) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

Answer : C

Question. How many comparisons are required in the worst case a traditional linear search utilizes?
a) N
b) N + 1
c) 2N
d) N + 2

Answer : D

Question. what is the output of the below code if the input array is [12, 34, 56, 29, 78]. and the X= 21?
int fun(int arr[], int N, int x)
{
for (int i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
a) 0
b) 1
c) -1
d) None

Answer : C

Question. Which of the following is correct recurrence for worst case of Binary Search?
a) T(n) = 2T(n/2) + O(1) and T(1) = T(0) = O(1)
b) T(n) = T(n-1) + O(1) and T(1) = T(0) = O(1)
c) T(n) = T(n/2) + O(1) and T(1) = T(0) = O(1)
d) T(n) = T(n-2) + O(1) and T(1) = T(0) = O(1)

Answer : C

Question. The increasing order of performance of the searching algorithms are:
a) linear search < jump search < binary search
b) linear search > jump search < binary search
c) linear search < jump search > binary search
d) linear search > jump search > binary search

Answer : A

Question. Consider the following program that attempts to locate an element x in a sorted array a[ ] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?
var i,j,k: integer; x: integer;
a: array; [1....N] of integer;
begin i:= 1; j:= N;
repeat
k:(i+j) div 2;
if a[k] < x then i:= k
else j:= k
until (a[k] = x) or (i >= j);
if (a[k] = x) then
writeln (\'x is in the array\')
else
writeln (\'x is not in the array\')
end;
a) x is the last element of the array a[]
b) x is greater than all elements of the array a[]
c) Both of the Above
d) x is less than the last element of the array a[]

Answer : C

Question. Match the following:
               List - I                               List - II
(a) Sequential Search                (i) Dynamic programming principle
(b)Branch - and - bound            (ii) repeatedly double index
(c) Exponential Search              (iii) O(LogN)
(d) Binary Search                     (iv) O(N)
codes:
     (a) (b)  (c) (d)
(1) (i) (iv) (iii) (ii)
(2) (iv) (i) (ii) (iii)
(3) (i) (iv) (ii) (iii)
(4) (iv) (ii) (i) (iii)
a) (1)
b) (2)
c) (3)
d) (4)

Answer : B

Question. What is sentinel value in Sentinel Linear Search?
a) The middle element
b) The second element
c) The last element
d) None

Answer : C

Question. Match the following:
            List - I                                 List - II
(a) Fibonacci Search                   (i) O(N)
(b) Jump Search                        (ii) O(√N)
(c) Sentinel Linear Search          (iii) O(log2(log2 n))
(d) Interpolation Search             (iv) F(n) = F(n-1) + F(n-2)
Hints:
     (a) (b)  (c) (d)
(1) (i) (iv) (iii) (ii)
(2) (iv) (i) (ii) (iii)
(3) (i) (iv) (ii) (iii)
(4) (iv) (ii) (i) (iii)
a) (1)
b) (2)
c) (3)
d) (4)

Answer : D

Question. 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? The 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 the output should be 100.
a) O(loglogn)
b) O(n)
c) O(log(n))
d) O(log(n) * log(n))

Answer : C

Question. The average case occurs in the Linear Search Algorithm when:
a) The item to be searched is in some where middle of the Array
b) The item to be searched is not in the array
c) The item to be searched is in the last of the array
d) The item to be searched is either in the last or not in the array

Answer : A

Question. Suppose there are 11 items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?
a) 3.00
b) 3.46
c) 2.81
d) 3.33

Answer : A

Question. what is the name of the below searching Algorithm?
int function(vector<int> arr,int x){
int n = arr.size();
if(n == 0)
return -1;
// Find range for binary search by repeatedly doubling i
int i = 1;
while(i < n and arr[i] < x)
i *= 2;
// Perform binary search on the range [i/2, min(i, n-1)]
int left = i /2;
int right = min(i, n-1);
while(left <= right){
int mid = (left + right)/2;
if(arr[mid] == x) return mid;
else if(arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}
a) Linear Search
b) Sequential Search
c) Jump Search
d) Exponential Search

Answer : D

Question. What are the advantages of Linear Search Over Binary Search?
a) The array is ordered.
b) Less number of comparison
c) less time and space complexity
d) Linear search can be used irrespective of whether the array is sorted or not

Answer : D

Question. 1. f(int Y[10], int x) {
2. int i, j, k;
3. i = 0; j = 9;
4. do {
5. k = (i + j) /2;
6. if( Y[k] < x) i = k; else j = k;
7. } while(Y[k] != x && i < j);
8. if(Y[k] == x) printf ("x is in the array ") ;
9. else printf (" x is not in the array ") ;
10. }
In the above question, the correction needed in the program to make it work properly is 
a) Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;
b) Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;
c) Change line 6 to: if (Y[k] <= x) i = k; else j = k;
d) Change line 7 to: } while ((Y[k] == x) && (i < j));

Answer : A

Question. The average number of key comparisons done in a successful sequential search in a list of length n is
a) log n
b) (n-1)/2
c) n/2
d) (n+1)/2

Answer : D

Question. Which of the following statements is true for Branch - and - Bound search?
a) Underestimates of remaining distance may cause deviation from optimal path.
b) Overestimates can\'t cause right path to be overlooked.
c) Dynamic programming principle can be used to discard redundant partial paths.
d) All of the above

Answer : C

Question. The necessary condition for using binary search in an array is :-
a) The array should not be too long
b) The array should of more size
c) The array should be sorted
d) None of these

Answer : C

Question. What is the time complexity for performing Jump search?
a) O(LogN)
b) O(N)
c) O(N^2)
d) O(√N)

Answer : D

Question. Consider a sorted array of n numbers and a number x. What would be the time complexity of the best known algorithm to find a triplet with sum equal to x. For example, arr[] = {1, 5, 10, 15, 20, 30}, x = 40. Then there is a triplet {5, 15, 20} with sum 40.
a) O(n)
b) O(n^2)
c) O(n Log n)
d) O(n^3)

Answer : B

Question. Number of comparisons required for an unsuccessful search of an element in a sequential search, organized, fixed length, symbol table of length L is
a) L
b) L/2
c) (L+1)/2
d) 2L

Answer : A

Question. The recurrence relation that arises in relation with the complexity of binary search is:
a) T(n) = 2T(n/ 2) + k , where k is constant
b) T(n) = T(n / 2) + k , where k is constant
c) T(n) = T(n / 2) + log n
d) T(n) = T(n / 2) + n

Answer : B

Question. In the worst case, (for instance where the numerical values of the keys increase exponentially) the interpolation search technique will take how many comparisons.?
a) O(N)
b) O(logN)
c) O(loglogN)
d) None

Answer : A