GATE 2010 CS (CS1) – Previous Year Questions with Solutions
All 65 questions of GATE 2010 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 most appropriate word: His rather casual remarks on politics his lack of seriousness about the subject.
- Question 2 – Choose the closest meaning of circuitous.
- Question 3 – Choose the most appropriate word: If we manage to our natural resources, we would leave a better planet for our children.
- Question 4 – In a room of 25 people, 15 play hockey, 17 play football, and 10 play both. How many play neither?
- Question 5 – Choose the closest analogy to Unemployed : Worker.
- Question 6 – In an implied number base, 137+276=435. In the same base, find 731+672.
- Question 7 – Hari, Gita, Irfan and Saira are siblings, all born on January 1 in different years. Each successive age gap is less than three years. Hari and Gita…
- Question 8 – Read the passage and choose the best inference. Modern warfare has changed from clashes of large armies to suppression of civilian populations.…
- Question 9 – Five skilled workers complete a job in 20 days, eight semiskilled workers in 25 days, and ten unskilled workers in 30 days. How long will two skilled,…
- Question 10 – Using the available digits 2,2,3,3,3,4,4,4,4 without exceeding their multiplicities, how many distinct four-digit numbers greater than 3000 can be…
- Question 11 – For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different trees S,T satisfy ξ(S)=ξ(T), what follows?
- Question 12 – Newton–Raphson solves x²−13=0 starting at 3.5. What is the first iterate?
- Question 13 – How many reflexive relations exist on a five-element set?
- Question 14 – S=1,ω,ω², where ω and ω² are cube roots of unity. Under multiplication, (S,*) forms
- Question 15 – Evaluate n(1-1/n)2n.
- Question 16 – Find the minterm expansion of f(P,Q,R)=PQ+Q R+P R.
- Question 17 – A 4 MB main memory uses 1M×1-bit DRAM chips. Every chip has 1K rows of 1K cells. A refresh operation takes 100 ns. Find the time to refresh every cell…
- Question 18 – Signed 16-bit P has two’s-complement hexadecimal representation F87B. Find the representation of 8P.
- Question 19 – The shown 4:1 multiplexer has select inputs P (MSB),Q (LSB). What is f?
- Question 20 – In a binary tree with n nodes, every node has an odd number of descendants, counting itself. How many nodes have exactly one child?
- Question 21 – What is printed?
- Question 22 – Packages A,B process n=10k database records. A needs 0.0001n² time; B needs 10n 10n. Find the smallest integer k for which B is faster.
- Question 23 – Which compiler structure manages information about variables and their attributes?
- Question 24 – Which languages necessarily need heap allocation in their runtime environment?
- Question 25 – Why does an IP datagram contain a Time-to-Live field?
- Question 26 – Which is NOT a client-server application?
- Question 27 – L₁ is recursive. L₂,L₃ are recursively enumerable but nonrecursive. Which is NOT necessarily true?
- Question 28 – A B+ tree allows at most five keys per node. Find the minimum number of keys in any nonroot node.
- Question 29 – Passenger(pid,pname,age) has (0,Sachin,65),(1,Rahul,66),(2,Sourav,67),(3,Anil,69). Reservation(pid,class,tid) has…
- Question 30 – Which protocols ensure both conflict serializability and freedom from deadlock? I: Two-phase locking. II: Timestamp ordering.
- Question 31 – Modules A and B each have cyclomatic complexity ten. They are sequentially integrated as shown. What is the combined complexity?
- Question 32 – Match lifecycle activities P: requirements capture, Q: design, R: implementation, S: maintenance, with (1) module development/integration, (2) domain…
- Question 33 – Shared Boolean S1,S2 start with arbitrary values. P1 waits while S1==S2, enters its critical section, then assigns S1=S2. P2 waits while S1!=S2,…
- Question 34 – FIFO page replacement has four initially empty frames. Access one hundred distinct pages in order, then the same pages in reverse. How many faults…
- Question 35 – Which are true? I: Shortest remaining time first may cause starvation. II: Preemptive scheduling may cause starvation. III: Round robin is better than…
- Question 36 – An assembly is faulty with probability p. A test correctly identifies a faulty or nonfaulty assembly with probability q. What is the probability that…
- Question 37 – A divisor of 1099 is chosen uniformly at random. What is the probability that it is a multiple of 1096?
- Question 38 – Which sequences cannot be degree sequences of simple graphs? 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
- Question 39 – The matrix pmatrix2&3\&ypmatrix has eigenvalues 4 and 8. Find x,y.
- Question 40 – Let F(x,y,t) mean that x can fool y at time t. What does x\, y\, t\, F(x,y,t) express?
- Question 41 – Find the output of the NOR-gate network shown.
- Question 42 – Two positive-edge-triggered T flip-flops have T=1. The external clock drives flip-flop 0, whose Q₀ output clocks flip-flop 1. Starting from Q₁Q₀=00,…
- Question 43 – A pipeline has IF, ID, OF, PO and WO stages. IF, ID, OF and WO each take one cycle. PO takes one cycle for ADD/SUB, three for MUL and six for DIV.…
- Question 44 – The weight of a sequence a 0,,a n-1 is a 0+a 1/2++a n-1/2n-1. Subsequences preserve order and may delete elements. Let X be the maximum subsequence…
- Question 45 – What does this C program print?
- Question 46 – For a singly linked list with at least two nodes, fill the blank to move its last node to the front.
- Question 47 – Without spilling values to memory, what is the minimum number of registers needed for this basic block?
- Question 48 – For the grammar S→aSa bSb c, which classification holds?
- Question 49 – Which regular expression denotes all binary strings with an even number of ones?
- Question 50 – For nonnegative i,j, let L 1=\0i1j:i j\, L 2=\0i1j:i=j\, L 3=\0i1j:i=2j+1\ and L 4=\0i1j:i2j\. Which is true?
- Question 51 – Let w be any binary string of length n, and L the set of all its substrings. What is the minimum number of states in an NFA accepting L?
- Question 52 – Find the equivalent serial order for this schedule, listed from first operation to last:
- Question 53 – Relations R(A,B,C) and S(B,D,E) satisfy B→A and A→C. R has 200 tuples and S has 100. What is the maximum tuple count in R natural-join S?
- Question 54 – Choose the tests giving statement coverage of: T1: a=b=c=d. T2: a,b,c,d all distinct. T3: a=b and c≠d. T4: a≠b and c=d.
- Question 55 – Binary semaphores S0,S1,S2 start at 1,0,0. Concurrent processes execute: How many times is zero printed?
- Question 56 – There are n resources R0,…,R(n−1), each with one instance, and k processes P0,…,P(k−1). Process Pi requests resources as below, then uses and releases…
- Question 57 – 10.105.1.113 and 10.105.1.91 belong to the same IP network. Which subnet mask is NOT possible?
- Question 58 – An L1 cache has four-word blocks and 2 ns access time. L2 has sixteen-word blocks and 20 ns access time. Main memory takes 200 ns. Each connecting bus…
- Question 59 – An L1 cache has four-word blocks and 2 ns access time; L2 has sixteen-word blocks and 20 ns access time; main memory takes 200 ns. Both buses transfer…
- Question 60 – The undirected graph on vertices 0,…,4 has weight matrix W=pmatrix0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0pmatrix. Find the minimum…
- Question 61 – The undirected graph on vertices 0,…,4 has weight matrix W=pmatrix0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0pmatrix. Find the shortest…
- Question 62 – A ten-slot hash table uses h(k)=k mod 10 and linear probing. Its occupied slots are 2:42, 3:23, 4:34, 5:52, 6:46, 7:33; all others are empty. Which…
- Question 63 – A ten-slot hash table uses h(k)=k mod 10 and linear probing. Its occupied slots are 2:42, 3:23, 4:34, 5:52, 6:46, 7:33; all others are empty. How many…
- Question 64 – The network uses distance-vector routing and is initialized with direct-link costs. Wait for convergence after each change. How many links will carry…
- Question 65 – The network uses distance-vector routing and is initialized with direct-link costs. Wait for convergence after each change. First identify the unused…