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

Number of Questions: 85 | |

Created by: Aliensbrain Bot | |

Tags: Computer Science GATE CS Previous Year Paper |

Attempted
0/85
Correct 0
Score 0

‹
›

What is the maximum number of different Boolean functions involving n Boolean variables?

Let G be the non-planar graph with the minimum possible number of edges. Then G has

Consider the DAG with V = {1, 2, 3, 4, 5, 6}, shown below.

Which of the following is NOT a topological ordering?

f (w, x, y, z) = $\sum$(1,3,4,6,9,11,12,14)

The function is:

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Which one of the following is a top-down parser?

P. f (x) is continuous for all real values of x

Q. f (x) is differentiable for all real values of x

Which of the following is TRUE?

Which of the following sorting algorithms has the lowest worst-case complexity?

In Ethernet when Manchester encoding is used, the bit rate is:

How many different non-isomorphic Abelian groups of order 4 are there?

Permutations of 1, 2, 3,….., 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?

Consider the set of (column) vectors defined by

$$X = \left \{x \in R^3 \mid x_1 + x_2 + x_3 = 0, \text{ where } x^T = \left[x_1,x_2,x_3\right]^T\right \}$$.

Which of the following is TRUE?

The control signal functions of a 4-bit binary counter are given below (where X is “don't care”):

Clear Clock Load Count Function

The counter is connected as follows:

Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:

Which of the following graphs has an Eulerian circuit?

Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match the entries in Group 1 to the entries in Group 2.

**Group I
**

Define the connective * for the Boolean variables X and Y as: X * Y = XY + X'Y'. Let Z = X *Y. Consider the following expressions P, Q and R.

$\pi P$ : X = Y * Z Q : Y = X * Z R : X *Y * Z = 1

Which of the following is TRUE?

Which one of the following uses UDP as the transport protocol?

Let f (w, x, y, z) = ^{$\sum$}(0,4,5,7,8,9,13,15). Which of the following expressions is/are NOT equivalent to f?

P. x’y’z’ + w’xy’ + wy’z + xz

Q. w’y’z’ + wx’y’ + xz

R. w’y’z’ + wx’y’ + xyz + xy’z

S. x’y’z’ + wx’y’ + w’y

d b e a f c g and a b d e c f g, respectively

The post order traversal of the binary tree is:

_{i} for

inputs A_{i} and B_{i} are given by:

P_{i} = A_{i} $\oplus$ B_{i} and G_{i} = A_{i} B_{i}

The expressions for the sum bit S_{i} and the carry bit C_{i+1} of the look-ahead carry adder are given by:

S_{i} = P_{i} C_{i} and C_{i+1} = G_{i} + P_{i }C_{i}, where C_{o} is the input carry.

Consider a two-level logic implementation of the look-ahead carry generator.

Assume that all P_{i} and G_{i} are available for the carry generator circuit and that the AND and OR gates

can have any number of inputs. The number of AND gates and OR gates needed to implement the

look-ahead carry generator for a 4-bit adder with 3 2 1 0 4 S ,S ,S ,S and C as its outputs are

respectively:

Which of the following is TRUE about formulae in Conjunctive Normal Form?

Int Do Something (int n) {

return 1;

else

return (Do Something (floor sqrt (n))) + n);

In the following C function, let n ^{$\ge$ }m.

Int gcd (n,m)

{

if (n% m ==0) return m;

n = n %m;

return gcd (m, n);

}

How many recursive calls are made by this function?

P: Every regular grammar is LL(1)

Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

Consider the grammar with non-terminals N = { S, C, S_{1}), terminals T = {a, b, i, t, e}, with S as the start symbol, and the following set of rules:

S $\rightarrow$iCtSS_{1} | a

S_{1} $\rightarrow$ eS |$\in$

C $\rightarrow$ b

The grammar is NOT LL(1) because:

number of frames to a process. Consider the following statements:

P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.

Q: Some programs do not exhibit locality of reference.

Which one of the following is TRUE?

int Is Prime (n)

{

int i, n;

for (i = 2; i <= sqrt (n) ; i ++)

if (n% i == 0) { print f (“ Not Prime n”); return 0; }

return 1;

}

Let T (n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:

Here, wants1 and wants2 are shared variables, which are initialized to false.

Which one of the following statements is TRUE about the above construct?

^{3} + 1 to protect it from errors. The message that should be transmitted is:

An operating system uses shortest remaining time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes:

Process Execution time Arrival time P1 20 0 P2 25 15 P3 10 30 P4 15 45

What is the total waiting time for process P2?

OP R_{j} , R_{i} - Performs R_{j} OP R_{i} and stores the result in register . R_{i}

OP m, R_{i} - Performs val i OP R_{i} and stores the result in R_{i}. val denotes the content of memory location m.

MOV m, R_{i} - Moves the content of memory location m to register R_{i}

MOV R_{i}^{ }, m - Moves the content of register R_{i} to memory location m.

The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:

t_{1} = a + b

t_{2} = c + d

t_{3} = e - t_{2}

t_{4} = t_{1} - b

Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

^{7} bps and the propagation speed is 200 metres/$\mu$s. The 1-bit delay in this network is equivalent to:

Suppose the letters a, b, c, d, e, f have probabilities $ \dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{8},\dfrac{1}{16},\dfrac{1}{32},\dfrac{1}{32}$ respectively.

Which of the following is the Huffman code for the letter a, b, c, d, e, f?

Match the following:

(P) | SMTP | (1) | Application layer |

(Q) | BGP | (2) | Transport layer |

(R) | TCP | (3) | Data link layer |

(S) | PPP | (4) | Network layer |

(5) | Physical layer |

Suppose the letters a, b, c, d, e, f have probabilities $ \dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{8},\dfrac{1}{16},\dfrac{1}{32},\dfrac{1}{32}$ respectively.

What is the average length of the correct answer to Q.?

A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): **1, 2, 1, 3, 7, 4, 5, 6, 3, 1**

If optimal page replacement policy is used, how many page faults occur for the above reference string?

A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): **1, 2, 1, 3, 7, 4, 5, 6, 3, 1**

Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?

Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules:

