Description: GATE Exam Previous Year Question Paper Solution Computer Science(CS) - 2006 | |

Number of Questions: 85 | |

Created by: Aliensbrain Bot | |

Tags: Computer Science GATE CS Previous Year Paper |

Attempted
0/85
Correct 0
Score 0

‹
›

(x,y) R (u,v) if x < u and y > v. Then R is:

In a binary max heap containing n numbers, the smallest element can be found in time

Which one of the following in place sorting algorithms needs the minimum number of swaps?

_{1}, v_{2},............., v_{n}} such that the weight of the edge (v_{i}, v_{j}) is 2 |i - j| . The weight of a minimum spanning tree of G is:

Consider the following grammar

S→ S * E

S→ E

E→ F + E

E→ F

F→ id

Consider the following LR(0) items corresponding to the grammar above

S → S *.E

E → F. + E

E → F + .E

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

_{1} ..............x_{n} } where x_{i} = 2^{i }A sample S $\subseteq $ X is drawn by selecting each x_{i} independently with probability p_{i} = 1/2. The expected value of the smallest number in sample S is:

Let $E, F$ and $G$ be finite sets. Let

$X = (E ∩ F) - (F ∩ G)$ and

$Y = (E - (E ∩ G)) - (E - F)$.

Which one of the following is true?

`for( i = n, j = 0; i > 0; i /= 2, j +=i );`

Let val ( j ) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

Consider the following propositional statements:

P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))

P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))

Which one of the following is true?

Consider the circuit above. Which one of the following options correctly represents f (x, y, z)?

Tigers and lions attack if they are hungry or threatened.

A logical binary relation $\odot$, is defined as follows:

$A$ | $B$ | $A\odot B$ |
---|---|---|

True | True | True |

True | False | True |

False | True | False |

False | False | True |

Let $\sim$ be the unary negation (NOT) operator, with higher precedence then $\odot$.

Which one of the following is equivalent to $A\wedge B$ ?

Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T.

The degrees of both u and n in G are at least 2. Which one of the following statements is true?

_{3} h_{2} h_{1} h_{0} be the gray code representation of a number n and let g_{3} g_{2} g_{1} g_{0} be the gray code of (n + 1) (modulo 16) value of the number. Which one of the following functions is correct?

_{2} a_{1} a_{0} and b_{2} b_{1} b_{0} and c, the carry in, the function that represents the carry generate function when these two numbers are added is:

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?

A set X can be represented by an array x [n] as follows:

x$\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & otherwise \end{cases}$

Consider the following algorithm in which x, y and z are boolean arrays of size n.

algorithm zzz (x [ ], y[ ], z [ ] ) {

int i;

for (i = 0 ; i< n; ++i)

z[i] = (x[i] Ù ~y[i]) Ú (~x[i] Ù y[i])

}

The set Z computed by the algorithm is

The order of the following recurrence:

$T(n) = 2T([\sqrt{n}]) + 1$

is

Consider the following code written in a pass-by-reference language like FORTRAN and these statements about the code.

S1: The compiler will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the cell swap

S2: On execution the code will generate a runtime error on line L1

S3: On execution the code will generate a runtime error on line L2

S4: The program will print 13 and 8

S5: The program will print 13 and - 2

Exactly the following set of statement(s) is correct:

for (i - 0, i<n; i++) {

for (j=0; j<n; j++) {

if (i%2) {

x += (4* j + 5* i);

y += (7 + 4*j);

}

}

}

Which one of the following is false?

_{1},..........., a_{n} and b_{1},............, b_{n} where each number is 0 or 1, the fastest algorithm to find the largest span (i, j ) such that

a_{i} + a_{i+1} + .........+ a_{j} = b_{i} + b_{i + 1} +...........+ b_{j} or report that there is not such span,

S$\rightarrow$ER

R$\rightarrow$*E {print ('*'); R}$\in$

E $\rightarrow$F + E {print ('+');} F

F$\rightarrow$ (S) | id {print (id.value);}

