http://www.questionpapers.net.in/Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 1 of 11 GATE Computer Science and Engineering Question Paper 2010 Q. No. 1 – 25 Carry One Mark Each 1. Let G = (V, E) be a graph. Define (G) = d id 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| = 2 |T| (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 n 2 lim n n1 1 ? (A) 0 (B) e-2 (C) e-1/2 (D) 1 6. The minterm expansion of f (P, Q, R) = R P R Q PQ is (A) m2 + m4 + m6 + m7 (B) m0 +m1 + m3 + m5 (C) m0 +m1 + m6 + m7 (D) m2 + m3 + m4 + m5 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) (C3D8)16 (B) (187B)16 (C) (F878)16 (D) (987B)1 9. The Boolean expression for the output f of the multiplexer shown below is (A) R Q P (B) P Q R (D) R Q P (C) P + Q + R f P Q RRRRhttp://www.questionpapers.net.in/Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 2 of 11 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); print 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 http://www.questionpapers.net.in/Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 3 of 11 19. A relational schema for a train reservation database is given below Passenger (pid, pname, age) Re servation (pid, cass, tid) Table: Passenger 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 pid ‘pname Age 0 ‘Sachin’ 65 1 ‘Rahul’ 66 2 ‘Sourav’ 67 3 ‘Anil’ 69 A B BAhttp://www.questionpapers.net.in/Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 4 of 11 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) ; while (S1 != S2) ; Critica1 Section Critica1 section S1 = S2; 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) 96 (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 http://www.questionpapers.net.in/Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 5 of 11 29. Consider the following matrix A = y x 3 2 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 xyt(¬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) R Q (B) Q P (C) R P (D) R Q P 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 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? P QQR P R QR f T Q 1 0 Q Q T Q 1 Clockhttp://www.questionpapers.net.in/Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 6 of 11 I nstruction Meaning of instruction I0 :MUL R2 ,R0 ,R1 R2 R0 *R1 I1 :DIV R5 ,R3 ,R4 R5 R3 /R4 I2 : ADD R2 ,R5 ,R2 R2 R5 + R2 I3 :SUB R5 ,R2 ,R6 R5 R2 R6 (A) 13 (B) 15 (C) 17 (D) 19 34. The weight of a sequence a0, a1,…, an-1 of real numbers is defined as a0 + a1 /2 +…+ aa-1/2n-1. 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 a 0, a1,…, an-1. Then X is equal to (A) max(Y, a0 + Y) (B) max(Y, a0 +Y/2) (C) max(Y, a0 +2Y) (D) a0 + 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; http://www.questionpapers.net.in/Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 7 of 11 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 http://www. ues n a er net. n/q tio p p s. i Published by: www.questionpapers.net.in Question Papers: GATE Computer Science and Engineering 2010 Page 8 of 11 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 P i. is as follows: if (i% 2==0) { if (i 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 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. 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 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 End of Question Papers