Question 1 |

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

\Theta (\sqrt{n}) | |

\Theta ( \log _2 (n)) | |

\Theta ( n^2) | |

\Theta ( n) |

Question 1 Explanation:

Question 2 |

Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?

t \gt 2n-2
| |

t \gt 3\lceil \frac{n}{2}\rceil \text{ and } t\leq 2n-2 | |

t \gt n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil | |

t \gt \lceil \log_2(n)\rceil \text{ and } t\leq n |

Question 2 Explanation:

Question 3 |

If an array A contains the items 10, 4, 7, 23, 67, 12 and 5 in that order, what will be the resultant array A after third pass of insertion sort?

67,12,10,5,4,7,23 | |

4,7,10,23,67,12,5 | |

4,5,7,67,10,12,23 | |

10,7,4,67,23,12,5 |

Question 3 Explanation:

Question 4 |

Consider a 2-dimensional array x with 10 rows and 4 columns, with each element storing a value equivalent to the product of row number and column number. The array is stored in row-major format. If the first element x[0][0] occupies the memory location with address 1000 and each element occupies only one memory location, which all locations (in decimal) will be holding a value of 10?

1018,1019 | |

1022,1041 | |

1017,1036 | |

1000,1399 |

Question 4 Explanation:

Originally all Options are wrong. We have modified one option.

Click here for detail solution by gateoverflow

Click here for detail solution by gateoverflow

Question 5 |

An array A consists of n integers in locations A[0],A[1],...A[n-1]. It is required to shift the elements of the array cyclically to the left by k places, where 1 \leq k \leq (n-1). An incomplete algorithm for doing this in linear time, without using another array is given bellow. Complete the algorithm by filling in the blanks.

```
min=n; i=0;
while(_________) {
temp= A[i]; j=i;
while(_________) {
A[j]= _______;
j=(j+k) mod n;
if(j < min) then
min = j;
}
A[(n+i-k) mod n]=_______;
i=________;
}
```

i \gt \min ; \quad j !=(n+1) \bmod n ; \quad A[j+k] \quad \text { temp; } \quad i+1 ; | |

i \lt \min ; \quad j !=(n+i) \bmod n ; \quad A[j+k] \quad \text { temp; } \quad i+1 ; | |

i \gt \min ; \quad j !=(n+i+k) \bmod n ; \quad A[j+k] \quad \text { temp; } \quad i+1 ; | |

i \lt \min ; \quad j !=(n+i-k) \bmod n ; \quad A[(j+k) \bmod n] \quad \text { temp; } \quad i+1 ; |

Question 5 Explanation:

There are 5 questions to complete.

Is there any available vedio for soln