Here id is a token that represents an integer and id.value represents the corresponding integer value.

For an input '2 * 3 + 4', this translation scheme prints

Consider the circuit in the diagram. The $\oplus$ operator represents Ex - OR. The D flip - flops are initialized to zeroes (cleared).

The following data: 100110000 is supplied to the “data” terminal in nine clock cycles. After that the values of q_{2} q_{1} q_{0} are:

S $\rightarrow$FR

R$\rightarrow$* S|$\in$

F$\rightarrow$id

In the predictive parser table, M, of the grammar the entries

M [S, id] and M [R,$] respectively.

void P (binary_semaphore *s) {

unsigned y;

unsigned *x = &(s->value);

do {

fetch-and-set x, y;

} while (y);

}

void V (binary_semaphore *s) {

S ->value = 0;

}

Which one of the following is true?

(

Which one of the following is true?

The 2^{n }vertices of a graph G corresponds to all subsets of a set of size n, for n $\ge$ 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of vertices of degree zero in G is:

The 2^{n }vertices of a graph G corresponds to all subsets of a set of size n, for n $\ge$ 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of connected components in G is:

_{i} instances of a resource R, 1$\le$ i$\le$ n. currently, all instances of R are occupied. Further, for all i, process i has placed a request for an additional y_{i} instances while holding the x_{i} instances it already has. There are exactly two processes p and q such that 0. y_{p} = y_{q} = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void) {

1: P(S);

2: process_arrived++;

- V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

Which one of the following rectifies the problem in the implementation?

The 2^{n }vertices of a graph G corresponds to all subsets of a set of size n, for n $ge$ 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The maximum degree of a vertex in G is:

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void) {

1: P(S);

2: process_arrived++;

- V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

The above implementation of barrier is incorrect. Which one of the following is true?

^{l} b^{m} with l ^{$\ne$} m?

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge. Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred.

Consider the correct spanning tree for the previous question. Let host H1 send out a broadcast ping packet. Which of the following options represents the correct forwarding table on B3?

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge. Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred.

For the given connection of LANs by bridges, which one of the following choices represents the depth first traversal of the spanning tree of bridges?

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h_{1} while that of the direct mapped one is h_{2}.

The value of h_{1} is:

temp$\leftarrow$reg & mask

Branch to label if temp is non-zero.

The variable temp is a temporary register. For correct emulation, the variable mask must be generated by

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h_{1} while that of the direct mapped one is h_{2}.

The value of h_{2} is:

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two dimensional

array of size 512×512 with elements that occupy 8-bytes each. Consider the

following two C code segments, P1 and P2.

P1: for (i=0; i<512; i++) {

for (j=0; j<512; j++) {

x +=A[i] [j];

}

}

P2: for (i=0; i<512; i++) {

for (j=0; j<512; j++) {

x +=A[j] [i];

}

}

P1 and P2 are executed independently with the same initial state, namely, the array A is

not in the cache and i, j, x are in registers. Let the number of cache misses experienced

by P1 be M_{1} and that for P2 be M_{2} .

The value of the ratio $\dfrac{M_1}{M_2}$

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two dimensional

array of size 512×512 with elements that occupy 8-bytes each. Consider the

following two C code segments, P1 and P2.

P1: for (i=0; i<512; i++) {

for (j=0; j<512; j++) {

x +=A[i] [j];

}

}

P2: for (i=0; i<512; i++) {

for (j=0; j<512; j++) {

x +=A[j] [i];

}

}

P1 and P2 are executed independently with the same initial state, namely, the array A is

not in the cache and i, j, x are in registers. Let the number of cache misses experienced

by P1 be M_{1} and that for P2 be M_{2} .

The value of 1 M is:

Consider these two functions and two statements S1 and S2 about them.

S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1

Consider the following C-function in which a [n] and b [m] are two sorted integer

arrays and c [n + m ] be another integer array.

```
void xyz (int a[ ], int b [ ], int c [ ]) {
int i, j, k;
i=j=k=0;
while ((i < n) && (j < m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
```

Which of the following condition(s) hold(s) after the termination of the while loop?

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4]location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

