## GATE 2008

 Question 1 equals
 A 1 B -1 C ∞ D -∞
Engineering-Mathematics       Calculus
Question 1 Explanation: Question 2

If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (Pc∩Q∩R) ∪ Q∪ Rc is

 A Qc ∪ Rc B P ∪ Qc ∪ Rc C Pc ∪ Qc ∪ Rc D U
Engineering-Mathematics       Sets-And-Relation
Question 2 Explanation:
Given,
(P∩Q∩R)∪(Pc∩Q∩R)∪Qc∪Rc
It can be written as the p.q.r + p'.q.r +q' + r'
=> (p+p').q.r + q' + r'
=> q.r + (q'+r')
=> q.r + q' + r' = 1 i.e., U
 Question 3

The following system of equations

x1 + x2 + 2x3  = 1
x1 + 2x2 + 3x3 = 2
x1 + 4x2 + ax3 = 4

has a unique solution. The only possible value(s) for a is/are

 A 0 B either 0 or 1 C one of 0, 1 or -1 D any real number
Engineering-Mathematics       Linear-Algebra
Question 3 Explanation:
The conjugate matrix [A|B] is When a-5 = 0, then rank(A) = rank[A|B]<3,
So infinite number of solutions.
But, it is given that the given system has unique solution i.e., rank(A) = rank[A|B] = 3 will be retain only if a-5 ≠ 0.
 Question 4

In the IEEE floating point representation, the hexadecimal value 0×00000000 corresponds to

 A the normalized value 2 - 127 B the normalized value 2 - 126 C the normalized value + 0 D the special value + 0
Digital-Logic-Design       Number-Systems
Question 4 Explanation:
Value is ±0 if M=0 and E=0. Question 5

In the Karnaugh map shown below, X denotes a don’t care term. What is the minimal form of the function represented by the Karnaugh map? A B C D Digital-Logic-Design       K-Map
Question 5 Explanation: Question 6

Let r denote number system radix. The only value(s) of r that satisfy the equation is/are

 A decimal 10 B decimal 11 C decimal 10 and 11 D any value > 2
Digital-Logic-Design       Number-Systems
Question 6 Explanation:
√121r = 11r
(r2 + 2r + 1)1/2 = r + 1
(r + 1)2 * 1/2 = r + 1
r + 1 = r + 1 Any value of r will satisfy the above equation. But the radix should be greater than 2 because the 121 has 2. So r > 2 is correct.
 Question 7

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

 A θ(n) B θ(m) C θ(m+n) D θ(mn)
Data-Structures       Graphs
Question 7 Explanation:
To find the number of connected components using either BFS or DFS time complexity is θ(m+n).
Suppose if we are using Adjacency matrix means it takes θ(n2).
 Question 8

Given f1, f3 and f in canonical sum of products form (in decimal) for the circuit f1 = Σm(4,5,6,7,8)
f3 = Σm(1,6,15)
f = Σm(1,6,8,15)

then f2 is

 A Σm(4,6) B Σm(4,8) C Σm(6,8) D Σm(4,6,8)
Data-Structures       Canonical-Normal-Form
Question 8 Explanation:
f = f1* f2 + f3
f1*f2 is intersection of minterms of f1 and f2
f = (f1*f2) + f3 is union of minterms of (f1*f2) and f3
Σm(1,6,8,15) = Σm(4,5,6,7,8) * f2 + Σm(1,6,15)
Options A, B and D have minterm m4 which result in Σm(1,4,6,15), Σm(1,4,6,8, 15) and Σm(1,4,6,8, 15)respectively and they are not equal to f.
Option C : If f2 = Σm(6,8)
RHS: Σm(4,5,6,7,8) * Σm(6,8) + Σm(1,6,15)
= Σm(6,8) + Σm(1,6,15)
= Σm(1,6,8,15)
= f = LHS
 Question 9

Which of the following is true for the language {ap|p is a prime} ?

 A It is not accepted by a Turing Machine B It is regular but not context-free C It is context-free but not regular D It is neither regular nor context-free, but accepted by a Turing machine
Theory-of-Computation       Identify-Class-Language
Question 9 Explanation:
Finding prime number cannot be done by FA or PDA, so it cannot be regular or CFL. This language can be recognized by LBA, hence it can be accepted by Turing Machine.
 Question 10

Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
 A I and II B I and IV C II and III D II and IV
Theory-of-Computation       Decidability-and-Undecidability
Question 10 Explanation:
The intersection of two regular languages is always a regular language (by closure property of regular language) and testing infiniteness of regular language is decidable. Hence statement I is decidable.
Statement IV is also decidable, we need to check that whether the given grammar satisfies the CFG rule (TYPE 2 grammar productions).
But statements II and III are undecidable, as there doesn’t exist any algorithm to check whether a given context-free language is regular and whether two push-down automata accept the same language.
 Question 11

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

 A It is the position in a sentential form where the next shift or reduce operation will occur. B It is non-terminal whose production will be used for reduction in the next step. C It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur. D It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
Compiler-Design       Parsers
Question 11 Explanation:
A handle is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
 Question 12

Some code optimizations are carried out on the intermediate code because

 A They enhance the portability of the compiler to other target processors B Program analysis is more accurate on intermediate code than on machine code C The information from dataflow analysis cannot otherwise be used for optimization D The information from the front end cannot otherwise be used for optimization
Compiler-Design       Compilers
Question 12 Explanation:
The code-optimization on intermediate code generation will always enhance the portability of the compiler to target processors. The main reason behind this is, as the intermediate code is independent of the target processor on which the code will be executed, so the compiler is able to optimize the intermediate code more conveniently without bothering the underlying architecture of target processor.
 Question 13

If L and are recursively enumerable, then L is

 A regular B context-free C context-sensitive D recursive
Theory-of-Computation       Recursive-Enumerable-Languages
Question 13 Explanation:
If L is recursive enumerable, then it implies that there exist a Turing Machine (lets say M1) which always HALT for the strings which is in L.
If are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L. This implies that L must be recursive.
 Question 14

What is the maximum size of data that the application layer can pass on to the TCP layer below?

 A Any size B 216 bytes-size of TCP header C 216 bytes D 1500 bytes
Computer-Networks       Application-Layer-Protocol
Question 14 Explanation:
Application Layer - Any size
Transport Layer - 65515 byte
Network layer - 65535 byte
Data link layer - 1500 byte
 Question 15

Which of the following tuple relational calculus expression(s) is/are equivalent to ∀t ∈ r(P(t))?

I. ¬∃t ∈ r(P(t))
II. ∃t ∉ r(P(t))
III. ¬∃t ∈ r(¬P(t))
IV. ∃t ∉ r(¬P(t))
 A I only B II only C III only D III and IV only
Database-Management-System       Relational-Calculus
Question 15 Explanation:
Demorgan law:
∀xP(x) ≡ ∼∃x(∼P(x))
∼∀x(∼P(x)) ≡ ∃x(P(x))
Given: ∀t ∈ r(P(t))------ (1)
As per Demorgan law
(1) ⇒ ∼∃t ∈ r(∼P(t))
which is option (III).
 Question 16

A clustering index is defined on the fields which are of type

 A non-key and ordering B non-key and non-ordering C key and ordering D key and non-ordering
Database-Management-System       Indexing
Question 16 Explanation:
Create index files, fields could be non-key attributes and which are in ordered form so as to form clusters easily.
 Question 17

Which of the following system calls results in the sending of SYN packets?

 A socket B bind C listen D connect
Computer-Networks       Sockets
Question 17 Explanation:
When connect( ) is called by client, following three way handshake happens to establish the connection in TCP.
1) The client requests a connection by sending a SYN (synchronize) message to the server.
2) The server acknowledges this request by sending SYN-ACK back to the client.
3) The client responds with an ACK, and the connection is established.
 Question 18

Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression?

