## Searching

Please wait while the activity loads.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

Question 1 |

**The time taken by binary search algorithm to search a key in a sorted array of n elements is**

O ( log _{2}n ) | |

O ( n ) | |

O ( n log _{2}n ) | |

O ( n _{2} ) |

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:

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 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**

O(log n) | |

O(n) | |

O(1) | |

(n ^{2}) |

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**

O(log n) | |

O(n) | |

O(1) | |

O(n ^{2}) |

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

n/2 | |

(n-1)/2 | |

(n+1)/2 | |

None of these |

Question 5 Explanation:

Total comparisons required

= No. of comparisons if element present in 1

= 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 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 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

L | |

L/2 | |

(L+1)/2 | |

2L |

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

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?

3.00 | |

3.46 | |

2.81 | |

3.33 |

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

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?

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 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.

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 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?

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 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.

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 10 |

The complexity of linear search algorithm is

O(nlogn) | |

O(n) | |

O(logn) | |

O(n*n) |

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)

→ 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

2 | |

10 | |

8 | |

5 |

Question 11 Explanation:

Step-1: Binary search we are using formula O(log

Sep-2: The maximum number of comparisons for a particular record among 32 sorted recorder through binary search method will be 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)=5Question 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 ?

3 | |

4 | |

5 | |

6 |

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

2*log _{2} n | |

log _{2} 2n | |

log _{2} (2n+1) | |

2*log _{2} n+1 |

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 = log

_{2}N. 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?

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 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:

O(lg n) | |

O(n lg n) | |

O(n) | |

O(n ^{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:

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 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.

→ 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.