Uttar Pradesh Technical University (UPTU) 2006 B.Tech Computer Science Information Technology GATE - Question Paper
Wednesday, 27 March 2013 07:45Web
Page 9 of 14
Ii ifx[i1]=O
otherwise
Consider the subsequent algorithm in which x,y and z are Boolean arrays of size n:
algorithm zzz(x[ 1, y[ 1, z [
mt i;
for (i=O; i
}
The set Z calculated by the algorithm is:
(A) (XUY)
(B) (xflY)
(C) (X-Y)fl(Y-X)
(D) (x-Y)U(Y-x)
51. Consider the subsequent recurrence:
T(n)=2T(r*i1)+1,T(1) = 1
Which 1 of the subsequent is true?
(A) T(n) = e(loglogn)
(B) T(n) = e(logn)
(C) T(n)=8(sJ)
(D) T(n)rz8(n)
52. The median of n elements can be obtained in O(n)time. Which 1 of the subsequent is accurate
about the complexity of quick sort, in which median is opted as pivot?
(A) 8(n)
(B) e(nlogn)
(C) 8(n2)
(D) 8(n3)
53. Consider the subsequent C-function in which a[nl and b[mlare 2 sorted integer arrays and
c[n + mibe a different integer array.
void xyz(int a[], mt b [1, mt c []){
mt i,j,k;
i=j=k=O;
while ((i
else c[k++] =
Which of the subsequent condition(s) hold(s) after the termination of the while loop?
(i) j
(A) only (i)
(B) only (ii)
(C) either (i) or (ii) but not both
(D) neither (i) nor (ii)
54. provided 2 arrays of numbers a1,...,a and b1,...,b where every number is 0 or 1, the fastest
algorithm to obtain the largest span (i,j)such that
a, + a,1 + ... + a = b, + b,1 + ... + b, or report that there is not such span,
(A) Takes Q(3n) and c(2)time if hashing is permitted
(B) Takes 0(n3) and c(n25)time in the key comparison model
(C) Takes e(n)time and space
(D) Takes o(J) time only if the sum of the 2n elements is an even number
55. Consider these 2 functions and 2 statements Si and S2 about them.
mt workl(±nt *a, mt ±, mt j) mt work2(±nt *a, mt ±, mt j)
| Earning: Approval pending. |