`     a = (x > y) ? ((x > z) ? x : z) : ((y > z) ? y : z) `
 A x = 3, y = 4, z = 2 B x = 6, y = 5, z = 3 C x = 6, y = 3, z = 5 D x = 5, y = 4, z = 5
Programming       C-Programming
Question 18 Explanation:
Required final output value of a=4.
→ We can directly eliminate the options B & C, because none of the variable can assign a value 4.
→ Given explanation is
a = (x>y)?((x>z)?x:z):((y>z)?y:z)
Option A:
x=3; y=4; z=2
a=(3>4)? ⇒ No
Then evaluate second expression ⇒ (4>2)?Yes
⇒a=y
a=4 (True)
Option D:
x=5; y=4; z=5
a=(5>4) ⇒ Yes
Then evaluate first expression ⇒ (5>5)? No
⇒ a=z ⇒ a=5 (Not true)
 Question 19

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is A MNOPQR B NQMPOR C QMNPRO D QMNPOR
Data-Structures       Graphs
Question 19 Explanation: Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).
 Question 20

The data blocks of a very large file in the Unix file system are allocated using

 A contiguous allocation B linked allocation C indexed allocation D an extension of indexed allocation
Operating-Systems       File-System
Question 20 Explanation:
An Unix file system can utilizes an extension of indexed allocation. Because it uses direct blocks, single indirect blocks, double indirect blocks and triple indirect blocks.
 Question 21

The minimum number of equal length subintervals needed to approximate to an accuracy of atleast using the trapezoidal rule is

 A 1000e B 1000 C 100e D 100
Engineering-Mathematics       Trapezidal Rule
Question 21 Explanation:
Note: Out of syllabus.
There are 21 questions to complete.

Register Now