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:

Question 6 |

Let A be an array of 31 numbers consisting of sequence of 0's followed by a sequence of 1's.
The problem is to find the smallest index i that A[i] is 1 by probing the minimum numbers of
locations in A. The worst case number of probes performed by an optimal algorithm is
_____________.

31 | |

15 | |

5 | |

1 |

Question 6 Explanation:

Question 7 |

The average number of key comparisons required for a successful search for sequential search on n items is

\frac{n}{2} | |

\frac{n-1}{2} | |

\frac{n+1}{2} | |

None of the above |

Question 7 Explanation:

Question 8 |

Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and nxn respectively, where 2\leq n\leq 10. Assume that in both code segments, elements of Y are initialized to 0 and each element X[i][j] of array X is initialized to i+j. Further assume that when stored in main memory all elements of X are in same main memory page frame.

Code segment 1:

S1: Final contents of array Y will be same in both code segments

S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory

S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory

Code segment 1:

```
//initialize elements of Y to 0
//initialize elements X[i][j] of X to i+j
for(i = 0; i < n; i++)
Y[i] += X[0][i];
```

Code Segment 2: ```
//initialize elements of Y to 0
//initialize elements X[i][j] of X to i+j
for(i = 0; i < n; i++)
Y[i] += X[i][0];
```

Which of the following statements is/are correct? S1: Final contents of array Y will be same in both code segments

S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory

S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory

Only S2 is correct | |

Only S3 is correct | |

Only S1 and S2 are correct | |

Only S1 and S3 are correct |

Question 8 Explanation:

Question 9 |

A frame buffer array is addressed in row major order for a monitor with pixel locations starting from (0,0) and ending with (100,100). What is address of the pixel(6,10)? Assume one bit storage per pixel and starting pixel location is at 0.

1016 | |

1006 | |

610 | |

616 |

Question 9 Explanation:

Question 10 |

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

There are 10 questions to complete.

Is there any available vedio for soln