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 |
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
→ 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?
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. |
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.
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 | |
n-1 | |
2n | |
n/2 |
Question 3 Explanation:
Question 4 |
Which one of the following statements is false?
Optimal binary search tree construction can be performed efficiently using dynamic programming. | |
Breadth-first 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. | |
Depth-first search can be used to find connected components of a graph. |
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
O ( log2n ) | |
O ( n ) | |
O ( n log2n ) | |
O ( n2 ) |
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:
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 |
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
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
O(log n) | |
O(n) | |
O(1) | |
(n2) |
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
O(log n) | |
O(n) | |
O(1) | |
O(n2) |
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
n/2 | |
(n-1)/2 | |
(n+1)/2 | |
None of these |
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
= 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
L | |
L/2 | |
(L+1)/2 | |
2L |
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
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?
3.00 | |
3.46 | |
2.81 | |
3.33 |
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
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?
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 |
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.
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 |
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?
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 |
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.
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 |
The complexity of linear search algorithm is
O(nlogn) | |
O(n) | |
O(logn) | |
O(n*n) |
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)
→ 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
2 | |
10 | |
8 | |
5 |
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
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 ?
3 | |
4 | |
5 | |
6 |
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
2*log2 n | |
log2 2n | |
log2 (2n+1) | |
2*log2 n+1 |
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?
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 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:
O(lg n) | |
O(n lg n) | |
O(n) | |
O(n 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).
→ 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:
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 |
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.
→ 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 21 Explanation:
Binary search algorithm requires that all of the data must be in order.
Question 22 |
Time complexity of Binary search is
O(n)
| |
O(n2) | |
O(log n)
| |
O(n log n) |
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?
Start Sub = Middle Sub – 1 : | |
Start Sub = Middle Sub + 1 : | |
Stop Sub = Middle Sub – 1 : | |
Stop Sub = Middle Sub + 1 : |
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;
start sub = 0;
stop sub = Middle sub + 1;
Question 24 |
What is the best case running time of binary search?
θ(n) | |
θ(1) | |
θ(log n) | |
θ(n log log n) |
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?
T(n) = T(n/2) + 1 | |
T(n) = T(n/2) + n | |
T(n) = 2T(n - 1) + 1 | |
T(n) = T(n - 1) + 1 |
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.
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.