GATE CSE 2003
View Questions

GATE CSE

1
Consider the following three claims
I. (n + k)m = $$\Theta \,({n^m})$$ where k and m are constants
II. 2n+1 = O(2n)
III. 22n = O(22n)
Which of those claims are correct?
2
Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is
3
In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
4
What is the weight of a minimum spanning tree of the following graph? GATE CSE 2003 Algorithms - Greedy Method Question 14 English
5
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
6
Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ……., vj) such that (vk, vk+1) ∈ E for all k in i through j – 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow
$$$A[j,k] = \left\{ {\matrix{ {1\,if\,(j,\,k)} \cr {1\,otherwise} \cr } } \right.$$$ Consider the following algorithm.
for i = 1 to n
   for j = 1 to n
      for k = 1 to n
         A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); 
Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?
7
Let G=(V,E) be an undirected graph with a subgraph G1=(V1,E1). Weights are assigned to edges of G as follows. $$$w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, otherwise} \end{cases}$$$ A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex v1 of V1 as the source. Which of the following can always be inferred from the path costs computed?
8
The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will
9
The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity of computing the cube root of n (n is represented in binary notation) is
10

Consider the grammar shown below

$$\eqalign{ & S \to iEtSS'\,|\,\,a \cr & S' \to eS\,|\,\,\varepsilon \cr & E \to b \cr} $$

In the predictive parse table, $$M$$, of this grammar, the entries $$M\left[ {S',e} \right]$$ and $$M\left[ {S',\phi } \right]$$ respectively are

11
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
12
In a bottom-up evaluation of a syntax directed definition, inherited attributes can
13
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is
14

Consider the translation scheme shown below

$$\eqalign{ & S \to TR \cr & R \to + T\left\{ {pr{\mathop{\rm int}} (' + ');} \right\}\,R\,|\,\varepsilon \cr & T \to num\,\left\{ {pr{\mathop{\rm int}} (num.val);} \right\} \cr} $$

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will print

15

Consider the syntax directed definition shown below.

GATE CSE 2003 Compiler Design - Code Generation and Optimization Question 15 English

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X : = Y + Z', the 3-address code sequence generated by this definition is

16
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?
17
Which of the following statements is FALSE?
18

Consider the grammar shown below.

$$\eqalign{ & S \to CC \cr & C \to cC\,|\,d \cr} $$

This grammar is

19
Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?
20
The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to this network?
21
Which of the following assertions is FALSE about the Internet Protocol (IP)?
22
Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50 $$\mu $$s Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 $$\mu $$s. What is the maximum achievable throughput in this communication?
23
A 2 km long broadcast LAN has 107 bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2 × 108 m/s. What is the minimum packet size that can be used on this network?
24
For a pipelined $$CPU$$ with a single $$ALU$$, consider the following situations
$$1.\,\,\,\,\,$$ The $$j+1$$ instruction uses the result of the $$j$$-$$th$$ instruction as an operand
$$2.\,\,\,\,\,$$ The execution of a conditional jump instruction
$$3.\,\,\,\,\,$$ The $$j$$-$$th$$ and $$j+1$$ instruction require the $$ALU$$ at the same time

Which of the above can cause a hazard?

25
The following is a scheme for floating point number representation using $$16$$ bits. GATE CSE 2003 Computer Organization - Computer Arithmetic Question 8 English

Let $$s, e,$$ and $$m$$ be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is

