Searching

Question 1

Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________.

A
5
B
6
C
7
D
8
       Algorithms       Searching       GATE 2017 [Set-1]
Question 1 Explanation: 
→ If we apply binary search to find the first occurrence of 1 in the list, it will give us the smallest index i where 1 is stored.
→ As in this array sequence of 0’s is followed by sequence of 1’s, the array is sorted. We can apply binary search directly without sorting it.
So number of probes = ceil(log2 31) = 4.954196310386876
⇒ here we are using ceiling so it becomes 5
Question 2

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.
       Algorithms       Searching       GATE 2014 [Set-3]
Question 2 Explanation: 
From the above code, we can identify
k = (i+j)/2;
where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.
So it is an implementation of Binary search.
Question 3

Consider the following algorithm for searching for a given number x in an unsorted array A[1...n] having n distinct values:

        1. Choose an i uniformly at random from 1...n;
        2. If A[i]=x then Stop else Goto 1; 

Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

A
n
B
n-1
C
2n
D
n/2
       Algorithms        Searching       GATE 2002
Question 3 Explanation: 
Question 4

Which one of the following statements is false?

A
Optimal binary search tree construction can be performed efficiently using dynamic programming.
B
Breadth-first search cannot be used to find converted components of a graph.
C
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D
Depth-first search can be used to find connected components of a graph.
       Algorithms       Searching       GATE 1994
Question 4 Explanation: 
In BFS algorithm, we can randomly select a source vertex and then run, after that whether we need to check distance to each and every vertex from source is still infinite (or) not. If we find any vertex having infinite distance then the graph is not connected.
Question 5
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 ( n2 )
       Algorithms       Searching       ISRO-2007
Question 5 Explanation: 
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. It takes a maximum of log(n) searches to search an element from the sorted array.
Question 6
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)+logn
D
T(n)=T(n/2)+n
       Algorithms       Searching       ISRO-2017 May
Question 6 Explanation: 
Binary search in a sorted array
The time to search in an array of ‘n’ elements is equal to the time to search in an array of n/2 elements plus k comparison.
T(n)=T(n/2)+k // k is constant
Question 7
The time required to search an element in a linked list of length n is
A
O(log n)
B
O(n)
C
O(1)
D
(n2)
       Data-Structures       Searching       ISRO CS 2008
Question 7 Explanation: 
In the worst case, the element to be searched has to be compared with all elements of linked list. It will take O(n) time to search the element.
Question 8
The time required to search an element in a linked list of length n is
A
O(log n)
B
O(n)
C
O(1)
D
O(n2)
       Data-Structures       Searching       ISRO CS 2008
Question 8 Explanation: 
In the worst case, the element to be searched has to be compared with all elements of linked list, so the time complexity is O(n)
Question 9
The average number of key comparisons required for a successful search for sequential search on items is
A
n/2
B
(n-1)/2
C
(n+1)/2
D
None of these
       Algorithms       Searching       ISRO-2016
Question 9 Explanation: 
Total comparisons required
= No. of comparisons if element present in 1st position + No. of comparisons if element present in 2ndnd position + ............. + No. of comparisons if element present in nth position
= 1+2+3+ ... + n
= n(n+1)/2
Since there are n elements in the list, so average no. of comparisons
= Total comparisons/Total no. of elements
= (n(n+1)/2)/n
= n+1/2
Question 10
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
       Algorithms       Searching       ISRO CS 2011
Question 10 Explanation: 
A linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched
A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list , whether element is found or not
Question 11
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
       Algorithms       Searching       ISRO CS 2014
Question 11 Explanation: 
We can arrange 11 items in the four levels(level-0,1,2,3).
Each level has 2i nodes where i is level number
Level -0 has one node so one comparison(1)
Level -1 has two nodes so for each node two comparisons and total four comparisons (4)
Level -2 has four nodes and total comparisons are 4x3 =12 comparisons
Level-3 has total 8 nodes but in the given question we need to process only 11 items and already we covered 7 nodes so remaining nodes 4 nodes at level -3. Total comparisons at level-3 are 4*4=16
So, total number of comparisons at each level are = 1+4+12+16= 33
Average comparisons required for 11 items = 33/11 = 3
Question 12
The question is based on the following program fragment.
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k] i=k;
else
j=k;
}
while((Y[k]!=x) && (i if(Y[k] ==x)
printf("x is in the array");
else
printf("x is not in the array");
}
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
       Algorithms       Searching       Nielit Scientific Assistance IT 15-10-2017
Question 12 Explanation: 
This above code is similar to binary search
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k] Second iteration :
I=0, j=k=4
K= (0+4)/2=2.
Third iteration:
I=0, j=k=2
K= (0+2)/2=1
Fourth iteration:
I=0, j=k=1
K= (0+1)/2=0
The while condition is Y[k] != x && i < j is true
● The above program doesn’t work for the cases where element to be searched is the last element of Y[ ] or greater than the last element (or maximum element) in Y[ ].
● For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j.
● So while condition never becomes false.
Question 13
The question is based on the following program fragment.
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k] i=k;
else
j=k;
}while((Y[k]!=x) && (i if(Y[k] ==x)
printf("x is in the array");
else
printf("x is not in the array");
}
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
       Algorithms       Searching       Nielit Scientific Assistance CS 15-10-2017
Question 13 Explanation: 
This above code is similar to binary search
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k] Second iteration :
I=0, j=k=4
K= (0+4)/2=2.
Third iteration:
I=0, j=k=2
K= (0+2)/2=1
Fourth iteration:
I=0, j=k=1
K= (0+1)/2=0
The while condition is Y[k] != x && i < j is true
→ The above program doesn’t work for the cases where element to be searched is the last element of Y[ ] or greater than the last element (or maximum element) in Y[ ].
→ For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j.
So, while condition never becomes false.
Question 14
The complexity of linear search algorithm is
A
O(nlogn)
B
O(n)
C
O(logn)
D
O(n*n)
       Algorithms       Searching       KVS DEC-2017
