Page 1 GATE CS - 1997 SECTION – A 1. This question contains 10 sub-parts each carrying ONE mark. Each sub-part contains a multiple-choice question. Write in your answer book the sub-part number and the letter a, b, c or d corresponding to the most appropriate answer. 1.1 The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow? (a) 0.3 (b) 0.25 (c) 0.35 (d) 0.4 1.2 The Newton-Raphson method is used to find the root of the equation 2 2 0 x - = . If the iterations are started form –1, the iterations will (a) converge to -1 (b) converge to 2 (c) converge to - 2 (d) not converge 1.3 The determinant of the matrix 6 8 1 1 0 2 4 6 0 0 4 8 0 0 0 1 - ? ? ? ? ? ? ? ? ? ? - ? ? ? ? is: (a) 11 (b) -48 (c) 0 (d) -24 1.4 The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used? (a) Singly linked list (b) Doubly linked list (c) Circular doubly linked list (d) Array implementation of list 1.5 The correct matching for the following pairs is (A) All pairs shortest paths (1) Greedy (B) Quick Sort (2) Depth-First search (C) Minimum weight spanning tree (3) Dynamic Programming (D) Connected Components (4) Divide and Conquer (a) A – 2 B – 4 C – 1 D - 3 (b) A – 3 B – 4 C – 1 D - 2 (c) A – 3 B – 4 C – 2 D - 1 (d) A – 4 B – 1 C – 2 D - 3 Page 2 GATE CS - 1997 SECTION – A 1. This question contains 10 sub-parts each carrying ONE mark. Each sub-part contains a multiple-choice question. Write in your answer book the sub-part number and the letter a, b, c or d corresponding to the most appropriate answer. 1.1 The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow? (a) 0.3 (b) 0.25 (c) 0.35 (d) 0.4 1.2 The Newton-Raphson method is used to find the root of the equation 2 2 0 x - = . If the iterations are started form –1, the iterations will (a) converge to -1 (b) converge to 2 (c) converge to - 2 (d) not converge 1.3 The determinant of the matrix 6 8 1 1 0 2 4 6 0 0 4 8 0 0 0 1 - ? ? ? ? ? ? ? ? ? ? - ? ? ? ? is: (a) 11 (b) -48 (c) 0 (d) -24 1.4 The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used? (a) Singly linked list (b) Doubly linked list (c) Circular doubly linked list (d) Array implementation of list 1.5 The correct matching for the following pairs is (A) All pairs shortest paths (1) Greedy (B) Quick Sort (2) Depth-First search (C) Minimum weight spanning tree (3) Dynamic Programming (D) Connected Components (4) Divide and Conquer (a) A – 2 B – 4 C – 1 D - 3 (b) A – 3 B – 4 C – 1 D - 2 (c) A – 3 B – 4 C – 2 D - 1 (d) A – 4 B – 1 C – 2 D - 3 GATE CS - 1997 1.6 In the following grammar :: :: * :: Y X X Y Y Y Z Z Z id = ? = = Which of the following is true? (a) ‘?’ is left associative while ‘*’ is right associative (b) Both ‘?’ and ‘*’ is left associative (c) ‘?’ is right associative while ‘*’ is left associative (d) None of the above 1.7 Which of the following is essential for converting an infix expression to the postfix form efficiently? (a) An operator stack (b) An operand stack (c) An operand stack and an operator stack (d) A parse tree 1.8 A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which one of the following is true? (a) A compiler using static memory allocation can be written for L (b) A compiler cannot be written for L; an interpreter must be used. (c) A compiler using dynamic memory allocation can be written for L (d) None of the above 1.9 The conditional expansion facility of macro processor is provided to (a) test a condition during the execution of the expanded program (b) to expand certain model statements depending upon the value of a condition during the execution of the expanded program (c) to implement recursion (d) to expand certain model statements depending upon the value of a condition during the process of macro expansion. 1.10 Heap allocation is required for languages. (a) that support recursion (b) that support dynamic data structures (c) that use dynamic scope rules (d) None of the above Page 3 GATE CS - 1997 SECTION – A 1. This question contains 10 sub-parts each carrying ONE mark. Each sub-part contains a multiple-choice question. Write in your answer book the sub-part number and the letter a, b, c or d corresponding to the most appropriate answer. 1.1 The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow? (a) 0.3 (b) 0.25 (c) 0.35 (d) 0.4 1.2 The Newton-Raphson method is used to find the root of the equation 2 2 0 x - = . If the iterations are started form –1, the iterations will (a) converge to -1 (b) converge to 2 (c) converge to - 2 (d) not converge 1.3 The determinant of the matrix 6 8 1 1 0 2 4 6 0 0 4 8 0 0 0 1 - ? ? ? ? ? ? ? ? ? ? - ? ? ? ? is: (a) 11 (b) -48 (c) 0 (d) -24 1.4 The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used? (a) Singly linked list (b) Doubly linked list (c) Circular doubly linked list (d) Array implementation of list 1.5 The correct matching for the following pairs is (A) All pairs shortest paths (1) Greedy (B) Quick Sort (2) Depth-First search (C) Minimum weight spanning tree (3) Dynamic Programming (D) Connected Components (4) Divide and Conquer (a) A – 2 B – 4 C – 1 D - 3 (b) A – 3 B – 4 C – 1 D - 2 (c) A – 3 B – 4 C – 2 D - 1 (d) A – 4 B – 1 C – 2 D - 3 GATE CS - 1997 1.6 In the following grammar :: :: * :: Y X X Y Y Y Z Z Z id = ? = = Which of the following is true? (a) ‘?’ is left associative while ‘*’ is right associative (b) Both ‘?’ and ‘*’ is left associative (c) ‘?’ is right associative while ‘*’ is left associative (d) None of the above 1.7 Which of the following is essential for converting an infix expression to the postfix form efficiently? (a) An operator stack (b) An operand stack (c) An operand stack and an operator stack (d) A parse tree 1.8 A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which one of the following is true? (a) A compiler using static memory allocation can be written for L (b) A compiler cannot be written for L; an interpreter must be used. (c) A compiler using dynamic memory allocation can be written for L (d) None of the above 1.9 The conditional expansion facility of macro processor is provided to (a) test a condition during the execution of the expanded program (b) to expand certain model statements depending upon the value of a condition during the execution of the expanded program (c) to implement recursion (d) to expand certain model statements depending upon the value of a condition during the process of macro expansion. 1.10 Heap allocation is required for languages. (a) that support recursion (b) that support dynamic data structures (c) that use dynamic scope rules (d) None of the above GATE CS - 1997 2. The question contains 5 subparts, each carrying 1 mark. Each subpart contains a multiple-choice question. Write in your answer book the subpart number and the letter a, b, c or d corresponding to the most appropriate answer. 2.1 Let * be defined as x*y=x +y. Let z = x*y. value of z*x is (a) x +y (b) x (c) 0 (d) 1 2.2 RST 7.5 interrupt in 8085 microprocessor executes service routing from interrupt vector location (a) 0000H (b) 0075H (c) 003CH (d) 0034H 2.3 Purpose of a start bit in RS 232 serial communication protocol is (a) to synchronize receiver for receiving every byte (b) to synchronize receiver for receiving a sequence of bytes (c) a parity bit (d) to synchronize receiver for receiving the last byte 2.4 The correct matching for the following pairs is (A) DMA I/O (1) High speed RAM (B) Cache (2) Disk (C) Interrupt I/O (3) Printer (D) Condition Code Register (4) ALU (a) A – 4 B – 3 C – 1 D - 2 (b) A – 2 B – 1 C – 3 D - 4 (c) A – 4 B – 3 C – 2 D - 1 (d) A – 2 B – 3 C – 4 D - 1 2.5 An N-bit carry lookhead adder, where N is a multiple of 4, employs ICs 74181 (4 bit ALU) and 74182 (4 bit carry lookhead generator). The minimum addition time using the best architecture for this adder is (a) proportional to N (b) proportional to log N (c) a constant (d) None of the above 3. The question contains 10 subparts, each carrying 1 mark. Each subpart contains a multiple-choice question. Write in your answer book the subpart number and the letter a, b, c or d corresponding to the most appropriate answer. 3.1 Let (Z,*) be an algebraic structure, where Z is the set of integers and the operation * is defined by n*m = maximum (n,m). which of the following statements is true for (Z,*)? (a) (Z,*) is a monoid (b) (Z,*) is an Abelian group (c) (Z,*) is a group (d) None of the above Page 4 GATE CS - 1997 SECTION – A 1. This question contains 10 sub-parts each carrying ONE mark. Each sub-part contains a multiple-choice question. Write in your answer book the sub-part number and the letter a, b, c or d corresponding to the most appropriate answer. 1.1 The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow? (a) 0.3 (b) 0.25 (c) 0.35 (d) 0.4 1.2 The Newton-Raphson method is used to find the root of the equation 2 2 0 x - = . If the iterations are started form –1, the iterations will (a) converge to -1 (b) converge to 2 (c) converge to - 2 (d) not converge 1.3 The determinant of the matrix 6 8 1 1 0 2 4 6 0 0 4 8 0 0 0 1 - ? ? ? ? ? ? ? ? ? ? - ? ? ? ? is: (a) 11 (b) -48 (c) 0 (d) -24 1.4 The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used? (a) Singly linked list (b) Doubly linked list (c) Circular doubly linked list (d) Array implementation of list 1.5 The correct matching for the following pairs is (A) All pairs shortest paths (1) Greedy (B) Quick Sort (2) Depth-First search (C) Minimum weight spanning tree (3) Dynamic Programming (D) Connected Components (4) Divide and Conquer (a) A – 2 B – 4 C – 1 D - 3 (b) A – 3 B – 4 C – 1 D - 2 (c) A – 3 B – 4 C – 2 D - 1 (d) A – 4 B – 1 C – 2 D - 3 GATE CS - 1997 1.6 In the following grammar :: :: * :: Y X X Y Y Y Z Z Z id = ? = = Which of the following is true? (a) ‘?’ is left associative while ‘*’ is right associative (b) Both ‘?’ and ‘*’ is left associative (c) ‘?’ is right associative while ‘*’ is left associative (d) None of the above 1.7 Which of the following is essential for converting an infix expression to the postfix form efficiently? (a) An operator stack (b) An operand stack (c) An operand stack and an operator stack (d) A parse tree 1.8 A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which one of the following is true? (a) A compiler using static memory allocation can be written for L (b) A compiler cannot be written for L; an interpreter must be used. (c) A compiler using dynamic memory allocation can be written for L (d) None of the above 1.9 The conditional expansion facility of macro processor is provided to (a) test a condition during the execution of the expanded program (b) to expand certain model statements depending upon the value of a condition during the execution of the expanded program (c) to implement recursion (d) to expand certain model statements depending upon the value of a condition during the process of macro expansion. 1.10 Heap allocation is required for languages. (a) that support recursion (b) that support dynamic data structures (c) that use dynamic scope rules (d) None of the above GATE CS - 1997 2. The question contains 5 subparts, each carrying 1 mark. Each subpart contains a multiple-choice question. Write in your answer book the subpart number and the letter a, b, c or d corresponding to the most appropriate answer. 2.1 Let * be defined as x*y=x +y. Let z = x*y. value of z*x is (a) x +y (b) x (c) 0 (d) 1 2.2 RST 7.5 interrupt in 8085 microprocessor executes service routing from interrupt vector location (a) 0000H (b) 0075H (c) 003CH (d) 0034H 2.3 Purpose of a start bit in RS 232 serial communication protocol is (a) to synchronize receiver for receiving every byte (b) to synchronize receiver for receiving a sequence of bytes (c) a parity bit (d) to synchronize receiver for receiving the last byte 2.4 The correct matching for the following pairs is (A) DMA I/O (1) High speed RAM (B) Cache (2) Disk (C) Interrupt I/O (3) Printer (D) Condition Code Register (4) ALU (a) A – 4 B – 3 C – 1 D - 2 (b) A – 2 B – 1 C – 3 D - 4 (c) A – 4 B – 3 C – 2 D - 1 (d) A – 2 B – 3 C – 4 D - 1 2.5 An N-bit carry lookhead adder, where N is a multiple of 4, employs ICs 74181 (4 bit ALU) and 74182 (4 bit carry lookhead generator). The minimum addition time using the best architecture for this adder is (a) proportional to N (b) proportional to log N (c) a constant (d) None of the above 3. The question contains 10 subparts, each carrying 1 mark. Each subpart contains a multiple-choice question. Write in your answer book the subpart number and the letter a, b, c or d corresponding to the most appropriate answer. 3.1 Let (Z,*) be an algebraic structure, where Z is the set of integers and the operation * is defined by n*m = maximum (n,m). which of the following statements is true for (Z,*)? (a) (Z,*) is a monoid (b) (Z,*) is an Abelian group (c) (Z,*) is a group (d) None of the above GATE CS - 1997 3.2 Which of the following propositions is a tautology? (a) (p ? q) p (b) p ? (q p) (c) p ? (p q) (d) p (p q) 3.3 In the lattice defined by the Hasse diagram given in following figure, how many complements does the element ‘e’ have? (a) 2 (b) 3 (c) 0 (d) 1 3.4 Given S={a,b}, which one of the following sets is not countable? (a) Set of all strings over S (b) Set of all languages over S (c) Set of all regular languages over S (d) Set of all languages over S accepted by Turing machines 3.5 Locality of reference implies that the page reference being made by a process (a) will always be to the page used in the previous page reference (b) is likely to be to one of the pages used in the last few page references (c) will always be to one of the pages existing in memory (d) will always lead to a page fault 3.6 The correct matching for the following pairs is: (A) Disk scheduling (1) Round robin (B) Batch processing (2) SCAN (C) Time sharing (3) LIFO (D) Interrupt processing (4) FIFO (a) A – 3 B – 4 C – 2 D - 1 (b) A – 4 B – 3 C – 2 D - 1 (c) A – 2 B – 4 C – 1 D - 3 (d) A – 3 B – 4 C – 3 D - 2 3.7 I/O redirection (a) implies changing the name of a file (b) can be employed to use an existing file as input file for a program (c) implies connection 2 programs through a pipe (d) None of the above a b e f d c g Page 5 GATE CS - 1997 SECTION – A 1. This question contains 10 sub-parts each carrying ONE mark. Each sub-part contains a multiple-choice question. Write in your answer book the sub-part number and the letter a, b, c or d corresponding to the most appropriate answer. 1.1 The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow? (a) 0.3 (b) 0.25 (c) 0.35 (d) 0.4 1.2 The Newton-Raphson method is used to find the root of the equation 2 2 0 x - = . If the iterations are started form –1, the iterations will (a) converge to -1 (b) converge to 2 (c) converge to - 2 (d) not converge 1.3 The determinant of the matrix 6 8 1 1 0 2 4 6 0 0 4 8 0 0 0 1 - ? ? ? ? ? ? ? ? ? ? - ? ? ? ? is: (a) 11 (b) -48 (c) 0 (d) -24 1.4 The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used? (a) Singly linked list (b) Doubly linked list (c) Circular doubly linked list (d) Array implementation of list 1.5 The correct matching for the following pairs is (A) All pairs shortest paths (1) Greedy (B) Quick Sort (2) Depth-First search (C) Minimum weight spanning tree (3) Dynamic Programming (D) Connected Components (4) Divide and Conquer (a) A – 2 B – 4 C – 1 D - 3 (b) A – 3 B – 4 C – 1 D - 2 (c) A – 3 B – 4 C – 2 D - 1 (d) A – 4 B – 1 C – 2 D - 3 GATE CS - 1997 1.6 In the following grammar :: :: * :: Y X X Y Y Y Z Z Z id = ? = = Which of the following is true? (a) ‘?’ is left associative while ‘*’ is right associative (b) Both ‘?’ and ‘*’ is left associative (c) ‘?’ is right associative while ‘*’ is left associative (d) None of the above 1.7 Which of the following is essential for converting an infix expression to the postfix form efficiently? (a) An operator stack (b) An operand stack (c) An operand stack and an operator stack (d) A parse tree 1.8 A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which one of the following is true? (a) A compiler using static memory allocation can be written for L (b) A compiler cannot be written for L; an interpreter must be used. (c) A compiler using dynamic memory allocation can be written for L (d) None of the above 1.9 The conditional expansion facility of macro processor is provided to (a) test a condition during the execution of the expanded program (b) to expand certain model statements depending upon the value of a condition during the execution of the expanded program (c) to implement recursion (d) to expand certain model statements depending upon the value of a condition during the process of macro expansion. 1.10 Heap allocation is required for languages. (a) that support recursion (b) that support dynamic data structures (c) that use dynamic scope rules (d) None of the above GATE CS - 1997 2. The question contains 5 subparts, each carrying 1 mark. Each subpart contains a multiple-choice question. Write in your answer book the subpart number and the letter a, b, c or d corresponding to the most appropriate answer. 2.1 Let * be defined as x*y=x +y. Let z = x*y. value of z*x is (a) x +y (b) x (c) 0 (d) 1 2.2 RST 7.5 interrupt in 8085 microprocessor executes service routing from interrupt vector location (a) 0000H (b) 0075H (c) 003CH (d) 0034H 2.3 Purpose of a start bit in RS 232 serial communication protocol is (a) to synchronize receiver for receiving every byte (b) to synchronize receiver for receiving a sequence of bytes (c) a parity bit (d) to synchronize receiver for receiving the last byte 2.4 The correct matching for the following pairs is (A) DMA I/O (1) High speed RAM (B) Cache (2) Disk (C) Interrupt I/O (3) Printer (D) Condition Code Register (4) ALU (a) A – 4 B – 3 C – 1 D - 2 (b) A – 2 B – 1 C – 3 D - 4 (c) A – 4 B – 3 C – 2 D - 1 (d) A – 2 B – 3 C – 4 D - 1 2.5 An N-bit carry lookhead adder, where N is a multiple of 4, employs ICs 74181 (4 bit ALU) and 74182 (4 bit carry lookhead generator). The minimum addition time using the best architecture for this adder is (a) proportional to N (b) proportional to log N (c) a constant (d) None of the above 3. The question contains 10 subparts, each carrying 1 mark. Each subpart contains a multiple-choice question. Write in your answer book the subpart number and the letter a, b, c or d corresponding to the most appropriate answer. 3.1 Let (Z,*) be an algebraic structure, where Z is the set of integers and the operation * is defined by n*m = maximum (n,m). which of the following statements is true for (Z,*)? (a) (Z,*) is a monoid (b) (Z,*) is an Abelian group (c) (Z,*) is a group (d) None of the above GATE CS - 1997 3.2 Which of the following propositions is a tautology? (a) (p ? q) p (b) p ? (q p) (c) p ? (p q) (d) p (p q) 3.3 In the lattice defined by the Hasse diagram given in following figure, how many complements does the element ‘e’ have? (a) 2 (b) 3 (c) 0 (d) 1 3.4 Given S={a,b}, which one of the following sets is not countable? (a) Set of all strings over S (b) Set of all languages over S (c) Set of all regular languages over S (d) Set of all languages over S accepted by Turing machines 3.5 Locality of reference implies that the page reference being made by a process (a) will always be to the page used in the previous page reference (b) is likely to be to one of the pages used in the last few page references (c) will always be to one of the pages existing in memory (d) will always lead to a page fault 3.6 The correct matching for the following pairs is: (A) Disk scheduling (1) Round robin (B) Batch processing (2) SCAN (C) Time sharing (3) LIFO (D) Interrupt processing (4) FIFO (a) A – 3 B – 4 C – 2 D - 1 (b) A – 4 B – 3 C – 2 D - 1 (c) A – 2 B – 4 C – 1 D - 3 (d) A – 3 B – 4 C – 3 D - 2 3.7 I/O redirection (a) implies changing the name of a file (b) can be employed to use an existing file as input file for a program (c) implies connection 2 programs through a pipe (d) None of the above a b e f d c g GATE CS - 1997 3.8 When an interrupt occurs, an operating system (a) ignores the interrupt (b) always changes state of interrupted process after processing the interrupt (c) always resumes execution of interrupted process after processing the interrupt (d) may change state of interrupted process to ‘blocked’ and schedule another process 3.9 Thrashing (a) reduces page I/O (b) decreases the degree of multiprogramming (c) implies excessive page I/O (d) improve the system performance 3.10 Dirty bit for a page in a page table (a) helps avoid unnecessary writes on a paging device (b) helps maintain LRU information (c) allows only read on a page (d) None of the above 4. The question contains 10 subparts, each carrying 2 marks. Each subpart contains a multiple-choice question. Write in your answer book the subpart number and the letter a, b, c or d corresponding to the most appropriate answer. 4.1 What is the maximum value of the function ( ) 2 2 2 6 f x x x = - + in the interval [0,2]? (a) 6 (b) 10 (c) 12 (d) 5.5 4.2 Let a= ( ) ij a be an n-rowed square matrix and 12 I be the matrix obtained by interchanging the first and second rows of the n-rowed Identify matrix. Then 12 AI is such that its first (a) row is the same as its second row (b) row is the same as the second row of A (c) column is the same as the second column of A (d) row is all zero 4.3 Using a forward Euler method to solve y'' (t) =f(t), y(0), y'' (0)=0 with a step size of h, we obtain the following values of y in the first four iterations: (a) 0, hf (0), h(f(0) + f(h)) and h(f(0) + f(h) = f(2h)) (b) 0, 0 h 2 f(0) and 2h 2 f(0)+f(h)Read More

380 docs|127 tests