Consider this C code to swap two integers and these five statements: the code.

S1: will generate a compilation error

S2: may generate a segmentation fault at runtime depending on the arguments passed

S3: correctly implements the swap procedure for all input pointers referring to integers stored in

memory locations accessible to the process

S4: implements the swap procedure correctly for some but not all valid input pointers

S5: may add or subtract integers and pointers.

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4]location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?

void insert (Q, x) {

push (S1, x);

}

void delete (Q) {

if (stack-empty(S2)) then

if (stack-empty(S1)) then {

print(“Q is empty”);

return;

}

else while (!(stack-empty(S1))){

x=pop (S1);

push (S2,x);

}

x=pop (S2);

}

Let n insert* *and m ($\le$ n) delete operations be performed in an arbitrary order on an empty queue Q. Let

x and y be the number of *push *and pop operations performed respectively in the process. Which one of

the following is true for all m and n?

Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. Ties are not broken but ranks are skipped: if exactly two customers have the largest balance they each get rank 1 and rank 2 is not assigned.

Consider these statements about Query 1 and Query 2.

- Query 1 will produce the same row set as Query 2 for some but not all databases.
- Both Query 1 and Query 2 are correct implementation of the specification.
- Query 1 is a correct implementation of the specification but Query 2 is not.
- Neither Query 1 nor Query 2 is a correct implementation of the specification.
- Assigning rank with a pure relational query takes less time than scanning in decreasing balance order assigning ranks using ODBC.

Which two of the above statements are correct?

Consider the following log sequence of two transactions on a bank account, with initial balance of Rs. 12,000, that transfers 2000 to a mortgage payment and then applies a 5% interest.

- T1 start
- T1 B old = 1200 new = 10000
- T1 M old = 0 new = 2000
- T1 commit
- T2 start
- T2 B old = 10000 new = 10500
- T2 commit

Suppose the database system crashes just before log record 7 is written. When the system is restarted, which statement is true for the recovery procedure?

AB^{$\rightarrow$}CD, AF ^{$\rightarrow$} D,DE ^{$\rightarrow$}F,C ^{$\rightarrow$}G, F ^{$\rightarrow$}E,G ^{$\rightarrow$}A.

Which one of the following options is false?

Assume no null values and no foreign keys or integrity constraints. Given the following four queries:

Query1:select student from enrolled where student in (select student from paid)

Query2:select student from paid where student in (select student from enrolled)

Query3:select E.student from enrolled E, paid P where E.student = P.student

Query4:select student from paid where exists (select * from enrolled where enrolled. student = paid. student)

Which one of the above statements is correct?

Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000 were each paid by 20% of the students. Consider these query plans (Plan 1 on left, Plan 2 on right) to “list all courses taken by students who have paid more than x”

A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if amount is greater than x takes 10Zs. Which of the following statements is correct?

_{,} be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with V divisible by 3 and DHAM' be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

_{1} = {0^{n+m}1^{n}0^{m}|n, m$\ge$0}. L_{2} = {0^{n+m}1^{n+m}0^{m}|n, m$\ge$0} and L_{3} = {0^{n+m}1^{n+m}0^{n+m}|n, m$\ge$0} Which of these languages are NOT context free?

Let L = {s $\in$ (0 + 1)* d (s)mod 5 = 2 and d (s) mod 7 $\ne$ 4}

Which one of the following statements is true?

_{0} (s) denote the number of 0's in s and n_{1} (s) the number of 1's in s. Which one of the following languages is not regular?

_{1} be a regular language, L_{2} be a deterministic context-free language and L_{3} a recursively enumerable, but not recursive, language. Which one of the following statements is false?

G = {S $\rightarrow$ SS, S $\rightarrow$ ab, S $\rightarrow$ ba, S $\rightarrow$$\in$}

I. G is ambiguous

II. G produces all strings with equal number of a's and b's

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?