$$\left\{ {\matrix{ {{{\left( { - 1} \right)}^s}\left( {1 + m \times {2^{ - 9}}} \right){2^{e - 31}},} & {if\,the\,{\mathop{\rm exponent}\nolimits} \, \ne \,111111} \cr {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,0} & {otherwise\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,} \cr } } \right.$$

What is the maximum difference between two successive real numbers representable in this system?

26
Consider the following graph among the following sequences
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e
GATE CSE 2003 Data Structures - Graphs Question 26 English What are depth first traversals of the above graph?
27
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
28
Consider the function f defined below.
struct item { 
      int data; 
      struct item * next; 
}; 

int f(struct item *p) { 
      return ((p == NULL) || (p ->next == NULL) || 
        ((p->data <= p -> next -> data) && 
        f(p-> next))); 
}
For a given linked list p, the function f returns 1 if and only if
29
Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is
30
Consider three data items D1, D2, and D3, and the following execution schedule of transactions T1, T2, and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D respectively. GATE CSE 2003 Database Management System - Transactions and Concurrency Question 28 English

Which of the following statements is correct?

31
Which of the following scenarios may lead to an irrecoverable error in a database system?
32
Consider the following SQL query:
Select distinct a1, a2, ..., an 

From r1, r2, ..., rm 

Where P; 
For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions?
33
Consider the set of relations shown below and the SQL query that follows.

Students: (Roll_number, Name, Date_of_birth)
Courses: (Course number, Course_name, Instructor)
Grades: (Roll_number, Course_number, Grade)

Select distinct Name
From Students, Courses, Grades
Where Students.Roll_number = Grades.Roll_number
      and Courses.Instructor = 'Korth'
      and Courses.Course_number = Grades.Course_number
      and Grades.grade = 'A';
Which of the following sets is computed by the above query?
34
Consider the following functional dependencies in a database.
$$\eqalign{ & \,\,\,\,Date\,\,of\,\,Birth\,\, \to \,\,Age \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Age\,\, \to \,\,Eligibility \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Name\,\, \to \,\,Roll\_number \cr & \,\,\,\,\,Roll\_number\,\, \to \,\,Name \cr & Course\_number\, \to \,\,Course\_name \cr & Course\_number\, \to Instructor \cr & (Roll\_Number,\,Course\_number)\,\, \to \,\,Grade \cr} $$

The relation (Roll_number, Name, Date_of_Birth, Age) is

35
Consider the $$ALU$$ shown below GATE CSE 2003 Digital Logic - Combinational Circuits Question 10 English

If the operands are in $$2's$$ complement representation, which of the following operations can be performed by suitably setting the control lines $$K$$ and $${C_0}$$ only ( + and - denote addition and subtraction respectively)?

36
Assuming all numbers are in $$2's$$ complement representation, which of the following numbers is divisible by $$11111011?$$
37
The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $$(xy + xz)$$ is $$4.$$ What are the minimum possible literal counts of the product -of -sum and sum -of-product representations respectively of the function given by the following Karnaugh map? Here, $$X$$ denotes “don’t care” GATE CSE 2003 Digital Logic - K Maps Question 6 English
38
A 1- input, 2- output synchronous sequential circuit behaves as follows.

Let $${z_k},\,{n_k}$$ denote the number of $$0’s$$ and $$1’s$$ respectively in initial $$k$$ bits of the input

$$\left({{z_k} + {n_k} = k} \right).$$ The circuit outputs $$00$$ until one of the following conditions holds.

$$ * \,\,\,\,\,$$ $${z_k} = {n_k} + 2.\,\,\,$$ In this case, the output at the $$k$$-th and all subsequent clock ticks is $$10.$$

$$ * \,\,\,\,\,$$ $${n_k} = {z_k} + 2.\,\,\,$$ In this case, the output at the $$k$$-th and all subsequent clock ticks is $$01.$$

What is the minimum number of states required in the state transition graph of the above circuit?

39
Consider the following circuit composed of $$XOR$$ gates are non-inverting buffers. GATE CSE 2003 Digital Logic - Boolean Algebra Question 20 English 1

The non-inverting buffers have delays $${\delta _1} = 2$$ $$ns$$ and $${\delta _2} = 4$$ $$ns$$ as shown in the figure. Both $$XOR$$ gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level $$0$$ at time$$0.$$ If the following waveform is applied at input $$A$$, how many transition(s) (change of logic levels) occurs(s) at $$B$$ during the interval from $$0$$ to $$10$$ $$ns?$$

GATE CSE 2003 Digital Logic - Boolean Algebra Question 20 English 2
40
$$A$$ system of equations represented by $$AX=0$$ where $$X$$ is a column vector of unknown and $$A$$ is a square matrix containing coefficients has a non-trival solution when $$A$$ is.
41
$$\mathop {Lim}\limits_{x \to 0} \,{{Si{n^2}x} \over x} = \_\_\_\_.$$
42
How many perfect matchings are there in a complete graph of 6 vertices?
43
$$A$$ graph $$G$$ $$=$$ $$(V, E)$$ satisfies $$\left| E \right| \le \,3\left| V \right| - 6.$$ The min-degree of $$G$$ is defined as $$\mathop {\min }\limits_{v \in V} \left\{ {{{\mathop{\rm d}\nolimits} ^ \circ }egree\left( v \right)} \right\}$$. Therefore, min-degree of $$G$$ cannot be
44
Consider the following system of linear equations $$$\left[ {\matrix{ 2 & 1 & { - 4} \cr 4 & 3 & { - 12} \cr 1 & 2 & { - 8} \cr } } \right]\left[ {\matrix{ x \cr y \cr z \cr } } \right] = \left[ {\matrix{ \alpha \cr 5 \cr 7 \cr } } \right]$$$

Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of $$\alpha $$, does this system of equations have infinitely many solutions?

45
Let $$G$$ be an arbitrary graph with $$n$$ nodes and $$k$$ components. If a vertex is removed from $$G$$, the number of components in the resultant graph must necessarily lie between
46
$$m$$ identical balls are to be placed in $$n$$ distinct bags. You are given that $$m \ge kn$$, where $$k$$ is a natural number $$ \ge 1$$. In how many ways can the balls be placed in the bags if each bag must contain at least $$k$$ balls?
47
$$n$$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is
48
Let $$A$$ be a sequence of $$8$$ distinct integers sorted in ascending order. How many distinct pairs of sequence, $$B$$ and $$C$$ are there such that
i) Each is sorted in ascending order.
ii) $$B$$ has $$5$$ and $$C$$ has $$3$$ elements, and
iii) The result of merging $$B$$ $$C$$ gives $$A$$?
49
Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = $${\raise0.5ex\hbox{$\scriptstyle 1$} \kern-0.1em/\kern-0.15em \lower0.25ex\hbox{$\scriptstyle 2$}}$$, the values of $$P\,(A\,\left| {B) \,} \right.$$ and $$P\,(B\,\left| {A) \,} \right.$$ respectively are
50
The following resolution rule is used in logic programming. Derive clause $$\left( {P \vee Q} \right)$$ from clauses $$\left( {P \vee R} \right)$$, $$\left( {Q \vee \neg R} \right)$$.

