The GATE Grind

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 →

  1. Question 1 (1 mark, Multiple choice) – For f(x)= x , consider P: f is continuous for all real x; Q: f is differentiable for all real x. Which is TRUE?
  2. Question 2 (1 mark, Multiple choice) – S has n elements. How many ordered pairs are in the largest and smallest equivalence relations on S respectively?
  3. Question 3 (1 mark, Multiple choice) – What maximum number of different Boolean functions involve n Boolean variables?
  4. Question 4 (1 mark, Multiple choice) – Let G be a nonplanar graph with the minimum possible number of edges. G has
  5. Question 5 (1 mark, Multiple choice) – For the shown DAG with V=1, 2, 3, 4, 5, 6, which is NOT a topological ordering?
  6. Question 6 (1 mark, Multiple choice) – Which problem is undecidable?
  7. Question 7 (1 mark, Multiple choice) – Which is TRUE?
  8. Question 8 (1 mark, Multiple choice) – How many3-to-8 decoders with an enable input construct a6-to-64 decoder without other logic gates?
  9. Question 9 (1 mark, Multiple choice) – For f(w,x,y,z)=(1,3,4,6,9,11,12,14), the function is
  10. Question 10 (1 mark, Multiple choice) – A4-way set-associative cache has128 lines, 64 words per line. CPU generates a20-bit word address. Give TAG, LINE, WORD field lengths.
  11. Question 11 (1 mark, Multiple choice) – 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.
  12. Question 12 (1 mark, Multiple choice) – Tree height is the maximum number of root-to-leaf edges. What maximum nodes can a height-h binary tree have?
  13. Question 13 (1 mark, Multiple choice) – How many different binary trees can be formed with three unlabeled nodes?
  14. Question 14 (1 mark, Multiple choice) – Which sort has lowest worst-case complexity?
  15. Question 15 (1 mark, Multiple choice) – For n>0, how many comparisons are made in this loop?
  16. Question 16 (1 mark, Multiple choice) – Match CPU scheduling algorithms P. Gang; Q. Rate monotonic; R. Fair share, with applications1. Guaranteed scheduling;2. Real-time scheduling;3. Thread…
  17. Question 17 (1 mark, Multiple choice) – Which statement about user/kernel-level threads is FALSE?
  18. Question 18 (1 mark, Multiple choice) – Which is a top-down parser?
  19. Question 19 (1 mark, Multiple choice) – With Ethernet Manchester encoding, the bit rate is
  20. Question 20 (1 mark, Multiple choice) – Which uses UDP as transport?
  21. Question 21 (2 marks, Multiple choice) – How many nonisomorphic abelian groups of order4 exist?
  22. Question 22 (2 marks, Multiple choice) – Graph(x) means x is a graph; Connected(x) means x is connected. Which does NOT express “Not every graph is connected”?
  23. Question 23 (2 marks, Multiple choice) – Which graph has an Eulerian circuit?
  24. Question 24 (2 marks, Multiple choice) – Uniformly select a permutation of1, 2, …, 20 from20! permutations. What is the probability that2 occurs before every other even number?
  25. Question 25 (2 marks, Multiple choice) – A4×4 matrix A has eigenvalues−5, −2, 1, 4. Which is an eigenvalue of pmatrixA&I\&Apmatrix, with I the4×4 identity?
  26. Question 26 (2 marks, Multiple choice) – 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…
  27. Question 27 (2 marks, Multiple choice) – 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?
  28. Question 28 (2 marks, Multiple choice) – Newton–Raphson produces x n+1=x n/2+9/(8x n), x 0=0.5. To what does it converge?
  29. Question 29 (2 marks, Multiple choice) – What is the minimum DFA size for binary strings whose number of0s is divisible by3 and number of1s divisible by5?
  30. Question 30 (2 marks, Multiple choice) – Over 0, 1, 2, L=\0i21i i0\ is
  31. Question 31 (2 marks, Multiple choice) – Which language is regular? Here wᴿ denotes reversal and + means nonempty strings.
  32. Question 32 (2 marks, Multiple choice) – 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…
  33. Question 33 (2 marks, Multiple choice) – 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.
  34. Question 34 (2 marks, Multiple choice) – Only one multiplexer and one inverter may implement any n-variable Boolean function. What minimum multiplexer size is needed?
  35. Question 35 (2 marks, Multiple choice) – 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…
  36. Question 36 (2 marks, Multiple choice) – 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;…
  37. Question 37 (2 marks, Multiple choice) – 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…
  38. Question 38 (2 marks, Multiple choice) – Evaluate postfix expression with single-digit operands using a stack: is exponentiation. What are the top two stack elements after the first *?
  39. Question 39 (2 marks, Multiple choice) – 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?
  40. Question 40 (2 marks, Multiple choice) – 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.
  41. Question 41 (2 marks, Multiple choice) – In an unweighted connected undirected graph, what most efficiently computes shortest paths from S to all other nodes?
  42. Question 42 (2 marks, Multiple choice) – What is f(5)?
  43. Question 43 (2 marks, Multiple choice) – 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.
  44. Question 44 (2 marks, Multiple choice) – Let n≥m. How many recursive calls does this C function make?
  45. Question 45 (2 marks, Multiple choice) – Find the time complexity.
  46. Question 46 (2 marks, Multiple choice) – CellNode is a binary-tree node. What does GetValue(root) return?
  47. Question 47 (2 marks, Multiple choice) – 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?
  48. Question 48 (2 marks, Multiple choice) – Which is TRUE of conjunctive-normal-form formulae?
  49. Question 49 (2 marks, Multiple choice) – In a connected undirected graph, w is the minimum edge weight and e is a specific edge of weight w. Which statement is FALSE?
  50. Question 50 (2 marks, Multiple choice) – An array has an even number n of elements. To find both its minimum and maximum, which comparison-count statement is TRUE?
  51. Question 51 (2 marks, Multiple choice) – Let T(n) count loop executions in this C code. Which is TRUE?
  52. Question 52 (2 marks, Multiple choice) – 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)?
  53. Question 53 (2 marks, Multiple choice) – P: Every regular grammar is LL(1). Q: Every regular set has an LR(1) grammar. Which is TRUE?
  54. Question 54 (2 marks, Multiple choice) – 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…
  55. Question 55 (2 marks, Multiple choice) – 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…
  56. Question 56 (2 marks, Multiple choice) – Fixed-frame virtual memory uses FIFO replacement. P: increasing frames sometimes increases fault rate. Q: some programs do not exhibit locality. Which…
  57. Question 57 (2 marks, Multiple choice) – Three processes share5 units each of resources X, Y, Z. alloc gives held resources; request gives further resources to finish. Which finishes LAST?…
  58. Question 58 (2 marks, Multiple choice) – Two processes share wants1, wants2, initially false, and use the following construct. Which is TRUE?
  59. Question 59 (2 marks, Multiple choice) – Relations studInfo(studId, name, sex), key studId, and enroll(studId, courseId), key(studId, courseId), record students and courses. Every course has…
  60. Question 60 (2 marks, Multiple choice) – employee(name, sex, supervisorName) has key name; supervisorName names an immediate supervisor. What does \e.name employee(e) x[ employee(x)…
  61. Question 61 (2 marks, Multiple choice) – employee(empId, name, department, salary) has more than one employee in department5. We want employees paid more than anyone in department5. Which is…
  62. Question 62 (2 marks, Multiple choice) – Which statement is FALSE?
  63. Question 63 (2 marks, Multiple choice) – 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…
  64. Question 64 (2 marks, Multiple choice) – 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)
  65. Question 65 (2 marks, Multiple choice) – In a slotted LAN with n stations, each independently transmits with probability p in a time slot. What is the probability exactly one station…
  66. Question 66 (2 marks, Multiple choice) – A token ring transmits at 107 bps; propagation speed is200 metres/μs. One-bit delay equals which cable length?
  67. Question 67 (2 marks, Multiple choice) – A class-B host address is split into subnets using a6-bit subnet number. Give maximum subnets and hosts per subnet.
  68. Question 68 (2 marks, Multiple choice) – Protect message11001001 with CRC polynomial x3+1. What message is transmitted?
  69. Question 69 (2 marks, Multiple choice) – 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…
  70. Question 70 (2 marks, Multiple choice) – Match protocols P.SMTP, Q.BGP, R.TCP, S.PPP with layers1.Application, 2.Transport, 3.Data link, 4.Network, 5.Physical.
  71. Question 71 (2 marks, Multiple choice) – 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]…
  72. Question 72 (2 marks, Multiple choice) – 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]…
  73. Question 73 (2 marks, Multiple choice) – 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]…
  74. Question 74 (2 marks, Multiple choice) – Which regular expression gives the language of the automaton shown?
  75. Question 75 (2 marks, Multiple choice) – How many states does the minimum automaton equivalent to the shown FSA have?
  76. Question 76 (2 marks, Multiple choice) – 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?
  77. Question 77 (2 marks, Multiple choice) – 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…
  78. Question 78 (2 marks, Multiple choice) – 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?
  79. Question 79 (2 marks, Multiple choice) – 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…
  80. Question 80 (2 marks, Multiple choice) – 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…
  81. Question 81 (2 marks, Multiple choice) – 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…
  82. Question 82 (2 marks, Multiple choice) – 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?
  83. Question 83 (2 marks, Multiple choice) – 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…
  84. Question 84 (2 marks, Multiple choice) – 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)?
  85. Question 85 (2 marks, Multiple choice) – 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…