Question 14 Explanation: 
→ Linear search algorithm will traverse all nodes with increment by one element in linear fashion(order).
→ So, it takes time complexity O(n)
Question 15
The maximum number of comparisons for a particular record among 32 sorted recorder through binary search method will be
A
2
B
10
C
8
D
5
       Algorithms       Searching       KVS DEC-2017
Question 15 Explanation: 
Step-1: Binary search we are using formula O(log​ 2​ n)
Sep-2: The maximum number of comparisons for a particular record among 32 sorted recorder through binary search method will be O(log​ 2​ 32)=5
Question 16
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16 What is the height of the binary search tree ?
A
3
B
4
C
5
D
6
       Algorithms       Searching       UGC NET CS 2017 Nov- paper-2
Question 16 Explanation: 

Height of the binary search tree = 3
Question 17
A and B are two sorted lists of integers such that A[n]<B[1]. An element is to be searched in both lists. Maximum number of comparisons using binary search is
A
2*log2 n
B
log2 2n
C
log2 (2n+1)
D
2*log2 n+1
       Algorithms       Searching       KVS 30-12-2018 Part B
Question 17 Explanation: 
In general, if N is the size of the list to be searched and C is the number of comparisons to do so in the worst case, C = log2N. In the question two sorted list of elements with the condition A[n]22N
Question 18
Postorder traversal of a given binary search tree T produces following sequence of keys:3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?
A
3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15
B
20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9
C
20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3
D
3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20
       Algorithms       Searching       UGC NET CS 2017 Nov- paper-2
Question 18 Explanation: 
We can easily find solutions based on given options because option D given all numbers in ascending order. In Order will print ascending order only.
Question 19
The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is:
A
O(lg n)
B
O(n lg n)
C
O(n)
D
O(n​ 2​ )
       Algorithms       Searching       UGC NET CS 2016 Aug- paper-2
Question 19 Explanation: 
Possibility-1:
→ Traversing all the nodes of a binary search tree with n nodes and printing them in order using inorder traversal.
→ Inorder traversal will print all elements in sorted order. It takes worst case time complexity is O(n).
Possibility-2:
Without sorted elements chance to form either left skewed or right skewed tree. It takes worst case time complexity is O(n).
Question 20
The average case occurs in the linear search algorithm when:
A
The item to be searched is in somewhere 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
       Algorithms       Searching       UGC NET CS 2015 Jun- paper-2
Question 20 Explanation: 
→ A linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.
→ A linear search runs in at worst linear time and makes at most n comparisons, where ‘n’ is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each element vary. → Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.
Question 21

Which searching algorithm requires that all of the data must be in order?

A
Sequential search
B
Binary search
C
Linear search
D
All (1), (2), and (3)
       Algorithms       Searching       APPSC-2012-DL CA
Question 21 Explanation: 
Binary search algorithm requires that all of the data must be in order.
Question 22

Time complexity of Binary search is

A
O(n)
B
O(n2)
C
O(log n)
D
O(n log n)
       Algorithms       Searching       APPSC-2012-DL CA
Question 22 Explanation: 
Time complexity of binary search is O(logn).
Question 23
If the binary search algorithm determines that the search argument is in the lower half of the array, which of the following statements will set the appropriate variable to the appropriate value?
A
Start Sub = Middle Sub – 1 :
B
Start Sub = Middle Sub + 1 :
C
Stop Sub = Middle Sub – 1 :
D
Stop Sub = Middle Sub + 1 :
       Algorithms       Searching       TNPSC-2012-Polytechnic-CS
Question 23 Explanation: 
If binary search algorithm determines that the search argument is in the lower half of the array then
start sub = 0;
stop sub = Middle sub + 1;
Question 24
What is the best case running time of binary search?
A
θ(n)
B
θ(1)
C
θ(log n)
D
θ(n log log n)
       Algorithms       Searching       TNPSC-2017-Polytechnic-CS
Question 24 Explanation: 
Best case running time complexity of binary search is O(1) and worst case running time complexity of binary search is O(log n).
Question 25
Which of the following is the recurrence relation for binary search?
A
T(n) = T(n/2) + 1
B
T(n) = T(n/2) + n
C
T(n) = 2T(n - 1) + 1
D
T(n) = T(n - 1) + 1
       Algorithms       Searching       TNPSC-2017-Polytechnic-CS
Question 25 Explanation: 
A-applying masters theorem we get O(logn) which is the time complexity of binary search.
B- applying masters theorem we get O(n) which is not the time complexity for binary search.
C- Using back substitution we get O(2n) which is not the time complexity for binary search.
D-Using back substitution we get time complexity as O(n) which is not of binary search.
There are 25 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com
error: Content is protected !!