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 _________.
5  
6  
7  
8 
→ 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(log_{2} 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 = n1; do { k = (i+j)/2; if (x <= listA[k]) j = k1; 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?
It will run into an infinite loop when x is not in listA.  
It is an implementation of binary search.  
It will always find the maximum element in listA.  
It will return −1 even when x is present in listA. 
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?
n  
n1  
2n  
n/2 
Question 4 
Which one of the following statements is false?
Optimal binary search tree construction can be performed efficiently using dynamic programming.  
Breadthfirst search cannot be used to find converted components of a graph.  
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.  
Depthfirst search can be used to find connected components of a graph. 
Question 5 
O ( log_{2}n )  
O ( n )  
O ( n log_{2}n )  
O ( n_{2} ) 
Question 6 
T(n)=2T(n/2)+k , where k is constant  
T(n)=T(n/2) +k, where k is constant  
T(n)=T(n/2)+logn  
T(n)=T(n/2)+n 
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 
O(log n)  
O(n)  
O(1)  
(n^{2}) 
Question 8 
O(log n)  
O(n)  
O(1)  
O(n^{2}) 
Question 9 
n/2  
(n1)/2  
(n+1)/2  
None of these 
= No. of comparisons if element present in 1^{st} position + No. of comparisons if element present in 2^{nd}nd position + ............. + No. of comparisons if element present in n^{th} 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 
L  
L/2  
(L+1)/2  
2L 
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 
3.00  
3.46  
2.81  
3.33 
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
Level3 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 level3 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 
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k;
}
while((Y[k]!=x) && (i
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?
Y is [1 2 3 4 5 6 7 8 9 10] and x<10  
Y is [1 3 5 7 9 11 13 15 17 19] and x<1  
Y is [ 2 2 2 2 2 2 2 2 2 2] and x>2  
Y is [ 2 4 6 8 10 12 14 16 18 20] and 2 
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k]
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 
f(int Y[10], int x)
{
int u,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k;
}while((Y[k]!=x) && (i
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?
Y is [1 2 3 4 5 6 7 8 9 10] and x<10  
Y is [1 3 5 7 9 11 13 15 17 19] and x<1  
Y is [ 2 2 2 2 2 2 2 2 2 2] and x>2  
Y is [ 2 4 6 8 10 12 14 16 18 20] and 2 
First iteration:
I=0,j=9
K=(0+9)/2=4
Elements with duplicate values of “2” the condition if(Y[k]
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 
O(nlogn)  
O(n)  
O(logn)  
O(n*n) 
→ So, it takes time complexity O(n)
Question 15 
2  
10  
8  
5 
Sep2: 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 
3  
4  
5  
6 
Height of the binary search tree = 3
Question 17 
2*log_{2} n  
log_{2} 2n  
log_{2} (2n+1)  
2*log_{2} n+1 
Question 18 
3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15  
20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9
 
20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3  
3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20 
Question 19 
O(lg n)  
O(n lg n)  
O(n)  
O(n ^{2} ) 
→ 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).
Possibility2:
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 item to be searched is in somewhere middle of the array  
The item to be searched is not in the array  
The item to be searched is in the last of the array  
The item to be searched is either in the last or not in the array 
→ 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?
Sequential search  
Binary search
 
Linear search  
All (1), (2), and (3)

Question 22 
Time complexity of Binary search is
O(n)
 
O(n^{2})  
O(log n)
 
O(n log n) 
Question 23 
Start Sub = Middle Sub – 1 :  
Start Sub = Middle Sub + 1 :  
Stop Sub = Middle Sub – 1 :  
Stop Sub = Middle Sub + 1 : 
start sub = 0;
stop sub = Middle sub + 1;
Question 24 
θ(n)  
θ(1)  
θ(log n)  
θ(n log log n) 
Question 25 
T(n) = T(n/2) + 1  
T(n) = T(n/2) + n  
T(n) = 2T(n  1) + 1  
T(n) = T(n  1) + 1 
B applying masters theorem we get O(n) which is not the time complexity for binary search.
C Using back substitution we get O(2^{n}) which is not the time complexity for binary search.
DUsing back substitution we get time complexity as O(n) which is not of binary search.