GATE 2013 CS (CS1) – Previous Year Questions with Solutions
All 65 questions of GATE 2013 CS (CS1) with answers and explanations. Read each question, then practise it by topic or as a full paper.
Practise this paper in The GATE Grind →
- Question 1 – Choose the closest meaning of “nadir”.
- Question 2 – Universalism is to particularism as diffuseness is to .
- Question 3 – What is the maximum sum of the sequence 44,42,40,…?
- Question 4 – Were you a bird, you in the sky.
- Question 5 – Choose the grammatically incorrect sentence.
- Question 6 – Find 11+2+12+3+13+4++180+81.
- Question 7 – A two-digit integer is chosen uniformly from all two-digit integers between 1 and 100. What is the probability it is not divisible by seven?
- Question 8 – After several defeats in wars, Robert Bruce went in exile and wanted to commit suicide. Just before committing suicide, he came across a spider…
- Question 9 – A tourist travels half the journey by train at 60 km/h, half the remainder by bus at 30 km/h, and the rest by cycle at 10 km/h. Find average speed in…
- Question 10 – Current erection cost of a structure is ₹13200. Daily labour wages rise by one fifth of current wages and working hours decrease by one twenty-fourth…
- Question 11 – On the integers define x y=x2+y2. Which property holds?
- Question 12 – Cars per minute at a junction between 5 PM and 6 PM follow a Poisson distribution with mean three. Find the probability of fewer than three cars in a…
- Question 13 – Which determinant does NOT equal vmatrix1&x&x2\\1&y&y2\\1&z&z2vmatrix?
- Question 14 – Find the smallest integer representable in eight-bit two’s complement.
- Question 15 – Inputs D₀,D₁,D₂,D₃ and outputs X₀,X₁,V have rows: 0000→xx0; 1000→001; x100→011; xx10→101; xxx1→111. x is don’t-care, and V=1 iff input is valid. What…
- Question 16 – What is the tightest upper bound on swaps used by selection sort on n numbers?
- Question 17 – What is the tightest worst-case upper bound for inserting into a binary search tree with n nodes?
- Question 18 – L₁=∅ and L₂=a. Evaluate L 1L 2* L 1*.
- Question 19 – A grammar has no ε-productions or unit productions (the source gives types A→ε and A→a). What is the maximum number of bottom-up reduce moves when…
- Question 20 – Priorities are proportional to process waiting times and start at zero. Every T time units the scheduler reevaluates priorities and selects the next…
- Question 21 – Match P: service-oriented computing, Q: heterogeneous communicating systems, R: information representation, S: process description to (1)…
- Question 22 – Which transport protocols are used respectively for real-time multimedia, file transfer, DNS and email?
- Question 23 – X signs message M, encrypts the message/signature pair and sends it to Y. Which key order is used to sign/encrypt and then decrypt/verify?
- Question 24 – S and D communicate through two intermediate routers. How many network-layer and data-link-layer visits occur per packet?
- Question 25 – An index is clustered if
- Question 26 – Binary semaphores a,b,c,d start at one. X needs a,b,c; Y needs b,c,d; Z needs c,d,a, releasing all after its code. Which acquisition order is…
- Question 27 – Which are false? 1: Every nondeterministic TM has an equivalent deterministic TM. 2: TM-recognizable languages are closed under union and complement.…
- Question 28 – Which are true? 1: Undirected cycle detection is in P. 2: Undirected cycle detection is in NP. 3: Every NP-complete problem has a nondeterministic…
- Question 29 – What is Bellman–Ford’s running time on a complete graph with n vertices?
- Question 30 – A k-way cache has v sets of k consecutive lines, with set s preceding s+1. Memory blocks are numbered from zero. To which line range can block j map?
- Question 31 – Which does NOT represent XNOR of x,y?
- Question 32 – Which function is continuous at x=3?
- Question 33 – At x=0,0.3,0.6,0.9,1.2,1.5,1.8,2.1,2.4,2.7,3.0 the values of f are 0,0.09,0.36,0.81,1.44,2.25,3.24,4.41,5.76,7.29,9.00. Approximate its integral from…
- Question 34 – An undirected random graph has eight vertices, each possible edge independently present with probability one half. Find the expected number of…
- Question 35 – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all vertex degrees is even. Which hold?
- Question 36 – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G edges share an endpoint. Which are always true? P: A cycle’s…
- Question 37 – With F(x)=“x is my friend” and P(x)=“x is perfect”, translate “None of my friends are perfect”.
- Question 38 – Micro-operations are MBR←PC; MAR←X; PC←Y; Memory←MBR. Which operation can they implement?
- Question 39 – A disk has sixteen surfaces, 16384 cylinders and 64 sectors per surface in a cylinder, with 512 bytes per sector. Address order is…
- Question 40 – How many elements can heap sort sort in ( n) time?
- Question 41 – What is the asymptotic return value, rather than running time?
- Question 42 – L 1=\0p1q0r:p,q,r0\ and L 2=\0p1q0r:p,q,r0,p r\. Which statement is false?
- Question 43 – For the shown DFA A, which are false? 1: Its language complement is context-free. 2: L(A)=L((11*0+0)(0+1)*0*1*). 3: A is minimal. 4: A accepts all…
- Question 44 – x initially zero is shared by W,X,Y,Z. Each process waits on counting semaphore S=2, reads x, computes and stores its update, signals S and…
- Question 45 – Schemas: Students(rollno,sname), Courses(courseno,cname), Registration(rollno,courseno,percent). Which queries give distinct student names scoring >90…
- Question 46 – An Ethernet LAN sends 10000-bit frames at 500 Mb/s. Signals travel at 200000 km/s. Find maximum cable length in km for collision detection.
- Question 47 – An IPv4 datagram has M=0, HLEN=10, total length 400 and fragment offset 300. Identify fragment position and zero-based first/last payload-byte…
- Question 48 – Filled circles in the shown access graphs are methods, unfilled circles attributes. Move method m from M₁ to M₂ while keeping attributes fixed. What…
- Question 49 – X computes a[i]=f(i), then ExitX(R,S), for i=0,…,n−1. Y calls EntryY(R,S), then computes b[i]=g(a[i]), for each i. R,S are binary semaphores initially…
- Question 50 – Two LR(1) item sets share core X→c·X, X→·cX, X→·d. Their lookaheads are respectively c,d and end-marker. Which claims about their LALR merge are…
- Question 51 – Which problems are undecidable? 1: Given CFG G, is L(G)=∅? 2: Given CFG G, is L(G)=Σ*? 3: Given TM M, is L(M) regular? 4: Given DFA A and NFA N, is…
- Question 52 – p starts at five. Find f(p,p). The first parameter is passed by reference and the second by value.
- Question 53 – A BST has preorder 30,20,10,15,25,23,39,35,42. Find its postorder.
- Question 54 – Along with Enqueue/Dequeue, a queue supports MultiDequeue(Q), which sets m=k and repeatedly Dequeues while Q is nonempty and m>0, decrementing m. For…
- Question 55 – A pipeline has FI,DI,FO,EI,WO stage delays 5,7,10,8,6 ns, with one-ns buffers after stages and no branch prediction. A twelve-instruction program has…
- Question 56 – A RAM chip stores 1024 eight-bit words. How many 2-to-4 decoders with enable are needed to build 16K×16 RAM from 1K×8 chips?
- Question 57 – Which formula is NOT equivalent to x( y\, z\,)?
- Question 58 – A processor permits register operands only, at most two sources and one destination per instruction. All variables are dead after this segment. Only…
- Question 59 – For the same register-only architecture and complete segment below, apply register allocation only, with no code motion. Find minimum registers to…
- Question 60 – A has length five; oldc,newc each have length three. The intended operation replaces each original A character at most once using the corresponding…
- Question 61 – A has length five; oldc,newc each have length three. The intended operation replaces each original A character at most once using the corresponding…
- Question 62 – Virtual addresses are 46 bits, physical addresses 32 bits. A three-level page table has one-page T₁, entries of T₁ pointing to T₂ pages and T₂ entries…
- Question 63 – Virtual addresses are 46 bits, physical addresses 32 bits. A three-level page table has one-page T₁, entries of T₁ pointing to T₂ pages and T₂ entries…
- Question 64 – R(A,B,C,D,E,F,G,H) has atomic fields. Exactly the dependencies implied by F=CH→G,A→BC,B→CFH,E→A,F→EG hold. How many candidate keys exist?
- Question 65 – R(A,B,C,D,E,F,G,H) has atomic fields. Exactly the dependencies implied by F=CH→G,A→BC,B→CFH,E→A,F→EG hold. What is the highest normal-form description…