GATE 2007 CS – Previous Year Questions with Solutions
All 85 questions of GATE 2007 CS with answers and explanations. Read each question, then practise it by topic or as a full paper.
85 questions worth 150 marks in all (20 1-mark, 65 2-mark). Subjects covered: Engineering Mathematics (14), Algorithms (12), Theory of Computation (9), Operating System (9), Digital Logic (8), Programming and Data Structures (8), Computer Networks (8), Computer Organization and Architecture (7).
Practise this paper in The GATE Grind →
- Question 1 – For f(x)= x , consider P: f is continuous for all real x; Q: f is differentiable for all real x. Which is TRUE?
- Question 2 – S has n elements. How many ordered pairs are in the largest and smallest equivalence relations on S respectively?
- Question 3 – What maximum number of different Boolean functions involve n Boolean variables?
- Question 4 – Let G be a nonplanar graph with the minimum possible number of edges. G has
- Question 5 – For the shown DAG with V=1, 2, 3, 4, 5, 6, which is NOT a topological ordering?
- Question 6 – Which problem is undecidable?
- Question 7 – Which is TRUE?
- Question 8 – How many3-to-8 decoders with an enable input construct a6-to-64 decoder without other logic gates?
- Question 9 – For f(w,x,y,z)=(1,3,4,6,9,11,12,14), the function is
- Question 10 – A4-way set-associative cache has128 lines, 64 words per line. CPU generates a20-bit word address. Give TAG, LINE, WORD field lengths.
- Question 11 – A disk pack has16 surfaces, 128 tracks per surface, 256 sectors per track, 512 bytes per sector. Give capacity and bits to identify a sector.
- Question 12 – Tree height is the maximum number of root-to-leaf edges. What maximum nodes can a height-h binary tree have?
- Question 13 – How many different binary trees can be formed with three unlabeled nodes?
- Question 14 – Which sort has lowest worst-case complexity?
- Question 15 – For n>0, how many comparisons are made in this loop?
- Question 16 – Match CPU scheduling algorithms P. Gang; Q. Rate monotonic; R. Fair share, with applications1. Guaranteed scheduling;2. Real-time scheduling;3. Thread…
- Question 17 – Which statement about user/kernel-level threads is FALSE?
- Question 18 – Which is a top-down parser?
- Question 19 – With Ethernet Manchester encoding, the bit rate is
- Question 20 – Which uses UDP as transport?
- Question 21 – How many nonisomorphic abelian groups of order4 exist?
- Question 22 – Graph(x) means x is a graph; Connected(x) means x is connected. Which does NOT express “Not every graph is connected”?
- Question 23 – Which graph has an Eulerian circuit?
- Question 24 – Uniformly select a permutation of1, 2, …, 20 from20! permutations. What is the probability that2 occurs before every other even number?
- Question 25 – A4×4 matrix A has eigenvalues−5, −2, 1, 4. Which is an eigenvalue of pmatrixA&I\&Apmatrix, with I the4×4 identity?
- Question 26 – Partitions of S=a, b, c, d are π1=a, b, c, d, π2=a, b, c, d, π3=a, b, c, d, π4=a, b, c, d. Define πi≺πj iff πi refines πj. Which shown poset diagram…
- Question 27 – Let X=\x R3 x 1+x 2+x 3=0\ for column vectors x=[x 1,x 2,x 3]T. Which is TRUE?
- Question 28 – Newton–Raphson produces x n+1=x n/2+9/(8x n), x 0=0.5. To what does it converge?
- Question 29 – What is the minimum DFA size for binary strings whose number of0s is divisible by3 and number of1s divisible by5?
- Question 30 – Over 0, 1, 2, L=\0i21i i0\ is
- Question 31 – Which language is regular? Here wᴿ denotes reversal and + means nonempty strings.
- Question 32 – Let f(w,x,y,z)=(0,4,5,7,8,9,13,15). Which expressions are NOT equivalent to f? P. x y z+w xy+wy z+xz Q. w y z+wx y+xz R. w y z+wx y+xyz+xy z S. x y…
- Question 33 – Define X*Y=XY+X Y. Let Z=X*Y. Which are valid? P: X=Y*Z; Q: Y=X*Z; R: X*Y*Z=1.
- Question 34 – Only one multiplexer and one inverter may implement any n-variable Boolean function. What minimum multiplexer size is needed?
- Question 35 – For carry lookahead, P i=A i B i, G i=A iB i, S i=P i C i, C i+1=G i+P iC i; C0 is input carry. Assume all Pi, Gi are available and unlimited-fan-in…
- Question 36 – A4-bit counter has controls: Clear=1→clear0 (other inputs irrelevant); Clear=0, Load=0, Count=0→no change; Clear=0, rising clock, Load=1→load input;…
- Question 37 – A pipeline has IF, ID (decode/operand fetch), EX, WB. IF, ID, WB take1 cycle; ADD/SUB EX takes1, MUL EX takes3. Operand forwarding is available. How…
- Question 38 – Evaluate postfix expression with single-digit operands using a stack: is exponentiation. What are the top two stack elements after the first *?
- Question 39 – A binary tree has inorder d b e a f c g and preorder a b d e c f g. What is its postorder?
- Question 40 – An empty size7 hash table starts at index0, h(x)=(3x+4) mod7. Insert1, 3, 8, 10 with closed hashing. Which table results? “empty” means unused.
- Question 41 – In an unweighted connected undirected graph, what most efficiently computes shortest paths from S to all other nodes?
- Question 42 – What is f(5)?
- Question 43 – A complete n-ary tree has either n children or none at each node. It has I internal nodes and L leaves. If L=41, I=10, find n.
- Question 44 – Let n≥m. How many recursive calls does this C function make?
- Question 45 – Find the time complexity.
- Question 46 – CellNode is a binary-tree node. What does GetValue(root) return?
- Question 47 – A max-heap is an array. To insert a new element, binary search the path from new leaf to root for its position. How many comparisons are performed?
- Question 48 – Which is TRUE of conjunctive-normal-form formulae?
- Question 49 – In a connected undirected graph, w is the minimum edge weight and e is a specific edge of weight w. Which statement is FALSE?
- Question 50 – An array has an even number n of elements. To find both its minimum and maximum, which comparison-count statement is TRUE?
- Question 51 – Let T(n) count loop executions in this C code. Which is TRUE?
- Question 52 – Grammar has N=S, C, S1, T=a, b, i, t, e, start S, rules S iCtSS 1 a, S 1 eS, C b. Why is it NOT LL(1)?
- Question 53 – P: Every regular grammar is LL(1). Q: Every regular set has an LR(1) grammar. Which is TRUE?
- Question 54 – A simplified computer has2 registers. OP Rj, Ri computes Rj OP Ri into Ri; OP m, Ri computes memory[m] OP Ri into Ri. OP is ADD/SUB. MOV m, Ri loads…
- Question 55 – Under shortest-remaining-time-first scheduling, what is total waiting time of P2? Process Execution time Arrival time --- --- --- P1 20 0 P2 25 15 P3…
- Question 56 – Fixed-frame virtual memory uses FIFO replacement. P: increasing frames sometimes increases fault rate. Q: some programs do not exhibit locality. Which…
- Question 57 – Three processes share5 units each of resources X, Y, Z. alloc gives held resources; request gives further resources to finish. Which finishes LAST?…
- Question 58 – Two processes share wants1, wants2, initially false, and use the following construct. Which is TRUE?
- Question 59 – Relations studInfo(studId, name, sex), key studId, and enroll(studId, courseId), key(studId, courseId), record students and courses. Every course has…
- Question 60 – employee(name, sex, supervisorName) has key name; supervisorName names an immediate supervisor. What does \e.name employee(e) x[ employee(x)…
- Question 61 – employee(empId, name, department, salary) has more than one employee in department5. We want employees paid more than anyone in department5. Which is…
- Question 62 – Which statement is FALSE?
- Question 63 – A B+ leaf’s order is its maximum number of(value, data-record-pointer) pairs. Block size1 KB; record pointer7 bytes; value9 bytes; block pointer6…
- Question 64 – Which is TRUE about these schedules? S1: r1(X);r1(Y);r2(X);r2(Y);w2(Y);w1(X) S2: r1(X);r2(X);r2(Y);w2(Y);r1(Y);w1(X)
- Question 65 – In a slotted LAN with n stations, each independently transmits with probability p in a time slot. What is the probability exactly one station…
- Question 66 – A token ring transmits at 107 bps; propagation speed is200 metres/μs. One-bit delay equals which cable length?
- Question 67 – A class-B host address is split into subnets using a6-bit subnet number. Give maximum subnets and hosts per subnet.
- Question 68 – Protect message11001001 with CRC polynomial x3+1. What message is transmitted?
- Question 69 – Stations M, N are L kilometres apart. Frames contain K bits; propagation delay is t seconds/km and channel rate R bits/s. Neglect processing. What…
- Question 70 – Match protocols P.SMTP, Q.BGP, R.TCP, S.PPP with layers1.Application, 2.Transport, 3.Data link, 4.Network, 5.Physical.
- Question 71 – R1, R2, R3 are general-purpose registers. Program below is loaded at memory1000; instruction word counts shown. M[3000]=10, R3=2000; each M[2000]…
- Question 72 – R1, R2, R3 are general-purpose registers. Program below is loaded at memory1000; instruction word counts shown. M[3000]=10, R3=2000; each M[2000]…
- Question 73 – R1, R2, R3 are general-purpose registers. Program below is loaded at memory1000; instruction word counts shown. M[3000]=10, R3=2000; each M[2000]…
- Question 74 – Which regular expression gives the language of the automaton shown?
- Question 75 – How many states does the minimum automaton equivalent to the shown FSA have?
- Question 76 – Letters a, b, c, d, e, f have probabilities1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which list is their Huffman code in that order?
- Question 77 – Letters a, b, c, d, e, f have probabilities1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of the code in the correct answer…
- Question 78 – CFG has nonterminals S, A, B, terminals a, b, start S, rules S aB bA, B b bS aBB, A a aS bAA. Which string is generated?
- Question 79 – CFG has nonterminals S, A, B, terminals a, b, start S, rules S aB bA, B b bS aBB, A a aS bAA. For the correct string in Q78, how many derivation trees…
- Question 80 – A byte-addressable machine has 216 bytes main memory and a direct-mapped data cache with32 lines of64 bytes each, initially empty. A50×50 byte array…
- Question 81 – A byte-addressable machine has 216 bytes main memory and a direct-mapped data cache with32 lines of64 bytes each, initially empty. A50×50 byte array…
- Question 82 – A process has3 page frames, initially empty, and reference string1, 2, 1, 3, 7, 4, 5, 6, 3, 1. How many page faults occur under optimal replacement?
- Question 83 – A process has3 page frames, initially empty, and reference string1, 2, 1, 3, 7, 4, 5, 6, 3, 1. How many more page faults occur under LRU than under…
- Question 84 – A robot starts on the Cartesian plane. At each step (i, j) it moves either to(i+1, j) or(i, j+1). How many paths reach(10, 10) from(0, 0)?
- Question 85 – A robot starts on the Cartesian plane. At each step (i, j) it moves either to(i+1, j) or(i, j+1). It may not traverse the segment(4, 4)→(5, 4). How…