Page 1 CS? GATE Paper 2010 Q. No. 1 â€“ 25 Carry One Mark Each 1. Let G=(V, E) be a graph. Define ( ) d d ? G i d = × ? , where i d 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 2 x 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) 2 10 (B) 2 15 (C) 2 20 (D) 2 25 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 2n n 1 lim 1 ? n ?8 ? ? - ? ? ? ? (A) 0 (B) e -2 (C) e -1/2 (D) 1 6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + (A) 2 4 6 7 m m m m + + + (B) 0 1 3 5 m m m m + + + (C) 0 1 6 7 m m m m + + + (D) 2 3 4 5 m m m m + + + 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*2 10 nanoseconds (C) 100*2 20 nanoseconds (D) 3200*2 20 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) ( ) 16 C3D8 (B) ( ) 16 187B (C) ( ) 16 F878 (D) ( ) 16 987B Page 2 CS? GATE Paper 2010 Q. No. 1 â€“ 25 Carry One Mark Each 1. Let G=(V, E) be a graph. Define ( ) d d ? G i d = × ? , where i d 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 2 x 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) 2 10 (B) 2 15 (C) 2 20 (D) 2 25 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 2n n 1 lim 1 ? n ?8 ? ? - ? ? ? ? (A) 0 (B) e -2 (C) e -1/2 (D) 1 6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + (A) 2 4 6 7 m m m m + + + (B) 0 1 3 5 m m m m + + + (C) 0 1 6 7 m m m m + + + (D) 2 3 4 5 m m m m + + + 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*2 10 nanoseconds (C) 100*2 20 nanoseconds (D) 3200*2 20 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) ( ) 16 C3D8 (B) ( ) 16 187B (C) ( ) 16 F878 (D) ( ) 16 987B CS? GATE Paper 2010 9. The Boolean expression for the output f of the multiplexer shown below is (A) P Q R ? ? (B) P Q R ? ? (C) P Q R + + (D) P Q R + + 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 10 k records. Package A requires 0.0001n 2 time units and package B requires 10nlog 10 n 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 f P Q R R R R Page 3 CS? GATE Paper 2010 Q. No. 1 â€“ 25 Carry One Mark Each 1. Let G=(V, E) be a graph. Define ( ) d d ? G i d = × ? , where i d 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 2 x 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) 2 10 (B) 2 15 (C) 2 20 (D) 2 25 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 2n n 1 lim 1 ? n ?8 ? ? - ? ? ? ? (A) 0 (B) e -2 (C) e -1/2 (D) 1 6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + (A) 2 4 6 7 m m m m + + + (B) 0 1 3 5 m m m m + + + (C) 0 1 6 7 m m m m + + + (D) 2 3 4 5 m m m m + + + 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*2 10 nanoseconds (C) 100*2 20 nanoseconds (D) 3200*2 20 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) ( ) 16 C3D8 (B) ( ) 16 187B (C) ( ) 16 F878 (D) ( ) 16 987B CS? GATE Paper 2010 9. The Boolean expression for the output f of the multiplexer shown below is (A) P Q R ? ? (B) P Q R ? ? (C) P Q R + + (D) P Q R + + 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 10 k records. Package A requires 0.0001n 2 time units and package B requires 10nlog 10 n 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 f P Q R R R R CS? GATE Paper 2010 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 n 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 19. A relational schema for a train reservation database is given below ( ) ( ) Passenger pid, pname, age Reservation pid, cass, tid Table :Passenger pid 'pname Age 0 'Sachin' 65 1 'Rahul' 66 2 'Sourav' 67 3 'Anil' 69 Table :Reservation pid class tid 0 'AC' 8200 1 'AC' 8201 2 'SC' 8201 5 'AC' 8203 1 'SC' 8204 3 'AC' 8202 Page 4 CS? GATE Paper 2010 Q. No. 1 â€“ 25 Carry One Mark Each 1. Let G=(V, E) be a graph. Define ( ) d d ? G i d = × ? , where i d 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 2 x 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) 2 10 (B) 2 15 (C) 2 20 (D) 2 25 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 2n n 1 lim 1 ? n ?8 ? ? - ? ? ? ? (A) 0 (B) e -2 (C) e -1/2 (D) 1 6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + (A) 2 4 6 7 m m m m + + + (B) 0 1 3 5 m m m m + + + (C) 0 1 6 7 m m m m + + + (D) 2 3 4 5 m m m m + + + 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*2 10 nanoseconds (C) 100*2 20 nanoseconds (D) 3200*2 20 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) ( ) 16 C3D8 (B) ( ) 16 187B (C) ( ) 16 F878 (D) ( ) 16 987B CS? GATE Paper 2010 9. The Boolean expression for the output f of the multiplexer shown below is (A) P Q R ? ? (B) P Q R ? ? (C) P Q R + + (D) P Q R + + 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 10 k records. Package A requires 0.0001n 2 time units and package B requires 10nlog 10 n 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 f P Q R R R R CS? GATE Paper 2010 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 n 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 19. A relational schema for a train reservation database is given below ( ) ( ) Passenger pid, pname, age Reservation pid, cass, tid Table :Passenger pid 'pname Age 0 'Sachin' 65 1 'Rahul' 66 2 'Sourav' 67 3 'Anil' 69 Table :Reservation pid class tid 0 'AC' 8200 1 'AC' 8201 2 'SC' 8201 5 'AC' 8203 1 'SC' 8204 3 'AC' 8202 CS? GATE Paper 2010 What pids are returned by the following SQL query for the above instance of the tables? SELECT pid FROM Reservation 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 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 A B B A Page 5 CS? GATE Paper 2010 Q. No. 1 â€“ 25 Carry One Mark Each 1. Let G=(V, E) be a graph. Define ( ) d d ? G i d = × ? , where i d 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 2 x 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) 2 10 (B) 2 15 (C) 2 20 (D) 2 25 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 2n n 1 lim 1 ? n ?8 ? ? - ? ? ? ? (A) 0 (B) e -2 (C) e -1/2 (D) 1 6. The minterm expansion of f (P, Q, R) PQ QR PR is = + + (A) 2 4 6 7 m m m m + + + (B) 0 1 3 5 m m m m + + + (C) 0 1 6 7 m m m m + + + (D) 2 3 4 5 m m m m + + + 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*2 10 nanoseconds (C) 100*2 20 nanoseconds (D) 3200*2 20 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) ( ) 16 C3D8 (B) ( ) 16 187B (C) ( ) 16 F878 (D) ( ) 16 987B CS? GATE Paper 2010 9. The Boolean expression for the output f of the multiplexer shown below is (A) P Q R ? ? (B) P Q R ? ? (C) P Q R + + (D) P Q R + + 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 10 k records. Package A requires 0.0001n 2 time units and package B requires 10nlog 10 n 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 f P Q R R R R CS? GATE Paper 2010 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 n 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 19. A relational schema for a train reservation database is given below ( ) ( ) Passenger pid, pname, age Reservation pid, cass, tid Table :Passenger pid 'pname Age 0 'Sachin' 65 1 'Rahul' 66 2 'Sourav' 67 3 'Anil' 69 Table :Reservation pid class tid 0 'AC' 8200 1 'AC' 8201 2 'SC' 8201 5 'AC' 8203 1 'SC' 8204 3 'AC' 8202 CS? GATE Paper 2010 What pids are returned by the following SQL query for the above instance of the tables? SELECT pid FROM Reservation 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 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 A B B A CS? GATE Paper 2010 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) ; Critica1 Section S1 = S2; while (S1 != S2) ; Critica1 Section 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) 196 (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 â€“ 55 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 10 99 is a multiple of 10 96 ? (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, 2Read More

131 docs|169 tests