Page 1 GATE CS - 2001 SECTION - A 1. This question consists of TWENTY-FIVE sub-questions (1.1 â€“ 1.25) of ONE mark each. For each of these sub-questions, four possible alternatives, A, B, C and D are provided. Choose the most appropriate alternative and darken its bubble on the Objective Response Sheet (ORS) against the corresponding sub-question number using a soft HB pencil. Do not darken more than one bubble for any sub-question. Do not use the ORS for any rough work. You may use the answer book for any rough work, if needed. 1.1 Consider the following statements: S1: The sum of two singular n × n matrices may be non-singular S2: The sum of two n × n non-singular matrices may be singular. Which of the following statements is correct? (a) S1 and S2 are both true (b) S1 is true, S2 is false (c) S1 is false, S2 is true (d) S1 and S2 are both false 1.2 Consider the following relations: R1 (a,b) iff (a+b) is even over the set of integers R2 (a,b) iff (a+b) is odd over the set of integers R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers R4 (a,b) iff |a â€“ b| = 2 over the set of natural numbers Which of the following statements is correct? (a) R1 and R2 are equivalence relations, R3 and R4 are not (b) R1 and R3 are equivalence relations, R2 and R4 are not (c) R1 and R4 are equivalence relations, R2 and R3 are not (d) R1, R2, R3 and R4 are all equivalence relations 1.3 Consider two well-formed formulas in prepositional logic F1: P ? ¬P F2: (P?¬P)?(¬P?P) Which of the following statements is correct? (a) F1 is satisfiable, F2 is valid (b) F1 unsatisfiable, F2 is satisfiable (c) F1 is unsatisfiable, F2 is valid (d) F1 and F2 are both satisfiable 1.4 consider the following two statements: S1: { } 2 0 1 n n = is a regular language S2: { } 0 1 0 1 and 1 m n m n m n + = = is a regular language Which of the following statements is correct? (a) Only S1 is correct (b) Only S2 is correct (c) Both S1 and S2 are correct (d) None of S1 and S2 is correct Page 2 GATE CS - 2001 SECTION - A 1. This question consists of TWENTY-FIVE sub-questions (1.1 â€“ 1.25) of ONE mark each. For each of these sub-questions, four possible alternatives, A, B, C and D are provided. Choose the most appropriate alternative and darken its bubble on the Objective Response Sheet (ORS) against the corresponding sub-question number using a soft HB pencil. Do not darken more than one bubble for any sub-question. Do not use the ORS for any rough work. You may use the answer book for any rough work, if needed. 1.1 Consider the following statements: S1: The sum of two singular n × n matrices may be non-singular S2: The sum of two n × n non-singular matrices may be singular. Which of the following statements is correct? (a) S1 and S2 are both true (b) S1 is true, S2 is false (c) S1 is false, S2 is true (d) S1 and S2 are both false 1.2 Consider the following relations: R1 (a,b) iff (a+b) is even over the set of integers R2 (a,b) iff (a+b) is odd over the set of integers R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers R4 (a,b) iff |a â€“ b| = 2 over the set of natural numbers Which of the following statements is correct? (a) R1 and R2 are equivalence relations, R3 and R4 are not (b) R1 and R3 are equivalence relations, R2 and R4 are not (c) R1 and R4 are equivalence relations, R2 and R3 are not (d) R1, R2, R3 and R4 are all equivalence relations 1.3 Consider two well-formed formulas in prepositional logic F1: P ? ¬P F2: (P?¬P)?(¬P?P) Which of the following statements is correct? (a) F1 is satisfiable, F2 is valid (b) F1 unsatisfiable, F2 is satisfiable (c) F1 is unsatisfiable, F2 is valid (d) F1 and F2 are both satisfiable 1.4 consider the following two statements: S1: { } 2 0 1 n n = is a regular language S2: { } 0 1 0 1 and 1 m n m n m n + = = is a regular language Which of the following statements is correct? (a) Only S1 is correct (b) Only S2 is correct (c) Both S1 and S2 are correct (d) None of S1 and S2 is correct GATE CS - 2001 1.5 Which of the following statements s true? (a) If a language is context free it can always be accepted by a deterministic push-down automaton (b) The union of two context free languages is context free (c) The intersection of two context free languages is context free (d) The complement of a context free language is context free 1.6 Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least (a) N 2 (b) 2 N (c) 2N (d) N! 1.7 More than one word are put in one cache block to (a) exploit the temporal locality of reference in a program (b) exploit the spatial locality of reference in a program (c) reduce the miss penalty (d) none of the above 1.8 Which of the following statements is false? (a) Virtual memory implements the translation of a programâ€™s address space into physical memory address space (b) Virtual memory allows each program to exceed the size of the primary memory (c) Virtual memory increases the degree of multiprogramming (d) Virtual memory reduces the context switching overhead 1.9 A low memory can be connected to 8085 by using (a) INTER (b) RESET IN (c) HOLD (d) READY 1.10 Suppose a processor does not have any stack pointer register. Which of the following statements is true? (a) It cannot have subroutine call instruction (b) It can have subroutine call instruction, but no nested subroutine calls (c) Nested subroutine calls are possible, but interrupts are not (d) All sequences of subroutine calls and also interrupts are possible Page 3 GATE CS - 2001 SECTION - A 1. This question consists of TWENTY-FIVE sub-questions (1.1 â€“ 1.25) of ONE mark each. For each of these sub-questions, four possible alternatives, A, B, C and D are provided. Choose the most appropriate alternative and darken its bubble on the Objective Response Sheet (ORS) against the corresponding sub-question number using a soft HB pencil. Do not darken more than one bubble for any sub-question. Do not use the ORS for any rough work. You may use the answer book for any rough work, if needed. 1.1 Consider the following statements: S1: The sum of two singular n × n matrices may be non-singular S2: The sum of two n × n non-singular matrices may be singular. Which of the following statements is correct? (a) S1 and S2 are both true (b) S1 is true, S2 is false (c) S1 is false, S2 is true (d) S1 and S2 are both false 1.2 Consider the following relations: R1 (a,b) iff (a+b) is even over the set of integers R2 (a,b) iff (a+b) is odd over the set of integers R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers R4 (a,b) iff |a â€“ b| = 2 over the set of natural numbers Which of the following statements is correct? (a) R1 and R2 are equivalence relations, R3 and R4 are not (b) R1 and R3 are equivalence relations, R2 and R4 are not (c) R1 and R4 are equivalence relations, R2 and R3 are not (d) R1, R2, R3 and R4 are all equivalence relations 1.3 Consider two well-formed formulas in prepositional logic F1: P ? ¬P F2: (P?¬P)?(¬P?P) Which of the following statements is correct? (a) F1 is satisfiable, F2 is valid (b) F1 unsatisfiable, F2 is satisfiable (c) F1 is unsatisfiable, F2 is valid (d) F1 and F2 are both satisfiable 1.4 consider the following two statements: S1: { } 2 0 1 n n = is a regular language S2: { } 0 1 0 1 and 1 m n m n m n + = = is a regular language Which of the following statements is correct? (a) Only S1 is correct (b) Only S2 is correct (c) Both S1 and S2 are correct (d) None of S1 and S2 is correct GATE CS - 2001 1.5 Which of the following statements s true? (a) If a language is context free it can always be accepted by a deterministic push-down automaton (b) The union of two context free languages is context free (c) The intersection of two context free languages is context free (d) The complement of a context free language is context free 1.6 Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least (a) N 2 (b) 2 N (c) 2N (d) N! 1.7 More than one word are put in one cache block to (a) exploit the temporal locality of reference in a program (b) exploit the spatial locality of reference in a program (c) reduce the miss penalty (d) none of the above 1.8 Which of the following statements is false? (a) Virtual memory implements the translation of a programâ€™s address space into physical memory address space (b) Virtual memory allows each program to exceed the size of the primary memory (c) Virtual memory increases the degree of multiprogramming (d) Virtual memory reduces the context switching overhead 1.9 A low memory can be connected to 8085 by using (a) INTER (b) RESET IN (c) HOLD (d) READY 1.10 Suppose a processor does not have any stack pointer register. Which of the following statements is true? (a) It cannot have subroutine call instruction (b) It can have subroutine call instruction, but no nested subroutine calls (c) Nested subroutine calls are possible, but interrupts are not (d) All sequences of subroutine calls and also interrupts are possible GATE CS - 2001 yz wx 1.11 Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map? (a) xy y z ' + (b) wx y xy xz ' '+ + (c) w x y z xy ' ' + + (d) xz+y 1.12 A processor needs software interrupt to (a) test the interrupt system of the processor (b) implement co-routines (c) obtain system services which need execution of privileged instructions (d) return from subroutine 1.13 A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged (a) a hardware interrupt is needed (b) a software interrupt is needed (c) a privileged instruction (which does not generate an interrupt) is needed (d) a non-privileged instruction (which does not generate an interrupt is needed 1.14 Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort? (a) O(n) (b) O(n log n) (c) O(n 2 ) (d) O(n!) 1.15 Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i=n), the index of the parent is (a) i-1 (b) ? 2 i ? (c) ? 2 i ? (d) ( ) 1 2 i + 00 01 11 10 00 0 X 0 X 01 X 1 X 1 11 0 X 1 0 10 0 1 X 0 Page 4 GATE CS - 2001 SECTION - A 1. This question consists of TWENTY-FIVE sub-questions (1.1 â€“ 1.25) of ONE mark each. For each of these sub-questions, four possible alternatives, A, B, C and D are provided. Choose the most appropriate alternative and darken its bubble on the Objective Response Sheet (ORS) against the corresponding sub-question number using a soft HB pencil. Do not darken more than one bubble for any sub-question. Do not use the ORS for any rough work. You may use the answer book for any rough work, if needed. 1.1 Consider the following statements: S1: The sum of two singular n × n matrices may be non-singular S2: The sum of two n × n non-singular matrices may be singular. Which of the following statements is correct? (a) S1 and S2 are both true (b) S1 is true, S2 is false (c) S1 is false, S2 is true (d) S1 and S2 are both false 1.2 Consider the following relations: R1 (a,b) iff (a+b) is even over the set of integers R2 (a,b) iff (a+b) is odd over the set of integers R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers R4 (a,b) iff |a â€“ b| = 2 over the set of natural numbers Which of the following statements is correct? (a) R1 and R2 are equivalence relations, R3 and R4 are not (b) R1 and R3 are equivalence relations, R2 and R4 are not (c) R1 and R4 are equivalence relations, R2 and R3 are not (d) R1, R2, R3 and R4 are all equivalence relations 1.3 Consider two well-formed formulas in prepositional logic F1: P ? ¬P F2: (P?¬P)?(¬P?P) Which of the following statements is correct? (a) F1 is satisfiable, F2 is valid (b) F1 unsatisfiable, F2 is satisfiable (c) F1 is unsatisfiable, F2 is valid (d) F1 and F2 are both satisfiable 1.4 consider the following two statements: S1: { } 2 0 1 n n = is a regular language S2: { } 0 1 0 1 and 1 m n m n m n + = = is a regular language Which of the following statements is correct? (a) Only S1 is correct (b) Only S2 is correct (c) Both S1 and S2 are correct (d) None of S1 and S2 is correct GATE CS - 2001 1.5 Which of the following statements s true? (a) If a language is context free it can always be accepted by a deterministic push-down automaton (b) The union of two context free languages is context free (c) The intersection of two context free languages is context free (d) The complement of a context free language is context free 1.6 Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least (a) N 2 (b) 2 N (c) 2N (d) N! 1.7 More than one word are put in one cache block to (a) exploit the temporal locality of reference in a program (b) exploit the spatial locality of reference in a program (c) reduce the miss penalty (d) none of the above 1.8 Which of the following statements is false? (a) Virtual memory implements the translation of a programâ€™s address space into physical memory address space (b) Virtual memory allows each program to exceed the size of the primary memory (c) Virtual memory increases the degree of multiprogramming (d) Virtual memory reduces the context switching overhead 1.9 A low memory can be connected to 8085 by using (a) INTER (b) RESET IN (c) HOLD (d) READY 1.10 Suppose a processor does not have any stack pointer register. Which of the following statements is true? (a) It cannot have subroutine call instruction (b) It can have subroutine call instruction, but no nested subroutine calls (c) Nested subroutine calls are possible, but interrupts are not (d) All sequences of subroutine calls and also interrupts are possible GATE CS - 2001 yz wx 1.11 Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map? (a) xy y z ' + (b) wx y xy xz ' '+ + (c) w x y z xy ' ' + + (d) xz+y 1.12 A processor needs software interrupt to (a) test the interrupt system of the processor (b) implement co-routines (c) obtain system services which need execution of privileged instructions (d) return from subroutine 1.13 A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged (a) a hardware interrupt is needed (b) a software interrupt is needed (c) a privileged instruction (which does not generate an interrupt) is needed (d) a non-privileged instruction (which does not generate an interrupt is needed 1.14 Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort? (a) O(n) (b) O(n log n) (c) O(n 2 ) (d) O(n!) 1.15 Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i=n), the index of the parent is (a) i-1 (b) ? 2 i ? (c) ? 2 i ? (d) ( ) 1 2 i + 00 01 11 10 00 0 X 0 X 01 X 1 X 1 11 0 X 1 0 10 0 1 X 0 GATE CS - 2001 1.16 Let ( ) ( ) ( ) 10 2 log and log f n n n g n n n = = be two positive functions of n. Which of the following statements is correct? (a) f(n) = O(g(n) and g(n) ?O(f(n)) (b) g(n) = O(f(n) and f(n) ?O(g(n)) (c) f(n)?O(g(n)) and g(n) ?O(f(n)) (d) f(n)=O(g(n)) and g(n) =O(f(n)) 1.17 The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called (a) Assembly (b) Parsing (c) Relocation (d) Symbol resolution 1.18 Which of the following statements is false? (a) An unambiguous grammar has same leftmost and rightmost derivation (b) An LL(1) parser is a top-down parser (c) LALR is more powerful than SLR (d) An ambiguous grammar can never be LR(k) for any k 1.19 Consider a set of n tasks with known runtimes r 1 , r 2 , â€¦. r n to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput? (a) Round-Robin (b) Shortest-Job-First (c) Highest-Response-Ratio-Next (d) First-Come-First-Served 1.20 Where does the swap space reside? (a) RAM (b) Disk (c) ROM (d) On-chip cache 1.21 Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will (a) always decrease the number of page faults (b) always increase the number of page faults (c) sometimes increase the number of page faults (d) never affect the number of page faults 1.22 Which of the following requires a device driver? (a) Register (b) Cache (c) Main memory (d) Disk Page 5 GATE CS - 2001 SECTION - A 1. This question consists of TWENTY-FIVE sub-questions (1.1 â€“ 1.25) of ONE mark each. For each of these sub-questions, four possible alternatives, A, B, C and D are provided. Choose the most appropriate alternative and darken its bubble on the Objective Response Sheet (ORS) against the corresponding sub-question number using a soft HB pencil. Do not darken more than one bubble for any sub-question. Do not use the ORS for any rough work. You may use the answer book for any rough work, if needed. 1.1 Consider the following statements: S1: The sum of two singular n × n matrices may be non-singular S2: The sum of two n × n non-singular matrices may be singular. Which of the following statements is correct? (a) S1 and S2 are both true (b) S1 is true, S2 is false (c) S1 is false, S2 is true (d) S1 and S2 are both false 1.2 Consider the following relations: R1 (a,b) iff (a+b) is even over the set of integers R2 (a,b) iff (a+b) is odd over the set of integers R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers R4 (a,b) iff |a â€“ b| = 2 over the set of natural numbers Which of the following statements is correct? (a) R1 and R2 are equivalence relations, R3 and R4 are not (b) R1 and R3 are equivalence relations, R2 and R4 are not (c) R1 and R4 are equivalence relations, R2 and R3 are not (d) R1, R2, R3 and R4 are all equivalence relations 1.3 Consider two well-formed formulas in prepositional logic F1: P ? ¬P F2: (P?¬P)?(¬P?P) Which of the following statements is correct? (a) F1 is satisfiable, F2 is valid (b) F1 unsatisfiable, F2 is satisfiable (c) F1 is unsatisfiable, F2 is valid (d) F1 and F2 are both satisfiable 1.4 consider the following two statements: S1: { } 2 0 1 n n = is a regular language S2: { } 0 1 0 1 and 1 m n m n m n + = = is a regular language Which of the following statements is correct? (a) Only S1 is correct (b) Only S2 is correct (c) Both S1 and S2 are correct (d) None of S1 and S2 is correct GATE CS - 2001 1.5 Which of the following statements s true? (a) If a language is context free it can always be accepted by a deterministic push-down automaton (b) The union of two context free languages is context free (c) The intersection of two context free languages is context free (d) The complement of a context free language is context free 1.6 Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least (a) N 2 (b) 2 N (c) 2N (d) N! 1.7 More than one word are put in one cache block to (a) exploit the temporal locality of reference in a program (b) exploit the spatial locality of reference in a program (c) reduce the miss penalty (d) none of the above 1.8 Which of the following statements is false? (a) Virtual memory implements the translation of a programâ€™s address space into physical memory address space (b) Virtual memory allows each program to exceed the size of the primary memory (c) Virtual memory increases the degree of multiprogramming (d) Virtual memory reduces the context switching overhead 1.9 A low memory can be connected to 8085 by using (a) INTER (b) RESET IN (c) HOLD (d) READY 1.10 Suppose a processor does not have any stack pointer register. Which of the following statements is true? (a) It cannot have subroutine call instruction (b) It can have subroutine call instruction, but no nested subroutine calls (c) Nested subroutine calls are possible, but interrupts are not (d) All sequences of subroutine calls and also interrupts are possible GATE CS - 2001 yz wx 1.11 Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map? (a) xy y z ' + (b) wx y xy xz ' '+ + (c) w x y z xy ' ' + + (d) xz+y 1.12 A processor needs software interrupt to (a) test the interrupt system of the processor (b) implement co-routines (c) obtain system services which need execution of privileged instructions (d) return from subroutine 1.13 A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged (a) a hardware interrupt is needed (b) a software interrupt is needed (c) a privileged instruction (which does not generate an interrupt) is needed (d) a non-privileged instruction (which does not generate an interrupt is needed 1.14 Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort? (a) O(n) (b) O(n log n) (c) O(n 2 ) (d) O(n!) 1.15 Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i=n), the index of the parent is (a) i-1 (b) ? 2 i ? (c) ? 2 i ? (d) ( ) 1 2 i + 00 01 11 10 00 0 X 0 X 01 X 1 X 1 11 0 X 1 0 10 0 1 X 0 GATE CS - 2001 1.16 Let ( ) ( ) ( ) 10 2 log and log f n n n g n n n = = be two positive functions of n. Which of the following statements is correct? (a) f(n) = O(g(n) and g(n) ?O(f(n)) (b) g(n) = O(f(n) and f(n) ?O(g(n)) (c) f(n)?O(g(n)) and g(n) ?O(f(n)) (d) f(n)=O(g(n)) and g(n) =O(f(n)) 1.17 The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called (a) Assembly (b) Parsing (c) Relocation (d) Symbol resolution 1.18 Which of the following statements is false? (a) An unambiguous grammar has same leftmost and rightmost derivation (b) An LL(1) parser is a top-down parser (c) LALR is more powerful than SLR (d) An ambiguous grammar can never be LR(k) for any k 1.19 Consider a set of n tasks with known runtimes r 1 , r 2 , â€¦. r n to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput? (a) Round-Robin (b) Shortest-Job-First (c) Highest-Response-Ratio-Next (d) First-Come-First-Served 1.20 Where does the swap space reside? (a) RAM (b) Disk (c) ROM (d) On-chip cache 1.21 Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will (a) always decrease the number of page faults (b) always increase the number of page faults (c) sometimes increase the number of page faults (d) never affect the number of page faults 1.22 Which of the following requires a device driver? (a) Register (b) Cache (c) Main memory (d) Disk GATE CS - 2001 1.23 Consider a schema R(A,B,C,D) and functional dependencies A B and C D. Then the decomposition of R into R 1 (AB) and R 2 (CD) is (a) dependency preserving and lossless join (b) lossless join but not dependency preserving (c) dependency preserving but not lossless join (d) not dependency preserving and not lossless join 1.24 Suppose the adjacency relation of vertices in a graph is represented in a table Adj (X,Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length? (a) List of all vertices adjacent to a given vertex (b) List all vertices which have self loops (c) List all vertices which belong to cycles of less than three vertices (d) List all vertices reachable from a given vertex 1.25 Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. then the relational algebra expression A a s = (r s) is always equal to (a) A a s = (r) (b) r (c) A a s = (r) s (d) None of the above 2. This question consists of TWENTY-FIVE sub-questions (2.1 â€“ 2.25) of TWO marks each. For each of these sub-questions, four possible alternatives, A,B, C and D are provided. Choose the most appropriate alternative and darken its bubble on the Objective Response Sheet (ORS) against the corresponding sub-question number using a soft HB pencil. Do not darken more than one bubble for any sub-question. Do not use the ORS for any rough work. You may use the answer book for any rough work, if needed. 2.1 How many 4-digit even numbers have all 4 digits distinct? (a) 2240 (b) 2296 (c) 2620 (d) 4536 2.2 Consider the following statements: S1: There exists infinite sets A, B, C such that An(B?C) is finite. S2: There exists two irrational numbers x and y such that (x+y) is rational. Which of the following is true about S1 and S2? (a) Only S1 is correct (b) Only S2 is correct (c) Both S1 and S2 are correct (d) None of S1 and S2 is correctRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!