GATE 2014 for IITs and PSUs: July 2010

Training Center	Apex Academy
Course Name	Correspondence Course For GATE
Category	GATE Entrance
Fees	Rs. 11,067 /-
Duration	1 year
Location	Mumbai, Maharashtra

The GATE Programme is designed to test how strong your concepts and fundamentals are. The Programme emphasizes on logical, analytical, conceptual and problem solving skills that should be acquired by the students. The course is designed and conducted in such a way that, the student acquires the right temperament and develop a strong confidence to face the GATE examination.

The course material is continuous researched, after analyzing the trends of the past and the current GATE papers, prepared by our subject expert team of IIT’ians and professors from Universities. Regular feedback will be obtained from students and the study material will be upgraded constantly. Very Important feature of our study material is POINTS TO REMEMBER which contains very Important and critical points of each subject with formulae. Our study materials contain scores of challenging problems to be solved by the students. This course is very demanding on your efforts and requires commitment and determination to meet the challenges. Actually preparation of GATE will prepare you for other competitive examinations like IES, UPSC, etc.

Features:
Eight sets of study material in each Stream & Two sets of Mathematics covering entire GATE Syllabus.
Five Assignments for each Subject to be attempted at home and submitted to us for evaluation.
Six Mock Tests, strictly as per the GATE examination Pattern. All tests will follow the latest GATE pattern comprising of all new questions.
Total Twenty Subject- wise Home Test Series of One hour duration.
Total Sixteen Subject- wise Home Test Series of One hour duration for Pharmaceutical Sciences.
Total Sixteen Evaluation of test papers, along with detailed solution.
Test report along with statistical analysis, relative ranking.
Queries reply.
Last 15 year GATE papers with solution of objective