Which of the following statements related to this rule is FALSE?

51
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?
52
A processor uses $$2$$-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $$32$$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $$10$$ most significant bits of the virtual address are used as index into the first level page table while the next $$10$$ bits are used as index into the second level page table. The $$12$$ least significant bits of the virtual address are used as offset within thepage. Assume that the page table entries in both levels of page tables are $$4$$ bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of $$96$$%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of $$90$$%. Main memory access time is $$10$$ ns, cache access time is $$1$$ ns, and TLB access time is also $$1$$ ns.

Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address $$0 \times 00000000,$$ two contiguous data pages starting at virtual address $$0 \times 00400000,$$ and a stack page starting at virtual address $$0 \times FFFFF000.$$ The amount of memory required for storing the page tables of this process is

53
A processor uses $$2$$-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $$32$$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $$10$$ most significant bits of the virtual address are used as index into the first level page table while the next $$10$$ bits are used as index into the second level page table. The $$12$$ least significant bits of the virtual address are used as offset within thepage. Assume that the page table entries in both levels of page tables are $$4$$ bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of $$96$$%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of $$90$$%. Main memory access time is $$10$$ ns, cache access time is $$1$$ ns, and TLB access time is also $$1$$ ns.

Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest $$0.5$$ ns)

54
In a system with $$32$$ bit virtual addresses and $$1$$ $$KB$$ page size, use of one-level page tables for virtual to physical address translation is not practical because of
55
Using a larger block size in a fixed block size file system leads to
56
A uni-processor computer system only has two processes, both of which alternate $$10$$ $$ms$$ $$CPU$$ bursts with $$90$$ $$ms$$ $${\rm I}/O$$ bursts. Both the processes were created at nearly the same time. The $${\rm I}/O$$ of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least $$CPU$$ utilization (over a long period of time) for this system?
57
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.

Process P:

while(1){
  W:
  Print '0';
  Print '0';
  X:
}

Process Q:

while(1){
  Y:
  Print '1';
  Print '1';
  Z:
}
Synchronization statements can be inserted only at points W, X, Y, and Z.

Which of the following will ensure that the output string never contains a substring of the form 01n0 or 10n1 where n is odd?