S$ \rightarrow$ a B S $ \rightarrow$bA

B $ \rightarrow$b A$ \rightarrow$ a

B $ \rightarrow$bS A $ \rightarrow$aS

B $ \rightarrow$aBB S$ \rightarrow$ bAA

Which of the following strings is generated by the grammar?

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i, j) then it can move to either (i + 1, j) or (i, j + 1).

Suppose that the robot is not allowed to traverse the line segment from (4, 4) to (5, 4). With this

constraint, how many distinct paths are there for the robot to reach (10, 10) starting from (0, 0)?

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i, j) then it can move to either (i + 1, j) or (i, j + 1).

How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?

Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules:

S ^{$\rightarrow$} aB S ^{$\rightarrow$ }bA

B ^{$\rightarrow$ }b A ^{$\rightarrow$} a

B ^{$\rightarrow$ }bS A ^{$\rightarrow$ }aS

B ^{$\rightarrow$ }aBB S ^{$\rightarrow$} bAA

How many derivation trees are there?

Consider a machine with a byte addressable main memory of 2^{16} bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.

Which of the following lines of the data cache will be replaced by new blocks in accessing the array for the second time?

IF: Instruction Fetch

ID: Instruction Decode and Operand Fetch

EX: Execute

WB: Write Back

The IF, ID and WB stages take one clock cycle each to complete the operation.

The number of clock cycles for the EX stage depends on the instruction. The ADD and SUB instructions

need 1 clock cycle and the MUL instruction needs 3 clock cycles in the EX stage. Operand forwarding

is used in the pipelined processor.

What is the number of clock cycles taken to complete the following sequence of instructions?

ADD R2, R1, R0 R2 $\rightarrow$ R1 + R0

MUL R4, R3, R2 R4$\rightarrow$ R3 * R2

SUB R6, R5, R4 R6 $\rightarrow$R5 - R4

Consider a machine with a byte addressable main memory of 2^{16} bytes. Assume that a direct mapped data cache consisting of 32 lines of 64 bytes each is used in the system. A 50 × 50 two-dimensional array of bytes is stored in the main memory starting from memory location 1100H. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.

How many data cache misses will occur in total?

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.

Instruction |
Operation |
Instruction size (no. of words) |

MOV R1, (3000) | R1 _ m[3000] | 2 |

LOOP: MOV R2, (R3) | R2 _ M[R3] | 1 |

ADD R2, R1 | R2 _ R1 + R2 | 1 |

MOV (R3), R2 | M[R3] _ R2 | 1 |

INC R3 | R3 _ R3 + 1 | 1 |

DEC R1 | R1 _ R1 - 1 | 1 |

BNZ LOOP | Branch on not zero | 2 |

HALT | Stop | 1 |

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.

Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is:

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.

Instruction |
Operation |
Instruction size (no. of words) |