Q. No. 1 – 25 Carry One Mark Each
1. Let G=(V, E) be a graph. Define ( ) d
d
ξG= Σi×d, where id is the number of
vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T) ,
then
(A) S =2T (B) S=T−1 (C) S=T (D) S=T+1
2. Newton-Raphson method is used to compute a root of the equation x2 −13=0
with 3.5 as the initial value. The approximation after one iteration is
(A) 3.575 (B) 3.676 (C) 3.667 (D) 3.607
3. What is the possible number of reflexive relations on a set of 5 elements?
(A) 210 (B) 215 (C) 220 (D) 225
4. Consider the set S = {1, ω, ω2}, where ω and ω2 are cube roots of unity. If *
denotes the multiplication operation, the structure (S, *) forms
(A) A group (B) A ring
(C) An integral domain (D) A field
5. What is the value of
2n
n
1
lim 1 ?
→∞ n
⎛⎜ − ⎞⎟
⎝ ⎠
(A) 0 (B) e-2 (C) e-1/2 (D) 1
6. The minterm expansion of f (P, Q, R)=PQ+QR +PR is
(A) 2 4 6 7 m +m +m +m (B) 0 1 3 5 m +m +m +m
(C) 0 1 6 7 m +m +m +m (D) 2 3 4 5 m +m +m +m
7. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The
time taken for a single refresh operation is 100 nanoseconds. The time required
to perform one refresh operation on all the cells in the memory unit is
(A) 100 nanoseconds (B) 100*210 nanoseconds
(C) 100*220 nanoseconds (D) 3200*220 nanoseconds
8. P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)16.
The 2’s complement representation of 8*P is
(A) ( )16 C3D8 (B) ( )16 187B (C) ( )16 F878 (D) ( )16 987B
9. The Boolean expression for the output f of the multiplexer shown below is
(A) P⊕Q⊕R
(B) P⊕Q⊕R
(C) P+Q+R
(D) P+Q+R
10. In a binary tree with n nodes, every node has an odd number of descendants.
Every node is considered to be its own descendant. What is the number of nodes
in the tree that have exactly one child?
(A) 0 (B) 1 (C) (n−1)/2 (D) n-1
11. What does the following program print?
( )
( )
#include stdio.h
void f int *p, int * g {
p q;
*p 2;
}
int i 0, j 1;
int main ( ){
f(&i, & j);
pr int f "%d%d \ n", i, j ;
return 0;
}
< >
=
=
= =
(A) 2 2 (B) 2 1 (C) 0 1 (D) 0 2
12. Two alternative packages A and B are available for processing a database having
10k records. Package A requires 0.0001n2 time units and package B requires
10nlog10n time units to process n records. What is the smallest value of k for
which package B will be preferred over A?
(A) 12 (B) 10 (C) 6 (D) 5
13. Which data structure in a compiler is used for managing information about
variables and their attributes?
(A) Abstract syntax tree (B) Symbol table
(C) Semantic stack (D) Parse table
14. Which languages necessarily need heap allocation in the runtime environment?
(A) Those that support recursion (B) Those that use dynamic scoping
(C) Those that allow dynamic data structures (D) Those that use global variables
15. One of the header fields in an IP datagram is the Time to Live (TTL) field. Which
of the following statements best explains the need for this field?
(A) It can be used to prioritize packets
(B) It can be used to reduce delays
(C) It can be used to optimize throughput
(D) It can be used to prevent packet looping
16. Which one of the following is not a client server application?
(A) Internet chat (B) Web browsing (C) E-mail (D) Ping
17. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively
enumerable but not recursive. Which of the following statements is not
necessarily true?
(A) L2 – L1 is recursively enumerable
(B) L1 – L3 is recursively enumerable
(C) L2 ∩ L1 is recursively enumerable
(D) L2 ∪ L1 is recursively enumerable
18. Consider a B+-tree in which the maximum number of keys in a node is 5. What is
the minimum number of keys in any non-root node?
(A) 1 (B) 2 (C) 3 (D) 4
19. A relational schema for a train reservation database is given below
( )
( )
Passenger pid, pname, age
Re servation pid, cass, tid
Table :Passenger
pid 'pname Age
0 'Sachin' 65
1 'Rahul' 66
2 'Sourav' 67
3 'Anil' 69
Table :Re servation
pid class tid
0 'AC' 8200
1 'AC' 8201
2 'SC' 8201
5 'AC' 8203
1 'SC' 8204
3 'AC' 8202
What pids are returned by the following SQL query for the above instance of the
tables?
SELECT pid
FROM Re servation
WHERE class 'AC' AND
EXISTS (SELECT *
FROM Passenger
WHERE age 65 AND
Passenger.pid Reservation.pid)
=
>
=
(A) 1, 0 (B) 1, 2 (C) 1, 3 (D) 1, 5
20. Which of the following concurrency control protocols ensure both conflict
serializability and freedom from deadlock?
I. 2-phase locking
II. Time-stamp ordering
(A) I only (B) II only
(C) Both I and II (D) Neither I nor II
21. The cyclomatic complexity of each of the modules A and B shown below is
10. What is the cyclomatic complexity of the sequential integration shown on
the right hand side?
(A) 19 (B) 21 (C) 20 (D) 10
22. What is the appropriate pairing of items in the two columns listing various
activities encountered in a software life cycle?
P. Requirements Capture 1. Module Development and Integration
Q. Design 2. Domain Analysis
R. Implementation 3. Structural and Behavioral Modeling
S. Maintenance 4. Performance Tuning
(A) P-3, Q-2,R-4,S-1 (B) P-2, Q-3,R-1,S-4
(C) P-3, Q-2,R-1,S-4 (D) P-2, Q-3,R-4,S-1
23. Consider the methods used by processes P1 and P2 for accessing their critical
sections whenever needed, as given below. The initial values of shared boolean
variables S1 and S2 are randomly assigned.
Method used by PI Method used by P2
while (S1 = = S2) ;
Critica1 Section
S1 = S2;
while (S1 != S2) ;
Critica1 Section
S2 = not (S1);
Which one of the following statements describes the properties achieved?
(A) Mutual exclusion but not progress
(B) Progress but not mutual exclusion
(C) Neither mutual exclusion nor progress
(D) Both mutual exclusion and progress
24. A system uses FIFO policy for page replacement. It has 4 page frames with no
pages loaded to begin with. The system first accesses 100 distinct pages in some
order and then accesses the same 100 pages but now in the reverse order. How
many page faults will occur?
(A) 196 (B) 192 (C) 197 (D) 195
25. Which of the following statements are true?
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time
(A) I only (B) I and III only (C) II and III only (D) I, II and III
Q. No. 26 – 51 Carry Two Marks Each
26. Consider a company that assembles computers. The probability of a faulty
assembly of any computer is p. The company therefore subjects each
computer to a testing process. This testing process gives the correct result for
any computer with a probability of q. What is the probability of a computer
being declared faulty?
(A) pq+(1−p)(1− q) (B) (1−q)p (C) (1−p)q (D) pq
27. What is the probability that divisor of 1099 is a multiple of 1096?
(A) 1/625 (B) 4/625 (C) 12/625 (D) 16/625
28. The degree sequence of a simple graph is the sequence of the degrees of the
nodes in the graph in decreasing order. Which of the following sequences can not
be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1
(A) I and II (B) III and IV (C) IV only (D) II and IV
29. Consider the following matrix
2 3
A
x y
⎡ ⎤
= ⎢ ⎥
⎣ ⎦
If the eigenvalues of A are 4 and 8, then
(A) x=4,y=10 (B) x=5,y=8 (C) x= −3,y=9 (D) x= −4,y=10
30. Suppose the predicate F(x, y, t) is used to represent the statement that person x
can fool person y at time t. which one of the statements below expresses best
the meaning of the formula ∀x∃y∃t(¬F(x,y,t))?
(A) Everyone can fool some person at some time
(B) No one can fool everyone all the time
(C) Everyone cannot fool some person all the time
(D) No one can fool some person at some time
31. What is the Boolean expression for the output f of the combinational logic circuit
of NOR gates given below?
(A) Q+R
(B) P+Q
(C) P+R
(D) P+Q+R
32. In the sequential circuit shown below, if the initial value of the output Q1Q0 is 00,
what are the next four values of Q1Q0?
(A) 11,10,01,00
(B) 10,11,01,00
(C) 10,00,01,11
(D) 11,10,00,01
T Q
Q0 Q1
33. A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID),
Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages.
The IF, ID, OF and WO stages take 1 clock cycle each for any instruction. The PO
stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL
instruction, and 6 clock cycles for DIV instruction respectively. Operand
forwarding is used in the pipeline. What is the number of clock cycles needed to
execute the following sequence of instructions?
0 2 0 1 2 0 1
1 5 3 4 5 3 4
2 2 5 2 2 5 2
3 5 2 6 5 2 6
Instruction Meaning of instruction
I :MUL R ,R ,R R R *R
I :DIV R ,R ,R R R /R
I : ADD R ,R ,R R R R
I :SUB R ,R ,R R R R
←
←
← +
← −
(A) 13 (B) 15 (C) 17 (D) 19
34. The weight of a sequence a0, a1,…,an-1 of real numbers is defined as
n 1
0 1 n1 a a /2 ... a /2 − .
− + + + A subsequence of a sequence is obtained by deleting
some elements from the sequence, keeping the order of the remaining elements
the same. Let X denote the maximum possible weight of a subsequence of
0 1 n1 a ,a ,...,a . − Then X is equal to
(A) ( ) 0 max Y, a + Y (B) ( ) 0 max Y, a + Y /2 (C) ( ) 0 max Y, a +2Y (D) 0a +Y/2
35. What is the value printed by the following C program?
#include stdio.h
int f(int * a, int n)
{
if (n 0)return 0;
else if(*a% 2 0) return * a f(a 1,n 1);
else return * a f(a 1, n 1);
}
int main ( )
{
int a[ ] {12, 7, 13, 4, 11, 6};
pr int f ("%d", f(a,6));
return 0;
}
< >
<=
= = + + −
− + −
=
(A) -9 (B) 5 (C) 15 (D) 19
36. The following C function takes a simply-linked list as input argument. It modifies
the list by moving the last element to the front of the list and returns the
modified list. Some part of the code is left blank.
typedef struct node {
int value;
struct node *next;
} Node;
Node *move_to_front(Node *head) {
Node *p, *q;
if ((head = = NULL: || (head->next = = NULL)) return head;
q = NULL; p = head;
while (p-> next !=NULL) {
q=P;
p=p->next;
}
_______________________________
return head;
}
Choose the correct alternative to replace the blank line.
(A) q = NULL; p->next = head; head = p;
(B) q->next = NULL; head = p; p->next = head;
(C) head = p; p->next = q; q->next = NULL;
(D) q->next = NULL; p->next = head; head = p;
37. The program below uses six temporary variables a, b, c, d, e, f.
a 1
b 10
c 20
d a b
e c d
f c e
b c e
e b f
d 5 e
return d f
=
=
=
= +
= +
= +
= +
= +
= +
+
Assuming that all operations take their operands from registers, what is the
minimum number of registers needed to execute this program without spilling?
(A) 2 (B) 3 (C) 4 (D) 6
38. The grammar S → aSa|bS|c is
(A) LL(1) but not LR(1) (B) LR(1) but not LR(1)
(C) Both LL(1) and LR(1) (D) Neither LL(1) nor LR(1)
39. Let L ={w∈(0+1)*|w has even number of 1s}, i.e. L is the set of all bit strings
with even number of 1s. Which one of the regular expressions below represents
L?
(A) (0*10*1)* (B) 0*(10*10*) *
(C) 0*(10*1*)*0* (D) 0*1(10*1) *10*
40. Consider the languages L1={0i1j | i ≠ j}. L2 ={0i1j | i = j}. L3 ={0i1j | i = 2j + 1}.
L4 ={0i1j | i ≠ 2j}. Which one of the following statements is true?
(A) Only L2 is context free (B) Only L2 and L3 are context free
(C) Only L1 and L2 are context free (D) All are context free
41. Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w.
What is the minimum number of states in a non-deterministic finite automaton
that accepts L?
(A) n-1 (B) n (C) n+1 (D) 2n-1
42. Consider the following schedule for transactions T1, T2 and T3:
( )
( )
( )
( )
( )
( )
( )
( )
T1 T2 T3
Re ad X
Re ad Y
Re ad Y
Write Y
Write X
Write X
Re ad X
Write X
Which one of the schedules below is the correct serialization of the above?
(A) T1→T3→T2 (B) T2→T1→T3
(C) T2→T3→T1 (D) T3→T1→T2
43. The following functional dependencies hold for relations R(A, B, C) and S(B, D, E)
B A,
A C
→
→
The relation R contains 200tuples and the relation S contains 100tuples. What is
the maximum number of tuples possible in the natural join R S?
(A) 100 (B) 200 (C) 300 (D) 2000
44. The following program is to be tested for statement coverage:
( ) { }
( ) { }
{ }
= =
= =
begin
if a b S1; exit;
else if c d S2;
else S3; exit;
S4;
end
The test cases T1, T2, T3 and T4 given below are expressed in terms of the
properties satisfied by the values of variables a, b, c and d. The exact values are
not given.
T1 : a, b, c and d are all equal
T2 : a, b, c and d are all distinct
T3 : a=b and c !=d
T4 : a !=b and c=d
Which of the test suites given below ensures coverage of statements S1, S2, S3
and S4?
(A) T1, T2, T3 (B) T2, T4 (C) T3, T4 (D) T1, T2, T4
45. The following program consists of 3 concurrent processes and 3 binary
semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.
Process P0 Process P1 Process P2
while (true) {
wait (S0);
print ‘0’
release (S1);
release (S2);
}
wait (S1);
Release (S0);
wait (S2);
release (S0);
How many times will process P0 print ‘0’?
(A) At least twice (B) Exactly twice (C) Exactly thrice (D) Exactly once
46. A system has n resources R0,…,Rn-1, and k processes P0,…..Pk-1. The
implementation of the resource request logic of each process Pi. is as follows:
i
i+2
n-i
n-i-2
if (i% 2==0) {
if (iif (i+2}
else {
if (iif (i+2}
In which one of the following situations is a deadlock possible?
(A) n=40,k=26 (B) n=21,k=12 (C) n=20,k=10 (D) n=41,k=19
47. Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91
respectively and they both use the same net mask N. Which of the values of N
given below should not be used if A and B should belong to the same network?
(A) 255.255.255.0 (B) 255.255.255.128
(C) 255.255.255.192 (D) 255.255.255.224
Common Data Questions: 48 & 49
A computer system has an L1 cache, an L2 cache, and a main memory unit
connected as shown below. The block size in L1 cache is 4 words. The block size
in L2 cache is 16 words. The memory access times are 2 nanoseconds.
20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory
unit respectively.
48. When there is a miss in L1 cache and a hit in L2 cache, a block is transferred
from L2 cache to L1 cache. What is the time taken for this transfer?
(A) 2 nanoseconds (B) 20 nanoseconds
(C) 22 nanoseconds (D) 88 nanoseconds
49. When there is a miss in both L1 cache and L2 cache, first a block is transferred
from main memory to L2 cache, and then a block is transferred from L2 cache to
L1 cache. What is the total time taken for these transfers?
(A) 222 nanoseconds (B) 888 nanoseconds
(C) 902 nanoseconds (D) 968 nanoseconds
Common Data Questions: 50 & 51
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in
the matrix W below is the weight of the edge {i, j}.
0 1 8 1 4
1 0 12 4 9
W 8 12 0 7 3
1 4 7 0 2
4 9 3 2 0
⎛ ⎞
⎜ ⎟
⎜ ⎟
=⎜ ⎟
⎜ ⎟
⎜ ⎟
⎜ ⎟
⎝ ⎠
50. What is the minimum possible weight of a spanning tree T in this graph such that
vertex 0 is a leaf node in the tree T?
(A) 7 (B) 8 (C) 9 (D) 10
51. What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this
graph such that P contains at most 3 edges?
(A) 7 (B) 8 (C) 9 (D) 10
Linked Answer Questions: Q.52 to Q.55 Carry Two Marks Each
Statement for Linked Answer Questions: 52 & 53
A hash table of length 10 uses open addressing with hash function h(k)=k
mod 10, and linear probing. After inserting 6 values into an empty hash table,
the table is as shown below
0
1
2 42
3 23
4 34
5 52
6 46
7 33
8
9
52. Which one of the following choices gives a possible order in which the key values
could have been inserted in the table?
(A) 46, 42, 34, 52, 23, 33 (B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33 (D) 42, 46, 33, 23, 34, 52
53. How many different insertion sequences of the key values using the same hash
function and linear probing will result in the hash table shown above?
(A) 10 (B) 20 (C) 30 (D) 40
Statement for Linked Answer Questions: 54 & 55
Consider a network with 6 routers R1 to R6 connected with links having
weights as shown in the following diagram
54. All the routers use the distance vector based routing algorithm to update their
routing tables. Each router starts with its routing table initialized to contain an
entry for each neighbour with the weight of the respective connecting link.
After all the routing tables stabilize, how many links in the network will never
be used for carrying any data?
(A) 4 (B) 3 (C) 2 (D) 1
55. Suppose the weights of all unused links in the previous question are changed
to 2 and the distance vector algorithm is used again until all routing tables
stabilize. How many links will now remain unused?
(A) 0 (B) 1 (C) 2 (D) 3
Q. No. 56 – 60 Carry One Mark Each
56. Choose the most appropriate word from the options given below to the complete
the following sentence:
His rather casual remarks on politics ___________ his lack of seriousness about
the subject.
(A) masked (B) belied (C) betrayed (D)suppressed
57. Which of the following options is closest in meaning to the word Circuitous.
(A) cyclic (B) indirect (C) confusing (D) crooked
58. Choose the most appropriate word from the options given below to complete the
following sentence:
If we manage to ____________ our natural resources, we would leave a better
planet for our children.
(A) uphold (B) restrain (C) cherish (D) conserve
59. 25 persons are in a room. 15 of them play hockey, 17 of them play football and
10 of them play both hockey and football. Then the number of persons playing
neither hockey nor football is:
(A) 2 (B) 17 (C) 13 (D) 3
60. The question below consists of a pair of related words followed by four pairs of
words. Select the pair that best expresses the relation in the original pair.
Unemployed: Worker
(A) fallow: land (B) unaware: sleeper (C) wit: jester (D) renovated:house
Q. No. 61 – 65 Carry Two Marks Each
61. If 137+276=435 how much is 731+672?
(A) 534 (B) 1403 (C) 1623 (D)1513
62. Hari (H), Gita (G), Irfan (I) and Saira (S) are siblings (i.e. brothers and sisters).
All were born on 1st january. The age difference between any two successive
siblings (that is born one after another) is less than 3 years. Given the following
facts:
i. Hari’s age + Gita’s age > Irfan’s age + Saira’s age
ii. The age difference between Gita and Saira is 1 year. However Gita is not the
oldest and Saira is not the youngest.
iii. There are no twins.
In what order were they born (oldest first)?
(A) HSIG (B) SGHI (C) IGSH (D) IHSG
64. 5 skilled workers can build a wall in 20days: 8 semi-skilled workers can build a wall
in 25 days; 10 unskilled workers can build a wall in 30days. If a team has 2 skilled, 6
semi-skilled and 5 unskilled workers, how long will it take to build the wall?
(A) 20 (B) 18 (C) 16 (D) 15
63. Modern warfare has changed from large scale clashes of armies to suppression of
civilian populations. Chemical agents that do their work silently appear to be
suited to such warfare; and regretfully, there exist people in military
establishments who think that chemical agents are useful tools for their cause.
Which of the following statements best sums up the meaning of the above passage:
(A) Modern warfare has resulted in civil strife.
(B) Chemical agents are useful in modern warfare.
(C) Use of chemical agents in warfare would be undesirable
(D) People in military establishments like to use chemical agents in war.
65. Given digits 2,2,3,3,4,4,4,4 how many distinct 4 digit numbers greater than 3000
can be formed?
(A) 50 (B) 51 (C) 52 (D) 54

GATE 2014 for IITs and PSUs

Gate 2011 Organising Institute

Gate books for computer science students

Gate Mathematics Books collection

Exclusive courses for GATE

Correspondence Course For GATE

Gate scholarship eligibility

GATE CRASH COURSE

CSE GATE 2010

Training Center	IES Made Easy
Course Name	Exclusive courses for GATE
Category	GATE Entrance
Fees	Rs. 22500/-
Duration	Session 2008-09
Location	New Delhi, Delhi

Training Center	The Engineering Academy (TEA)
Course Name	GATE CRASH COURSE
Category	GATE Entrance
Fees
Duration	3 Months
Location	Hyderabad, Andhra Pradesh