One Stop GATE Forum: (CS) Gate Examination -2000 Question Papers

Message

   SECTION -A (75 marks)  

1. This
		   question consists of 23 (TWENTY THREE) multiple-choice questions, each
		   carrying one mark. For each question (1. 1-1. 23), four alternatives
		   (a, b, c and d) are given, out of which only one is correct. Write the
		   correct answers in the boxes corresponding to the questions only on the
		   FIRST sheet of the answer book. ( 23 X l = 23) 

		   1.1 The minimum number of cards to be dealt from an arbitrarily
		   shuffled deck of 52 cards to guarantee that three cards are from some
		   same suit is 

		        3 
		        8 
		        9 
		        12 

 1.2 An n x n array v is defined as follows: 

 v [i, j] = i-j for all i, j, 1 £ i £ n, 1 £ j £ n 

 The sum of the elements of the array v is 

		        0 
		        n-1 
		        n 2 - 3n + 2 
		        n 2 (n + 1) /2 

 1.3 The determinant of the matrix is 

		        4 
		        0 
		        5 
		        20 

		   1.4 Let S and T be languages over S = {a, b} represented by the regular
		   expressions (a + b *) * and (a + b) *, respectively. Which of the
		   following is true? 

		        S Ì T 
		        T Ì S 
		        S = T 
		        S Ç T = f 

 1.5 Let L denotes the language generated by the grammar S ® 0S0/00. 

 Which of the following is true? 

		        L = 0 + 
		        L is regular but not 0 + 
		        L is context free but not regular 
		        L is not context free 

 1.6 The number 43 in 2's complement representation is 

		        01010101 
		        11010101 
		        00101011 
		        10101011 

 1.7 To put the 8085 microprocessor in the wait state 

		        lower the-HOLD input 
		        lower the READY input 
		        raise the HOLD input 
		        raise the READY input 

		   1.8 Comparing the time T1 taken for a single instruction on a pipelined
		   CPU with time T2 taken on a non pipelined but identical CPU, we can
		   say that 

		        T1 £ T2 
		        T1 ³ T2 
		        T1< T2 
		        T1 is T2 plus the time taken for one instruction fetch cycle 

 1.9 The 8085 microprocessor responds to the presence of an interrupt 

		        as soon as the TRAP pin becomes 'high' 
		        by checking the TRAP pin for 'high' status at the end of each instruction fetch 
		        by checking the TRAP pin for 'high' status at the end of the execution of each instruction 
		        by Checking the TRAP pin for 'high' status at regular intervals 

 1.10 The most appropriate matching for the following pairs 

 X: Indirect addressing 1 : Loops 

 Y: Immediate addressing 2 : Pointers 

 Z: Auto decrement addressing 3: Constants 

 is 

		        X-3, Y-2, Z-1 
		        X-I, Y-3, Z-2 
		        X-2, Y-3, Z-1 
		        X-3, Y-l, Z-2 

 1.11 The following C declarations 

 struct node { 

 int i; 

 float j ; 

 }; 

 struct node *s[10] ; 

 define s to be 

 (a) An array, each element of which is a pointer to a structure of type node 

 (b) A structure of 2 fields, each field being a pointer to an array of 10 elements 

 (c) A structure of 3 fields: an integer, a float, and an array of 10 elements 

 (d) An array, each element of which is a structure of type node 

 1.12 The most appropriate matching for the following pairs 

 X: m = malloc (5); m=NULL; 1 : using dangling pointers 

 Y: free (n) ; n-> value=5; 2 : using uninitialized pointers 

 Z: char *p; *p = 'a' ; 3 : lost memory 

 is 

		        X-I, Y-3, Z-2 
		        X-2, Y-l, Z-3 
		        X-3, Y-2, Z-l 
		        X-3, Y-l, Z-2 

 1.13 The most appropriate matching for the following pairs 

 X: depth first search 1: heap 

 Y: breadth-first search 2: queue 

 Z: sorting 3: stack 

 is 

		        ,X-l,Y-2; Z-3 
		        X-3, Y-l, Z-2 
		        X-3, Y-2, Z-l 
		        X-2, Y-3, Z-l 

		   1.14 Consider the following nested representation of binary trees: (X Y
		   Z) indicates Y and Z are the left and right sub trees, respectively, of
		   node X Note that Y and Z may be NULL, or further nested. Which of the
		   following represents a valid binary tree? 

		        (1 2 (4 5 6 7)) 
		        (1( (2 3 4) 5 6)7) 
		        (1 (2 3 4)(5 67)) 
		        (1 (23 NULL) ( 4 5)) 

		   1.15 Let s be a sorted array of n integers. Let t (n) denote the time
		   taken for the most efficient algorithm to determine if there are two
		   elements with sum less than 1000 in s. Which of the following
		   statements is true? 

		        t (n) is 0 (1) 
		        n £ t (n) £ n log 2 n 
		        n log 2 n £ t (n) < 
		        t (n) = 

 1.16 Aliasing in the context of programming languages refers to 

		        multiple variables having the same memory location 
		        multiple variables having the same value 
		        multiple variables having the same identifier 
		        multiple uses of the same variable 

 1.17 Consider the following C declaration 

 struct { 

 short s [5] 

 union { 

 float y; 

 long z; 

 }u; 

 } t; 

		   Assume that objects of the type short, float and long occupy 2 bytes, 4
		   bytes and 8 bytes, respectively. The memory requirement for variable t,
		   ignoring alignment considerations, is 

 (a) 22 bytes (b) 14 bytes 

 (e) 18 bytes (d) 10 bytes 

 1.18 The number of tokens in the following C statement 

 printf("i=%d, &i= %x", i, &i); 

 is 

		        3 
		        26 
		        10 
		        21 

		   1.19 Which of the following derivations does a top-down parser use
		   while parsing an input string? The input is assumed to be scanned in
		   left to right order. 

 (a) Leftmost derivation 

 (b) Leftmost derivation traced out in reverse 

 (c) Rightmost derivation 

 (d) Rightmost derivation traced out in reverse 

 1.20 Which of the following need not necessarily be saved on a context switch between processes? 

		        General purpose registers 
		        Translation look aside buffer 
		        Program counter 
		        All of the above 

		   1.21 Let m [0]….m [4] be mutexes (binary semaphores) and P [0] ... P
		   [4] be processes. Suppose each process P executes the following : 

 wait (m ); wait (m [(i + 1) mode 4]); 

 …….. 

 release (m ) ; release (m[(i + 1) mod 4 ] ); 

 This could cause 

		        Thrashing 
		        Deadlock 
		        Starvation, but not deadlock 
		        None of the above 

 1.22 B + -trees are preferred to binary trees in databases because 

		        Disk capacities are greater than memory capacities 
		        Disk access is much slower than memory access 
		        Disk data transfer rates are much less than memory data transfer rates 
		        Disks are more reliable than memory 

 1.23 Given the relations 

 employee (name, salary, deptno), and 

 department (deptno, deptname, address) . 

		   which of the following queries cannot be expressed using the basic
		   relational algebra operations ( s , p , ´ , |X|, È , Ç , - )? 

 (a) Department address of every employee 

 (b) Employees whose name is the same as their department name 

 (c) The sum of all employee salaries 

 (d) All employees of a given department 

		   2. This question consists of 26 (TWENTY SIX) multiple-choice questions,
		   each carrying two marks. For each question (2.1- 2. 26), four
		   alternatives (a, b, c and d) are given, out of which only one is
		   correct. Write the correct answers in the boxes corresponding to the
		   questions only on the SECOND sheet of the answer book. (26 x 2  =  52) 

		   2.1 X, Y and Z are closed intervals of unit length on the real line.
		   The overlap of X and Y is half a unit. The overlap of Y and Z is also
		   half a, unit. Let the overlap of X and Z be k units. Which of the
		   following is true? 

		        k must be 1 
		        k must be 0 
		        k can take any value between 0 and 1 
		        None of the above 

		       		          E 1 and E 2 are events in a probability space satisfying the following constraints: 

		        Pr (E I) = Pr (E 2) 
		        Pr (E I U E 2) = 1 
		        E 1 and E 2 are independent 

 The value of Pr (E 1), the probability of the event E p is 

		        0 

		        1 

 2.3 Let 

 and 

 Which of the following statements is true? 

		        S > T 
		        S = T 
		        S < T and 2S > T 
		        2S £ T 

 2.4 A polynomial p(x) satisfies the following: 

 p (1) = p(3) = p(5) = 1 

 p(2) = p(4) = -1 

 The minimum degree of such a polynomial is 

		        1 
		        2 
		        3 
		        4 

 2.5 A relation R is defined on the set of integers as x Ry if f(x + y) is even. Which of the following statements is true? 

		        R is not an equivalence relation 
		        R is an equivalence relation having 1 equivalence class 
		        R is an equivalence relation having 2 equivalence classes 
		        R is an equivalence relation having 3 equivalence classes 

 2.6 Let P(S) denotes the power set of set S. Which of the following is always true? 

		        P(P (S)) = P(S) 
		        P(S) Ç P(P(S)) = { f } 
		        P(S) Ç S = P(S) 
		        S Ï P(S) 

		   2.7 Let a, b, c, d be propositions. Assume that the equivalences a « (b
		   V-b) and b « c hold. Then the truth value of the formula (a Ù b) -J. (a
		   Ù c) Ù d) is always 

		        True 
		        False 
		        Same as the truth value of b 
		        Same as the truth value of d 

 2.8 What can be said about a regular language L over {a} whose minimal finite state automaton has two states? 

		        L must be {a n| n is odd} 
		        L must be {a n| n is even} 
		        L must be {a n| ³ O} 
		        Either L must be {a n | n is odd}, or L must be {a n | n is even} 

 2.9 Consider the following decision problems : 

 (PI) Does a given finite state machine accept a given string 

 (P2) Does a given context free grammar generate an infinite number of stings 

 Which of the following statements is true? 

 (a) Both (PI) and (P2) are decidable (b) Neither (PI) nor (P2) are decidable 

 (c) Only (PI) is decidable (d) Only (P2) is decidable 

 2.10 The simultaneous equations on the Boolean variables x, y, z and w, 

 x+y+z=l 

 xy =0 

 xz+w = l 

 x+  =0 

 have the following solution for x, y, z and w, respectively. 

 (a) 0 1 0 0 (b) 1 1 0 1 

 (c) 1 0 1 1 (d) 1 0 0 0 

 2.11 Which function does NOT implement the Karnaugh map given below? 

		          WZ ® 
		          00 
		          01 
		          11 
		          10 

		          Xy ¯ 

		          00 
		          0 
		          x 
		          0 
		          0 

		          01 
		          0 
		          x 
		          1 
		          1 

		          11 
		          1 
		          1 
		          1 
		          1 

		          10 
		          0 
		          x 
		          0 
		          0 

 (a) (w + x) y (b) xy + yw 

 (c) (w + x) (w + y) (x + y) (d) None of the above 

		   The following arrangement of master-slave flip flops has the initial
		   state of P, Q as 0, 1 (respectively). After three clock cycles the
		   output state P, Q is (respectively), 
		          1,0 
		          1,1 
		          0,0 
		          0,1 

 2.13 A graphics card has on board memory of 1 MB. Which of the following modes can the card not support? 

 (a) 1600 x 400 resolution with 256 colours on a 17-inch monitor 

 (b) 1600 x 400 resolution with 16 million colours on a 14-inch monitor 

 (c) 800 x 400 resolution with 16 million colours on a 17-inch monitor 

 (d) 800 x 800 resolution with 256 colours on a 14-inch monitor 

 2.14 Consider the values A = 2.0 x 10 30, B =-2.0 x 10 30 , C= 1.0, and the sequence 

 X: =A+B Y: =A+C 

 X: = X + C Y: =Y+B 

 executed on a computer where floating-point numbers are represented with 32 bits. The values for X and Y will be 

		        X = 1.0, Y = 1.0 
		        X = 1.0, Y = 0.0 
		        X = 0.0, Y = 1.0 
		        X = 0.0, Y = 0.0 

		   2.15 Suppose you are given an array s[1..n] and a procedure reverse (s,
		   i, j) which reverses the order of elements in a between positions i and
		   j (both inclusive). What does the following sequence do, where 1 £ k £
		   n: 

 reverse (s, 1, k) ; 

 reverse (s, k + 1, n); 

 reverse (s, l, n) ; 

 (a) Rotates s left by k positions (b) Leaves s unchanged 

 (c) Reverses all elements of s (d) None of the above 

		   2.16 Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in
		   a postorder, inorder and preorder traversal, respectively, of a
		   complete binary tree. Which of the following is always true? 

 (a) LASTIN = LASTPOST (b) LASTIN = LASTPRE 

 (c) LASTPRE = LASTPOST (d) None of the above 

 2.17 Consider the following functions 

 Which of the following is true? 

 (a) h (n) is O (f (n) ) (b) h (n) is O (g (n)) 

 (c) g (n) is not O (f (n) ) (d) f(n) is O(g (n)) 

		   2.18 Let G be an undirected connected graph with distinct edge weight.
		   Let e max be the edge with maximum weight and e min the edge with
		   minimum weight. Which of the following statements is false? 

		        Every minimum spanning tree of G must contain e min 
		        If e max is in a minimum spanning tree, then its removal must disconnect G 
		        No minimum spanning tree contains e max 
		        G has a unique minimum spanning tree 

		   2.19 Let G be an undirected graph. Consider a depth-first traversal of
		   G, and let T be the resulting depth-first search tree. Let u be a
		   vertex in G and let v be the first new (unvisited) vertex visited after
		   visiting u in the traversal. Which of the following statements is
		   always true? 

 (a) {u,v} must be an edge in G, and u is a descendant of v in T 

 (b) {u,v} must be an edge in G, and v is a descendant of u in T 

 (c) If {u,v} is not an edge in G then u is a leaf in T 

 (d) If {u,v} is not an edge in G then u and v must have the same parent in T 

		       		          The value of j at the end of the execution of the following C program 

 int incr (int i) 

 { 

 static int count = 0 ; 

 count = count + i ; 

 return ( count) ; 

 } 

 main ( ) { 

 int i, j ; 

 for (i = 0; i < = 4 ; i++) 

 j = incr (i) ; 

 } 

 is 

		       		          10 
		          4 
		          6 
		          7 

		       		          Given the following expression grammar: 

 E ® E * F | F+E | F 

 F ® F-F | id 

 Which of the following is true? 

 (a) * has higher precedence than + (b) - has higher precedence than * 

 (c) + and - have same precedence (d) + has higher precedence than * 

		   2.22 Suppose the time to service a page fault is on the average 10
		   milliseconds, while a memory access takes 1 microsecond. Then a 99.99%
		   hit ratio results in average memory access time of 

 (a) 1.9999 milliseconds (b) 1 millisecond 

 (c) 9.999 microseconds (d) 1.9999 microseconds 

 2.23 Which of the following is NOT a valid deadlock prevention scheme? 

 (a) Release all resources before requesting a new resource 

 (b) Number the resources uniquely and never request a lower numbered resource than the last one requested 

 (c) Never request a resource after releasing any resource 

 (d) Request and all required resources be allocated before execution 

 2.24 Given the following relation instance 

		      X Y Z

 1 4 2 

 1 5 3 

 1 6 3 

 3 2 2 

 Which of the following functional dependencies are satisfied by the instance? 

 (a) XY ® Z and Z ® Y (b)YZ ® X and Y ® Z 

 (c)YZ ® X and X ® Z (d) XZ ® Y and Y ® X 

 2.25 Given relations r (w, x) and s (V, 1,), the result of 

 select distinct w, x 

 from r, s 

 is guaranteed to be same as r, provided 

		        r has no duplicates and s is non-empty 
		        r and shave no duplicates 
		        s has no duplicates and r is non-empty 
		        r and s have the same number of tuples 

		   2.26 In SQL, relations can contain null values, and comparisons with
		   null values are treated as unknown. Suppose all comparisons with a null
		   value are treated as false. Which of the following pairs is not
		   equivalent? 

 (a) x = 5 not (not (x = 5 ) ) 

 (b) x= 5 x> 4 and x < 6, where x is an integer 

 (c) x ¹ 5 not (x = 5) 

 (d) None of the above 


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers