GATE CSE 2009
View Questions

GATE CSE

1
Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable from the source.
2
Consider a binary max-heap implemented using an array. What is the content of the array {25, 14, 16, 13, 10, 8, 12} after two delete operations?
3
Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?
4
What is the number of swaps required to sort n elements using selection sort, in the worst case?
5
The running time of an algorithm is represented by the following recurrence relation:
$$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$
Which one of the following represents the time complexity of the algorithm?
6
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
7
Consider the following graph: GATE CSE 2009 Algorithms - Greedy Method Question 24 EnglishWhich one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
8
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function I(i,j) to compute the length of the LCS of X[m] and Y[n] is given below:
l(i,j)  = 0, if either i = 0 or j = 0
        = expr1, if i,j > 0 and X[i-1] = Y[j-1]
        = expr2, if i,j > 0 and X[i-1] ≠ Y[j-1]
The value of l(i, j) could be obtained by dynamic programming based on the correct recursive definition of l(i, j) of the form given above, using an array L[M, N], where M = m+1 and N = n + 1, such that L[i, j] = l(i, j).

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?
9
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function I(i,j) to compute the length of the LCS of X[m] and Y[n] is given below:
l(i,j)  = 0, if either i = 0 or j = 0
        = expr1, if i,j > 0 and X[i-1] = Y[j-1]
        = expr2, if i,j > 0 and X[i-1] ≠ Y[j-1]
Which one of the following options is correct?
10
Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
11
Match all items in Group 1 with correct options from those given in Group 2.

Group 1

P. Regular expression
Q. Pushdown automata
R. Dataflow analysis
S. Register allocation

Group 2

1. Syntax analysis
2. Code generation
3. Lexical analysis
4. Code optimization
12
While opening a TCP connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order 32 bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter increments once per millisecond. The maximum packet lifetime is given to be 64s.

Which one of the choices given below is closest to the minimum permissible rate at which sequence numbers used for packets of a connection can increase?

13
In the RSA public key cryptosystem, the private and public keys are (e, n) and (d, n) respectively, where n = p$$ \times $$q and p and q are large primes. Besides, n is public and p and q are private. Let M be an integer such that 0 < M < n and f(n) = (p - 1)(q - 1). Now consider the following equations.

I. M'= Me mod n
M = (M')d mod n

II. ed ≡ 1 mod n

III. ed ≡ 1 mod $$\phi $$(n)

IV. M'= Me mod $$\phi $$(n)
M = (M')d mod $$\phi $$(n)

Which of the above equations correctly represent RSA cryptosystem?
14
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
15
Frames of 1000 bits are sent over a 106 bps duplex link between two hosts. The propagation time is 25 ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

Suppose that the sliding window protocol is used with the sender window size of 2l, where l is the number of bits identified in the earlier part and acknowledgements are always piggy backed. After sending 2l frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)
16
Frames of 1000 bits are sent over a 106 bps duplex link between two hosts. The propagation time is 25 ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).
What is the minimum number of bits (I) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames.
17
A $$CPU$$ generally handles an interrupt by executing an interrupt service routine
18
How many $$32k$$ x $$1$$ $$RAM$$ chips are needed to provide a memory capacity of $$256$$ $$K$$-bytes?
19
Consider a $$4$$-way set associative cache (initially empty) with total $$16$$ cache blocks. The main memory consists of $$256$$ blocks and the request for memory blocks is in the following order:
0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155.

Which one of the following memory block will NOT be in cache if $$LRU$$ replacement policy is used?

20
Consider a $$4$$ stage pipeline processor. The number of cycles needed by the four instructions $${\rm I}1,$$ $${\rm I}2,$$ $${\rm I}3,$$ $${\rm I}4,$$ in stages $$S1, S2, S3, S4$$ is shown below. GATE CSE 2009 Computer Organization - Pipelining Question 26 English

What is the number of cycles needed to execute the following loop?
For $$\left( {i = 1} \right.$$ to $$\left. 2 \right)$$ $$\left\{ {{\rm I}1;{\rm I}2;{\rm I}3;{\rm I}4;} \right\}$$

21
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
22
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
23
Consider the following relational schema:

Suppliers(sid : integer, sname : string, city : string, street : string)

Parts(pid : integer, pname : string, color : string)

Catalog(sid : integer, pid : integer, cost : real)

Consider the following relational query on the above database:
SELECT S.sname 
FROM Suppliers S 
WHERE S.sid NOT IN 
     (SELECT C.sid 
      FROM Catalog C 
      WHERE C.pid NOT IN 
        (SELECT P.pid 
         FROM Parts P 
         WHERE P.color<> 'blue'))
Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?
24
Consider the following relational schema:

Suppliers(sid : integer, sname : string, city : string, street : string)

Parts(pid : integer, pname : string, color : string)

Catalog(sid : integer, pid : integer, cost : real)

Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?
25
Consider two transactions T1 and T2 and four schedules S1, S2, S3, S4 of T1 and T2 as given below:

T1: R1[ x ] W1[ x ] W1[ y ]
T2: R2[ x ] R2[ y ] W2[ y ]
S1: R1[ x ] R2[ x ] R2[ y ] W1[ x ] W1[ y ] W2[ y ]
S2: R1[ x ] R2[ x ] R2[ y ] W1[ x ] W2[ y ] W1[ y ]
S3: R1[ x ] W1[ x ] R2[ x ] W1[ y ] R2[ y ] W2[ y ]
S4: R2[ x ] R2[ y ] R1[ x ] W1[ x ] W1[ y ] W2[ y ]

Which of the above schedules are conflict-serializable?
26
Let R and S be relational schemes such that R = { a, b, c } and S = { c }. Now consider the following queries on the database:

I. $$\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$$

II. $$\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall u \in s \left(\exists v \in r \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right )\right\}$$

III.$$\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall v \in r \left(\exists u \in s \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right ) \right\}$$

IV. Select R.a, R.b
    From R, S
    Where R.c = S.c
Which of the above queries are equivalent?
27
The following key values are inserted into a B+-tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+- tree is initially empty.

10, 3, 6, 8, 4, 2, 1

The maximum number of times leaf nodes would get split up as a result of these insertions is
28
$${\left( {1217} \right)_8}$$ is equivalent to
29
What is the minimum number of gates required to implement the Boolean function $$(AB+C)$$ if we have to use only $$2$$-input NOR gates?
30
Given the following state table of an $$FSM$$ with two states $$A$$ and $$B,$$ one input and one output: GATE CSE 2009 Digital Logic - Sequential Circuits Question 20 English

If the initial state is $$A = 0, B=0.$$ What is the minimum length of an input string which will take the machine to the state $$A=0, B=1$$ with Output$$=1?$$

31
Which one of the following is the most appropriate logical formula to represent the statement:

"$$Gold\,and\,silver\,ornaments\,are\,precious$$"

The following notations are used:
$$G\left( x \right):\,\,x$$ is a gold ornament.
$$S\left( x \right):\,\,x$$ is a silver ornament.
$$P\left( x \right):\,\,x$$ is precious.

32
Consider the following well-formed formulae:

$${\rm I}.$$ $$\,\,\neg \forall x\left( {P\left( x \right)} \right)$$
$${\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {P\left( x \right)} \right)$$
$${\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {\neg P\left( x \right)} \right)$$
$${\rm I}V.\,\,\,\,\,\,\exists x\left( {\neg P\left( x \right)} \right)$$

Which of the above are equivalent?

33
Which one of the following in NOT necessarily a property of Group?
34
consider the binary relation $$R = \left\{ {\left( {x,y} \right),\,\left( {x,z} \right),\,\left( {z,x} \right),\,\left( {z,y} \right)} \right\}$$ on the set $$\left\{ {x,\,y,\,z} \right\}$$. which one of the following is TRUE?
35
The binary operation ◻ is defined as follows: GATE CSE 2009 Discrete Mathematics - Mathematical Logic Question 14 English

Which one of the following is equivalence to $$P \vee Q$$?

36
For the compositive table of a cyclic group shown below GATE CSE 2009 Discrete Mathematics - Set Theory & Algebra Question 34 English

Which one of the following choices is correct?

37
What is the chromatic number of an $$n$$-vertex simple connected graph which does not contain any odd length cycle? Assume $$n \ge 2$$.
38
Which one of the following is TRUE for any simple connected undirected graph with more than $$2$$ vertices?
39
$$\int\limits_0^{\pi /4} {\left( {1 - \tan x} \right)/\left( {1 + \tan x} \right)dx} $$ $$\,\,\,\,\,\,$$ evaluates to
40
An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face valueis even. The probability of getting any even bnumbered face is the same.

If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?

41
The essential content(s) in each entry of a page table is / are:
42
How many $$32K\,\, \times \,\,1RAM$$ chips are needed to provide a memory capacity of $$256$$ $$K$$-bytes?
43
Consider the virtual page reference string $$$1,2,3,2,4,1,3,2,4,1$$$
On a demand paged virtual memory system running on a computer system that has main memory size of $$3$$ page frames which are initially empty. Let $$LRU,$$ $$FIFO$$ and $$OPTIMAL$$ denote the number of page faults under the corresponding page replacement policy. Then
44
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because.
45
Consider a disk system with $$100$$ cylinders. The requests to access the cylinders occur in following sequence:
$$4, 34, 10, 7, 19, 73, 2, 15, 6, 20$$
Assuming that the head is currently at cylinder $$50,$$ what is the time taken to satisfy all requests if it takes $$1$$ $$ms$$ to move from one cylinder to adjacent one and shortest seek time first policy is used?
46
In which one of the following page replacement policies, Belady’s anomaly may occur?
47
Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently. GATE CSE 2009 Operating Systems - Deadlocks Question 15 English Which one of the following statements is TRUE if all three processes run concurrently starting at time t = 0?
48
A CPU generally handles an interrupt by executing an interrupt service routine
49
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: GATE CSE 2009 Operating Systems - Process Concepts and Cpu Scheduling Question 23 English

Now consider the following statements:
$$1.\,\,\,$$ If a process makes a transition $$D,$$ it would result in another process making transition $$A$$ immediately.
$$2.\,\,\,$$ $$A$$ process $${P_2}$$ in blocked state can make transition $$E$$ while another process $${P_1}$$ is in running state.
$$3.\,\,\,$$ The $$OS$$ uses preemptive scheduling.
$$4.\,\,\,$$ The $$OS$$ uses non-preemptive scheduling. Which of the above statements are TRUE?

50
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:
void enter_CS(X) { 
   while test-and-set(X) ; 
} 

void leave_CS(X) { 
  X=0; 
}
In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:

I. The above solution to CS problem is deadlock-free
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV More than one process can enter CS at the same time.

Which of the above statements is TRUE?
51
The coupling between different modules of a software is categorized as follows
$${\rm I}.\,\,\,\,\,\,\,\,\,\,\,$$ Content coupling
$${\rm II}.\,\,\,\,\,\,\,\,\,$$ Common coupling
$${\rm III}.\,\,\,\,\,\,\,$$ Control coupling
$${\rm IV}.\,\,\,\,\,\,\,$$ Stamp coupling
$${\rm V}.\,\,\,\,\,\,\,\,\,$$ Data coupling
Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows.
52
Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE?

$${\rm I}.\,\,\,\,\,\,$$ The cyclomatic complexity of a module is equal to the maximum number of
$$\,\,\,\,\,\,\,\,\,\,\,$$linearly independent circuits in the graph.
$${\rm II}.\,\,\,$$ The cyclomatic complexity of a module is the number of decisions in the
$$\,\,\,\,\,\,\,\,\,\,$$module plus one, where a decision is effectively any conditional statement in
$$\,\,\,\,\,\,\,\,\,\,$$the module.
$${\rm III}\,$$ The cyclomatic complexity can also be used as a number of linearly
$$\,\,\,\,\,\,\,\,\,\,$$independent paths that should be tested during path coverage testing.

53
Which of the following statements are TRUE?

$${\rm I}.\,\,\,\,\,\,$$ The content diagram should depict the system as a single bubble.
$${\rm II}.\,\,\,\,$$ External entities should be identified clearly at all levels of $$DFDs$$
$${\rm III}.\,\,$$ Control information should not be represented in $$DFD$$
$${\rm IV}.\,\,$$ A data store can be connected either to another data store or to an external
$$\,\,\,\,\,\,\,\,\,\,\,\,$$entity.

54
Which one of the following languages over the alphabet $$\left\{ {0,\left. 1 \right)} \right.$$ is described by the regular expression $${\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^ * }$$
55
$$L = {L_1} \cap {L_2}$$ where $${L_1}$$ and $${L_2}$$ are languages defined as follows.
$${L_1} = \left\{ {{a^m}{b^m}\,c\,{a^n}{b^n}\left| {m,n \ge 0} \right.} \right\}$$
$${L_2} = \left\{ {{a^i}{b^i}{c^k}\left| {i,j,k \ge 0} \right.} \right\}$$ Then $$L$$ is
56
GATE CSE 2009 Theory of Computation - Finite Automata and Regular Language Question 55 English

The above $$DFA$$ accepts the set of all strings over $$\left\{ {0,\,\,1} \right\}$$ that

57
Which one of the following is FALSE?
58
$$S \to aSa\,\left| {\,bSb\,\left| {\,a\,\left| {\,b} \right.} \right.} \right.$$
The language generated by the above grammar over the alphabet $$\left\{ {a,\,b} \right\}$$ is the set of
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