MOV R1, (3000) | R1 _ m[3000] | 2 |

LOOP: MOV R2, (R3) | R2 _ M[R3] | 1 |

ADD R2, R1 | R2 _ R1 + R2 | 1 |

MOV (R3), R2 | M[R3] _ R2 | 1 |

INC R3 | R3 _ R3 + 1 | 1 |

DEC R1 | R1 _ R1 - 1 | 1 |

BNZ LOOP | Branch on not zero | 2 |

HALT | Stop | 1 |

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.

Assume that the memory is word addressable. After the execution of this program, the content of memory location 2010 is:

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers.

Instruction |
Operation |
Instruction size (no. of words) |

MOV R1, (3000) | R1 _ m[3000] | 2 |

LOOP: MOV R2, (R3) | R2 _ M[R3] | 1 |

ADD R2, R1 | R2 _ R1 + R2 | 1 |

MOV (R3), R2 | M[R3] _ R2 | 1 |

INC R3 | R3 _ R3 + 1 | 1 |

DEC R1 | R1 _ R1 - 1 | 1 |

BNZ LOOP | Branch on not zero | 2 |

HALT | Stop | 1 |

Assume that the content of memory location 3000 is 10 and the content of the register R3 is 2000. The content of each of the memory locations from 2000 to 2010 is 100. The program is loaded from the memory location 1000. All the numbers are in decimal.

Assume that the memory is byte addressable and the word size is 32 bits. If an interrupt occurs during the execution of the instruction “INC R3”, what return address will be pushed on to the stack?

Consider the following C function:

```
int f(int n) {
static int r = 0;
if (n <= 0) return 1;
if (n > 3) {
r = n;
return f(n - 2) + 2;
}
return f(n - 1) + r;
}
```

What is the value of f (5)?

The following postfix expression with single digit operands is evaluated using a stack:

8 2 3 $\land$/ 2 3 * + 5 1 * -

Note that $\land$ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

Consider the following segment of C-code:

```
int j, n;
j = 1;
while (j <= n)
j = j*2
```

The number of comparisons made in the execution of the loop for any n > 0 is:

Consider the following C program segment where CellNode represents a node in a binary tree:

```
Struct Cell Node {
Struct Cell Node * left child;
Int element;
Struct Cell Node * right Child;
};
Int Get Value(struct Cell Node * ptr) {
Int Value = 0;
if (ptr! = NULL)
if ((ptr - > left child == NULL) &&
(ptr - > right Child == NULL))
Value = 1;
else
Value = value + GetValue(ptr - > left Child) + Get Value(ptr - > right child);
}
return (value);
}
```

The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:

Information about a collection of students is given by the relation studinfo (studId, name, sex). The relation enroll (studId, courseId) gives which student has enrolled for (or taken) what course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent?

$\pi_{courceId}\left(\left(\pi_{\text{studId}}\left(\sigma_{sex="female"}\left(\text{studInfo}\right)\right) \times \pi_{courseId}\left(\text{enroll}\right)\right) -\text{enroll}\right)$

Consider the table employee (empId, name, department, salary) and the two queries Q_{1}, Q_{2} below.

Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary in department 5, which one of the statements is TRUE for any arbitrary employee table?

```
$Q_1$ : Select e. empId
From employee
Where not exists
(Select * From employee s where s. department = “5” and s. salary >= e. salary)
$Q_2$ : Select e. empId
From employee e
Where e. salary > any
(select distinct salary From employee s where s. Where s. department = “5”)
```

Consider the following schedules involving two transactions. Which one of the following statements is TRUE?

S_{1} : r_{1} (X); r_{1} (Y); r_{2} (X); r_{2} (Y); w_{2} (Y); W_{1} (X)

S_{2} : r_{1} (X); r_{2} (Y); r_{2} (X); w_{2} (Y); r_{1} (Y); W_{1} (X)

{

e. name| employee (e) ^{$\land$}

^{$\forall X$}[^{$\neg$}employee (x) ^{$\lor$ }x.supervisorName ^{$\ne$}e.name ^{$\lor$} x.sex = “male”]

}

Which one of the following statements is FALSE?

^{+} - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?

Which of the following problems is undecidable?

Which of the following is TRUE?

Consider the following Finite State Automaton:

The language accepted by this automaton is given by the regular expression

The language {0^{i} 21^{i} | i $\ge$0} over the alphabet {0, 1, 2} is:

Consider the following Finite State Automaton:

The minimum state automaton equivalent to the above FSA has the following number of states

Which of the following languages is regular?