# GATE Computer Science and IT Solved Paper 2015 Session 1 - Part 4

31.       SELECT operation in SQL is equivalent to
(A) the selection operation in relational algebra
(B) the selection operation in relational algebra, except that SELECT in SQL retains duplicates
(C) the projection operation in relational algebra
(D) the projection operation in relational algebra, except that SELECT in SQL retains duplicates
32.       A file is organized so that the ordering of data records is the same as or closes to the ordering of data entries in some index. Then that index is called
(A) Dense         (B) Sparse
(C) Clustered    (D) Unclustered
33.       In the LU decomposition of the matrix
if the diagonal elements of U are both 1, then the lower diagonal entry l22 of L is ..............
34.       The output of the following C program is ....................
void f1(int a, int b) {
int c;
c=a; a=b; b=c;
}
void f2(int *a, int *b) {
int c;
c=*a; *a=*b; *b=c;
}
int main() {
int a=4, b=5, c=6;
f1(a,b);
f2(&b, &c);
printf(“%d”,c-a-b);
}
35.       What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
(A) θ(log n) for both insertion and deletion
(B) θ(n) for both insertion and deletion
(C) θ(n) for insertion and θ(log n) for deletion
(D) θ(log n) for insertion and θ(n) for deletion

36.       Suppose that the stop-and-wait protocol is used on a link with a bit rate of 64 kilobits per second and 20 milliseconds propagation delay. Assume that the transmission time for the acknowledgement and the processing time at nodes are negligible. Then the minimum frame size in bytes to achieve a link utilization of at least 50% is .................
37.       Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.
Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
(A) 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
(B) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(C) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(D) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30
38.       Consider the following C program segment.
while(first <= last)
{
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
found = TRUE;
else last = middle - 1;
middle = (first + last)/2;
}
if (first > last) notPresent = TRUE;
The cyclomatic complexity of the program segment is .....................
39.       Consider a LAN with four nodes S1, S2, S3 and S4. Time is divided into fixed-size slots, and a node can begin its transmission only at the beginning of a slot. A collision is said to have occurred if more than one node transmit in the same slot. The probabilities of generation of a frame in a time slot by S1, S2, S3 and S4 are 0.1, 0.2, 0.3 and 0.4, respectively. The probability of sending a frame in the first slot without any collision by any of these four stations is ...................