Searching

Question 1
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 1 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 2
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 2 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 3
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 3 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 4
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 4 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 5
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 5 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 6
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 6 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 7
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 7 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 8
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 8 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 9
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 9 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 10
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 10 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 11
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 11 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 12
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 12 Explanation: 

Height of the binary search tree = 3
Question 13
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 13 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 14
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 14 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 15
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 15 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 16
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 16 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.
There are 16 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com