58
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below.

Process P:

while(1){
  W:
  Print '0';
  Print '0';
  X:
}

Process Q:

while(1){
  Y:
  Print '1';
  Print '1';
  Z:
}
Synchronization statements can be inserted only at points W, X, Y, and Z.

Which of the following will always lead to an output starting with 001100110011

59
Consider the C program shown below.
#include < stdio.h >
#define print(x) printf("%d ", x)
int x;
void Q(int z) {
   z += x; print(z);
}
void P(int *y) {
   int x = *y+2;
   Q(x); *y = x-1;
   print(x);
}
main(void) {
   x = 5;
   P(&x);
   print(x);
}
The output of this program is
60
The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print (x);
}
main() {
    P(i + j);
}
If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are
61
The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print (x);
}
main() {
    P(i + j);
}
If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are
62
Which of the following statements is FALSE?
63
Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.
Class P {
    void f(int i) {
           print(i);
          }
}

Class Q subclass of P {
       void f(int i) {
            print(2*i);
          }
}
Now consider the following program fragment:
Px = new Q();
Qy = new Q();
Pz = new Q();
x.f(1); ((P)y).f(1); z.f(1);
Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be
64
Assume the following C variable declaration

int * A[10], B[10][10];

Of the following expressions

I. A[2]
II. A[2] [3]
III. B[1]
IV. B[2] [3]

Which will not give compile-time errors if used as left hand sides of assignment statements in a C program?
65
Consider the following C function.
float f,(float x, int y) {
    float p, s; int i;
    for (s=1,p=1,i=1; i < y; i++) {
         p *= x/i;
         s+=p;
    }
return s;
}
For large values of y, the return value of the function f best approximates
66
Consider the set $$\sum {^ * } $$ of all strings over the alphabet $$\,\sum { = \,\,\,\left\{ {0,\,\,\,1} \right\}.\sum {^ * } } $$ with the concatenation operator for strings
67
The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ * $$denotes the same set as
68
Define Languages $${L_0}$$ and $${L_1}$$ as follows
$${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \right\}$$
$${L_1} = \left\{ { < M,w,1 > \left| M \right.} \right.$$ does not halts on $$\left. w \right\}$$

Here $$ < M,\,w,\,i > $$ is a triplet, whose first component, $$M$$ is an encoding of a Turing Machine, second component, $$w$$, is a string, and third component, $$t,$$ is a bit.
Let $$L = {L_0} \cup {L_1}.$$ Which of the following is true?

69
A single tape Turing Machine $$M$$ has two states $${q_0}$$ and $${q_1}$$, of which $${q_0}$$ is the starting state. The tape alphabet of $$M$$ is $$\left\{ {0,\,\,1,\,\,B} \right\}$$ and its input alphabet is $$\left\{ {0,\,\,1} \right\}$$. The symbol $$B$$ is the blank symbol used to indicate end of an input string. The transition function of $$M$$ is described in the following table. GATE CSE 2003 Theory of Computation - Recursively Enumerable Language and Turing Machine Question 23 English

The table is interpreted as illustrated below. The entry $$\left( {{q_1},1,\,R} \right)$$ in row $${{q_0}}$$ and column $$1$$ signifies that if $$M$$ is in state $${{q_0}}$$ and reads $$1$$ on the current tape square, then it writes $$1$$ on the same tape square, moves its tape head one position to the right and transitions to state $${{q_1}}$$.

Which of the following statements is true about $$M?$$

70
If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is true?
71
Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows
$$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,\,\,Otherwise} \cr } } \right.$$

Which of the following statement is true?

72
Consider the following deterministic finite state automation $$M.$$ GATE CSE 2003 Theory of Computation - Finite Automata and Regular Language Question 39 English

Let $$S$$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $$1$$. The number of strings in $$S$$ that are accepted by $$M$$ is

73
Consider the $$NFA$$ $$M$$ shown below. GATE CSE 2003 Theory of Computation - Finite Automata and Regular Language Question 40 English

Let the language accepted by $$M$$ be $$L.$$ Let $${L_1}$$ be the language accepted by the $$NFA$$, $${M_1}$$ obtained by changing the accepting state of $$M$$ to a non accepting state and by changing the non accepting state of $$M$$ to accepting states. Which of the following statements is true?

EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12