Computer Science and Information Technology (CS) 1994 GATE Paper without solution GATE Notes | EduRev

 Page 1


GATE CS - 1994
  
Read the following instructions carefully: 
(i) This question paper consists of two sections: A & B. 
(ii) Section A has EIGHT questions. Answer all questions in this section. 
(iii) Section B has TWENTY questions. Answer any TEN questions in this section. 
(iv) Begin answer for this section on a fresh page. 
(v) Answer to questions in each section should appear together in the same 
sequence in which they appear in the question paper. 
(vi) There will be no negative marking. 
Section – A 
1. Choose one of the alternatives for the following questions:
1.1 FORTRAN implementation do not permit recursion because 
(a) they use static allocation for variables  
(b) they use dynamic allocation for variables 
(c) stacks are not available on all machines 
(d) it is not possible to implement recursion on all machines 
1.2 Let A and B be real symmetric matrices of size n n × . Then which one of the 
following is true?
(a) 1 AA' = (b) 
1
A A
-
= (c) AB = BA (d) ( ) AB BA
'
=
1.3 Backward Euler method for solving the differential equation ( ) ,
dy
f x y
dx
= is 
specified by, (choose one of the following).  
(a) ( )
1
,
n n n n
y y hf x y
+
= + (b) ( )
1 1 1
,
n n n n
y y hf x y
+ + +
= +
(c) ( )
1 1
2 ,
n n n n
y y hf x y
+ -
= + (d) ( ) ( )
1 1 1
1 ,
n n n
y h f x y
+ + +
= +
1.4 Let A and B be any two arbitrary events, then, which one of the following is true? 
(a) ( ) ( ) ( ) P A B P A P B n =  (b) ( ) ( ) ( ) P A B P A P B ? = +
(c) 
( ) ( ) ( ) P A B P A B P B = n (d) ( ) ( ) ( ) P A B P A P B ? = +
1.5 An unrestricted use of the “goto” statement is harmful because 
(a) it makes it more difficult to verify programs  
(b) it increases the running time of the programs 
(c) it increases the memory required for the programs 
(d) it results in the compiler generating longer machine code 
Page 2


GATE CS - 1994
  
Read the following instructions carefully: 
(i) This question paper consists of two sections: A & B. 
(ii) Section A has EIGHT questions. Answer all questions in this section. 
(iii) Section B has TWENTY questions. Answer any TEN questions in this section. 
(iv) Begin answer for this section on a fresh page. 
(v) Answer to questions in each section should appear together in the same 
sequence in which they appear in the question paper. 
(vi) There will be no negative marking. 
Section – A 
1. Choose one of the alternatives for the following questions:
1.1 FORTRAN implementation do not permit recursion because 
(a) they use static allocation for variables  
(b) they use dynamic allocation for variables 
(c) stacks are not available on all machines 
(d) it is not possible to implement recursion on all machines 
1.2 Let A and B be real symmetric matrices of size n n × . Then which one of the 
following is true?
(a) 1 AA' = (b) 
1
A A
-
= (c) AB = BA (d) ( ) AB BA
'
=
1.3 Backward Euler method for solving the differential equation ( ) ,
dy
f x y
dx
= is 
specified by, (choose one of the following).  
(a) ( )
1
,
n n n n
y y hf x y
+
= + (b) ( )
1 1 1
,
n n n n
y y hf x y
+ + +
= +
(c) ( )
1 1
2 ,
n n n n
y y hf x y
+ -
= + (d) ( ) ( )
1 1 1
1 ,
n n n
y h f x y
+ + +
= +
1.4 Let A and B be any two arbitrary events, then, which one of the following is true? 
(a) ( ) ( ) ( ) P A B P A P B n =  (b) ( ) ( ) ( ) P A B P A P B ? = +
(c) 
( ) ( ) ( ) P A B P A B P B = n (d) ( ) ( ) ( ) P A B P A P B ? = +
1.5 An unrestricted use of the “goto” statement is harmful because 
(a) it makes it more difficult to verify programs  
(b) it increases the running time of the programs 
(c) it increases the memory required for the programs 
(d) it results in the compiler generating longer machine code 
GATE CS - 1994
  
1.6 The number of distinct simple graphs with upto three nodes is 
(a) 15 (b) 10 (c) 7 (d) 9 
1.7 The recurrence relation that arises in relation with the complexity of binary 
search is: 
(a) ( ) , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(b) ( ) 2 , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(c) ( ) log
2
n
T n T n
? ?
= +
? ?
? ?
(d) ( )
2
n
T n T n
? ?
= +
? ?
? ?
1.8 The logic expression for the output of the circuit shown in figure below is: 
(a) AC BC CD + +
(b) AC BC CD + + 
(c) ABC CD = 
(d)    A B B C C D + + 
1.9 The rank of matrix 
0 0 3
9 3 5 is:
3 1 1
- ? ?
? ?
? ?
? ?
? ?
 
(a) 0 (b) 1 (c) 2 (d) 3 
1.10 Some group ( ) , G o is known to be abelian. Then, which one of the following is
true for G? 
(a) 
1
 for every g g g G
-
= ? (b) 
2
 for every g g g G = ?
(c) ( )
2
2 2
 for every , goh g oh g h G = ? (d) G is of finite order 
1.11 In a compact single dimensional array representation for lower triangular 
matrices (i.e all the elements above the diagonal are zero) of size , n n × non-zero 
elements (i.e elements of the lower triangle) of each row are stored one after 
another, starting from the first row, the index of the ( ) ,
th
i j element of the lower
triangular matrix in this new representation is: 
(a) i j + (b) 1 i j + - (c) 
( ) 1
2
i i
j
-
+ (d) 
( ) 1
2
j j
i
-
+
1.12 Generation of intermediate code based on an abstract machine model is useful in 
compilers because  
(a) it makes implementation of lexical analysis and syntax analysis easier 
A 
B 
C 
D 
Page 3


GATE CS - 1994
  
Read the following instructions carefully: 
(i) This question paper consists of two sections: A & B. 
(ii) Section A has EIGHT questions. Answer all questions in this section. 
(iii) Section B has TWENTY questions. Answer any TEN questions in this section. 
(iv) Begin answer for this section on a fresh page. 
(v) Answer to questions in each section should appear together in the same 
sequence in which they appear in the question paper. 
(vi) There will be no negative marking. 
Section – A 
1. Choose one of the alternatives for the following questions:
1.1 FORTRAN implementation do not permit recursion because 
(a) they use static allocation for variables  
(b) they use dynamic allocation for variables 
(c) stacks are not available on all machines 
(d) it is not possible to implement recursion on all machines 
1.2 Let A and B be real symmetric matrices of size n n × . Then which one of the 
following is true?
(a) 1 AA' = (b) 
1
A A
-
= (c) AB = BA (d) ( ) AB BA
'
=
1.3 Backward Euler method for solving the differential equation ( ) ,
dy
f x y
dx
= is 
specified by, (choose one of the following).  
(a) ( )
1
,
n n n n
y y hf x y
+
= + (b) ( )
1 1 1
,
n n n n
y y hf x y
+ + +
= +
(c) ( )
1 1
2 ,
n n n n
y y hf x y
+ -
= + (d) ( ) ( )
1 1 1
1 ,
n n n
y h f x y
+ + +
= +
1.4 Let A and B be any two arbitrary events, then, which one of the following is true? 
(a) ( ) ( ) ( ) P A B P A P B n =  (b) ( ) ( ) ( ) P A B P A P B ? = +
(c) 
( ) ( ) ( ) P A B P A B P B = n (d) ( ) ( ) ( ) P A B P A P B ? = +
1.5 An unrestricted use of the “goto” statement is harmful because 
(a) it makes it more difficult to verify programs  
(b) it increases the running time of the programs 
(c) it increases the memory required for the programs 
(d) it results in the compiler generating longer machine code 
GATE CS - 1994
  
1.6 The number of distinct simple graphs with upto three nodes is 
(a) 15 (b) 10 (c) 7 (d) 9 
1.7 The recurrence relation that arises in relation with the complexity of binary 
search is: 
(a) ( ) , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(b) ( ) 2 , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(c) ( ) log
2
n
T n T n
? ?
= +
? ?
? ?
(d) ( )
2
n
T n T n
? ?
= +
? ?
? ?
1.8 The logic expression for the output of the circuit shown in figure below is: 
(a) AC BC CD + +
(b) AC BC CD + + 
(c) ABC CD = 
(d)    A B B C C D + + 
1.9 The rank of matrix 
0 0 3
9 3 5 is:
3 1 1
- ? ?
? ?
? ?
? ?
? ?
 
(a) 0 (b) 1 (c) 2 (d) 3 
1.10 Some group ( ) , G o is known to be abelian. Then, which one of the following is
true for G? 
(a) 
1
 for every g g g G
-
= ? (b) 
2
 for every g g g G = ?
(c) ( )
2
2 2
 for every , goh g oh g h G = ? (d) G is of finite order 
1.11 In a compact single dimensional array representation for lower triangular 
matrices (i.e all the elements above the diagonal are zero) of size , n n × non-zero 
elements (i.e elements of the lower triangle) of each row are stored one after 
another, starting from the first row, the index of the ( ) ,
th
i j element of the lower
triangular matrix in this new representation is: 
(a) i j + (b) 1 i j + - (c) 
( ) 1
2
i i
j
-
+ (d) 
( ) 1
2
j j
i
-
+
1.12 Generation of intermediate code based on an abstract machine model is useful in 
compilers because  
(a) it makes implementation of lexical analysis and syntax analysis easier 
A 
B 
C 
D 
GATE CS - 1994
  
(b) syntax-directed translations can be written for intermediate code generation  
(c) it enhances the portability of the front end of the compiler  
(d) it is not possible to generate code for real machines directly from high level 
language programs 
1.13 A memory page containing a heavily used variable that was initialized very early 
and is in constant use is removed when 
(a) LRU page replacement algorithm is used 
(b) FIFO page replacement algorithm is used 
(c) LFU page replacement algorithm is used 
(d) None of the above  
1.14 Which of the following permutations can be obtained in the output (in the same 
order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that 
order? 
(a) 3, 4, 5, 1, 2 (b) 3, 4, 5, 2, 1 (c) 1, 5, 2, 3, 4 (d) 5, 4, 3, 1, 2 
1.15 The number of substrings (of all lengths inclusive) that can be formed from a 
character string of length n is 
(a) n (b) 
2
n (c) 
( ) 1
2
n n-
(d) 
( ) 1
2
n n+
1.16 Which of the following conversions is not possible (algorithmically)? 
(a) Regular grammar to context free grammar  
(b) Non-deterministic FSA to deterministic FSA  
(c) Non-deterministic PDA to deterministic PDA  
(d) Non-deterministic Turing machine to deterministic Turing machine 
1.17 Linked lists are not suitable data structures of which one of the following 
problems? 
(a) Insertion sort   (b) Binary search  
(c) Radix sort   (d) Polynomial manipulation 
1.18 Which of the following features cannot be captured by context-free grammars? 
(a) Syntax of if-then-else statements  
(b) Syntax of recursive procedures 
(c) Whether a variable has been declared before its use 
(d) Variable names of arbitrary length 
Page 4


GATE CS - 1994
  
Read the following instructions carefully: 
(i) This question paper consists of two sections: A & B. 
(ii) Section A has EIGHT questions. Answer all questions in this section. 
(iii) Section B has TWENTY questions. Answer any TEN questions in this section. 
(iv) Begin answer for this section on a fresh page. 
(v) Answer to questions in each section should appear together in the same 
sequence in which they appear in the question paper. 
(vi) There will be no negative marking. 
Section – A 
1. Choose one of the alternatives for the following questions:
1.1 FORTRAN implementation do not permit recursion because 
(a) they use static allocation for variables  
(b) they use dynamic allocation for variables 
(c) stacks are not available on all machines 
(d) it is not possible to implement recursion on all machines 
1.2 Let A and B be real symmetric matrices of size n n × . Then which one of the 
following is true?
(a) 1 AA' = (b) 
1
A A
-
= (c) AB = BA (d) ( ) AB BA
'
=
1.3 Backward Euler method for solving the differential equation ( ) ,
dy
f x y
dx
= is 
specified by, (choose one of the following).  
(a) ( )
1
,
n n n n
y y hf x y
+
= + (b) ( )
1 1 1
,
n n n n
y y hf x y
+ + +
= +
(c) ( )
1 1
2 ,
n n n n
y y hf x y
+ -
= + (d) ( ) ( )
1 1 1
1 ,
n n n
y h f x y
+ + +
= +
1.4 Let A and B be any two arbitrary events, then, which one of the following is true? 
(a) ( ) ( ) ( ) P A B P A P B n =  (b) ( ) ( ) ( ) P A B P A P B ? = +
(c) 
( ) ( ) ( ) P A B P A B P B = n (d) ( ) ( ) ( ) P A B P A P B ? = +
1.5 An unrestricted use of the “goto” statement is harmful because 
(a) it makes it more difficult to verify programs  
(b) it increases the running time of the programs 
(c) it increases the memory required for the programs 
(d) it results in the compiler generating longer machine code 
GATE CS - 1994
  
1.6 The number of distinct simple graphs with upto three nodes is 
(a) 15 (b) 10 (c) 7 (d) 9 
1.7 The recurrence relation that arises in relation with the complexity of binary 
search is: 
(a) ( ) , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(b) ( ) 2 , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(c) ( ) log
2
n
T n T n
? ?
= +
? ?
? ?
(d) ( )
2
n
T n T n
? ?
= +
? ?
? ?
1.8 The logic expression for the output of the circuit shown in figure below is: 
(a) AC BC CD + +
(b) AC BC CD + + 
(c) ABC CD = 
(d)    A B B C C D + + 
1.9 The rank of matrix 
0 0 3
9 3 5 is:
3 1 1
- ? ?
? ?
? ?
? ?
? ?
 
(a) 0 (b) 1 (c) 2 (d) 3 
1.10 Some group ( ) , G o is known to be abelian. Then, which one of the following is
true for G? 
(a) 
1
 for every g g g G
-
= ? (b) 
2
 for every g g g G = ?
(c) ( )
2
2 2
 for every , goh g oh g h G = ? (d) G is of finite order 
1.11 In a compact single dimensional array representation for lower triangular 
matrices (i.e all the elements above the diagonal are zero) of size , n n × non-zero 
elements (i.e elements of the lower triangle) of each row are stored one after 
another, starting from the first row, the index of the ( ) ,
th
i j element of the lower
triangular matrix in this new representation is: 
(a) i j + (b) 1 i j + - (c) 
( ) 1
2
i i
j
-
+ (d) 
( ) 1
2
j j
i
-
+
1.12 Generation of intermediate code based on an abstract machine model is useful in 
compilers because  
(a) it makes implementation of lexical analysis and syntax analysis easier 
A 
B 
C 
D 
GATE CS - 1994
  
(b) syntax-directed translations can be written for intermediate code generation  
(c) it enhances the portability of the front end of the compiler  
(d) it is not possible to generate code for real machines directly from high level 
language programs 
1.13 A memory page containing a heavily used variable that was initialized very early 
and is in constant use is removed when 
(a) LRU page replacement algorithm is used 
(b) FIFO page replacement algorithm is used 
(c) LFU page replacement algorithm is used 
(d) None of the above  
1.14 Which of the following permutations can be obtained in the output (in the same 
order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that 
order? 
(a) 3, 4, 5, 1, 2 (b) 3, 4, 5, 2, 1 (c) 1, 5, 2, 3, 4 (d) 5, 4, 3, 1, 2 
1.15 The number of substrings (of all lengths inclusive) that can be formed from a 
character string of length n is 
(a) n (b) 
2
n (c) 
( ) 1
2
n n-
(d) 
( ) 1
2
n n+
1.16 Which of the following conversions is not possible (algorithmically)? 
(a) Regular grammar to context free grammar  
(b) Non-deterministic FSA to deterministic FSA  
(c) Non-deterministic PDA to deterministic PDA  
(d) Non-deterministic Turing machine to deterministic Turing machine 
1.17 Linked lists are not suitable data structures of which one of the following 
problems? 
(a) Insertion sort   (b) Binary search  
(c) Radix sort   (d) Polynomial manipulation 
1.18 Which of the following features cannot be captured by context-free grammars? 
(a) Syntax of if-then-else statements  
(b) Syntax of recursive procedures 
(c) Whether a variable has been declared before its use 
(d) Variable names of arbitrary length 
GATE CS - 1994
  
1.19. Which of the following algorithm design techniques is used in the quicksort 
algorithm? 
(a) Dynamic programming (b) Backtracking 
(c) Divide and conquer  (d) Greedy method 
1.20. In which one of the following cases is it possible to obtain different results for 
call-by reference and call-by-name parameter passing methods? 
(a) Passing a constant value as a parameter 
(b) Passing the address of an array as a parameter 
(c) Passing an array element as a parameter 
(d) Passing an array following statements is true 
1.21. Which one of the following statements is true? 
(a) Macro definitions cannot appear within other macro definitions in assembly 
language programs 
(b) Overlaying is used to run a program which is longer than the address space 
of computer 
(c) Virtual memory can be used to accommodate a program which is longer than 
the address space of a computer 
(d) It is not possible to write interrupt service routines in a high level language 
1.22. Which one of the following statements is false? 
(a) Optimal binary search tree construction can be performed efficiently using 
dynamic programming. 
(b) Breadth-first search cannot be used to find converted components of a graph  
(c) Given the prefix and postfix walks over a binary tree, the binary tree cannot 
be uniquely constructed. 
(d) Depth-first search can be used to find connected components of a graph. 
1.23. Consider the following two functions: 
( )
( )
3
1
2
2 3
 for 0 10,000
 for 10,000
 for 0 100
 for 100
n n
g n
n n
n n
g n
n n
? = =
=
?
=
?
= = ?
=
?
>
?
Which of the following is true? 
(a) ( ) ( ) ( )
1 2
 is 0 g n g n (b) ( ) ( )
3
1
 is 0 g n n
(c) ( ) ( ) ( )
2 1
 is 0 g n g n (d) ( ) ( )
2
 is 0 g n n
Page 5


GATE CS - 1994
  
Read the following instructions carefully: 
(i) This question paper consists of two sections: A & B. 
(ii) Section A has EIGHT questions. Answer all questions in this section. 
(iii) Section B has TWENTY questions. Answer any TEN questions in this section. 
(iv) Begin answer for this section on a fresh page. 
(v) Answer to questions in each section should appear together in the same 
sequence in which they appear in the question paper. 
(vi) There will be no negative marking. 
Section – A 
1. Choose one of the alternatives for the following questions:
1.1 FORTRAN implementation do not permit recursion because 
(a) they use static allocation for variables  
(b) they use dynamic allocation for variables 
(c) stacks are not available on all machines 
(d) it is not possible to implement recursion on all machines 
1.2 Let A and B be real symmetric matrices of size n n × . Then which one of the 
following is true?
(a) 1 AA' = (b) 
1
A A
-
= (c) AB = BA (d) ( ) AB BA
'
=
1.3 Backward Euler method for solving the differential equation ( ) ,
dy
f x y
dx
= is 
specified by, (choose one of the following).  
(a) ( )
1
,
n n n n
y y hf x y
+
= + (b) ( )
1 1 1
,
n n n n
y y hf x y
+ + +
= +
(c) ( )
1 1
2 ,
n n n n
y y hf x y
+ -
= + (d) ( ) ( )
1 1 1
1 ,
n n n
y h f x y
+ + +
= +
1.4 Let A and B be any two arbitrary events, then, which one of the following is true? 
(a) ( ) ( ) ( ) P A B P A P B n =  (b) ( ) ( ) ( ) P A B P A P B ? = +
(c) 
( ) ( ) ( ) P A B P A B P B = n (d) ( ) ( ) ( ) P A B P A P B ? = +
1.5 An unrestricted use of the “goto” statement is harmful because 
(a) it makes it more difficult to verify programs  
(b) it increases the running time of the programs 
(c) it increases the memory required for the programs 
(d) it results in the compiler generating longer machine code 
GATE CS - 1994
  
1.6 The number of distinct simple graphs with upto three nodes is 
(a) 15 (b) 10 (c) 7 (d) 9 
1.7 The recurrence relation that arises in relation with the complexity of binary 
search is: 
(a) ( ) , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(b) ( ) 2 , k a constant
2
n
T n T k
? ?
= +
? ?
? ?
(c) ( ) log
2
n
T n T n
? ?
= +
? ?
? ?
(d) ( )
2
n
T n T n
? ?
= +
? ?
? ?
1.8 The logic expression for the output of the circuit shown in figure below is: 
(a) AC BC CD + +
(b) AC BC CD + + 
(c) ABC CD = 
(d)    A B B C C D + + 
1.9 The rank of matrix 
0 0 3
9 3 5 is:
3 1 1
- ? ?
? ?
? ?
? ?
? ?
 
(a) 0 (b) 1 (c) 2 (d) 3 
1.10 Some group ( ) , G o is known to be abelian. Then, which one of the following is
true for G? 
(a) 
1
 for every g g g G
-
= ? (b) 
2
 for every g g g G = ?
(c) ( )
2
2 2
 for every , goh g oh g h G = ? (d) G is of finite order 
1.11 In a compact single dimensional array representation for lower triangular 
matrices (i.e all the elements above the diagonal are zero) of size , n n × non-zero 
elements (i.e elements of the lower triangle) of each row are stored one after 
another, starting from the first row, the index of the ( ) ,
th
i j element of the lower
triangular matrix in this new representation is: 
(a) i j + (b) 1 i j + - (c) 
( ) 1
2
i i
j
-
+ (d) 
( ) 1
2
j j
i
-
+
1.12 Generation of intermediate code based on an abstract machine model is useful in 
compilers because  
(a) it makes implementation of lexical analysis and syntax analysis easier 
A 
B 
C 
D 
GATE CS - 1994
  
(b) syntax-directed translations can be written for intermediate code generation  
(c) it enhances the portability of the front end of the compiler  
(d) it is not possible to generate code for real machines directly from high level 
language programs 
1.13 A memory page containing a heavily used variable that was initialized very early 
and is in constant use is removed when 
(a) LRU page replacement algorithm is used 
(b) FIFO page replacement algorithm is used 
(c) LFU page replacement algorithm is used 
(d) None of the above  
1.14 Which of the following permutations can be obtained in the output (in the same 
order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that 
order? 
(a) 3, 4, 5, 1, 2 (b) 3, 4, 5, 2, 1 (c) 1, 5, 2, 3, 4 (d) 5, 4, 3, 1, 2 
1.15 The number of substrings (of all lengths inclusive) that can be formed from a 
character string of length n is 
(a) n (b) 
2
n (c) 
( ) 1
2
n n-
(d) 
( ) 1
2
n n+
1.16 Which of the following conversions is not possible (algorithmically)? 
(a) Regular grammar to context free grammar  
(b) Non-deterministic FSA to deterministic FSA  
(c) Non-deterministic PDA to deterministic PDA  
(d) Non-deterministic Turing machine to deterministic Turing machine 
1.17 Linked lists are not suitable data structures of which one of the following 
problems? 
(a) Insertion sort   (b) Binary search  
(c) Radix sort   (d) Polynomial manipulation 
1.18 Which of the following features cannot be captured by context-free grammars? 
(a) Syntax of if-then-else statements  
(b) Syntax of recursive procedures 
(c) Whether a variable has been declared before its use 
(d) Variable names of arbitrary length 
GATE CS - 1994
  
1.19. Which of the following algorithm design techniques is used in the quicksort 
algorithm? 
(a) Dynamic programming (b) Backtracking 
(c) Divide and conquer  (d) Greedy method 
1.20. In which one of the following cases is it possible to obtain different results for 
call-by reference and call-by-name parameter passing methods? 
(a) Passing a constant value as a parameter 
(b) Passing the address of an array as a parameter 
(c) Passing an array element as a parameter 
(d) Passing an array following statements is true 
1.21. Which one of the following statements is true? 
(a) Macro definitions cannot appear within other macro definitions in assembly 
language programs 
(b) Overlaying is used to run a program which is longer than the address space 
of computer 
(c) Virtual memory can be used to accommodate a program which is longer than 
the address space of a computer 
(d) It is not possible to write interrupt service routines in a high level language 
1.22. Which one of the following statements is false? 
(a) Optimal binary search tree construction can be performed efficiently using 
dynamic programming. 
(b) Breadth-first search cannot be used to find converted components of a graph  
(c) Given the prefix and postfix walks over a binary tree, the binary tree cannot 
be uniquely constructed. 
(d) Depth-first search can be used to find connected components of a graph. 
1.23. Consider the following two functions: 
( )
( )
3
1
2
2 3
 for 0 10,000
 for 10,000
 for 0 100
 for 100
n n
g n
n n
n n
g n
n n
? = =
=
?
=
?
= = ?
=
?
>
?
Which of the following is true? 
(a) ( ) ( ) ( )
1 2
 is 0 g n g n (b) ( ) ( )
3
1
 is 0 g n n
(c) ( ) ( ) ( )
2 1
 is 0 g n g n (d) ( ) ( )
2
 is 0 g n n
GATE CS - 1994
     
1.24. Consider the following heap (figure) in which blank regions are not in use and 
hatched region are in use. 
The sequence of requests for blocks of size 300, 25, 125, 50 can be satisfied if 
we use 
(a) either first fit or best fit policy (any one) 
(b) first fit but not best fit policy 
(c) best fit but first fit policy 
(d) None of the above  
2. Fill in the blanks:
2.1 The number of flip-flops required to construct a binary modulo N counter is 
__________ 
2.2. On the set N of non-negative integers, the binary operation __________ is 
associative and non-commutative. 
2.3. Amongst the properties {reflexivity, symmetry, anti-symmetry, transitivity} the 
relation R ={(x,y) 
2
N x y ? ? } satisfies __________ 
2.4. The number of subsets { } 1,2, n K with odd cardinality is __________
2.5. The number of edges in a regular graph of degree d and n vertices is _________ 
2.6. The probability of an event B is 
1
. P The probability that events A and B occur 
together is 
2
P while the probability that A and B occur together is 
3
. P The 
probability of the event A in terms of 
1 2 3
, and P P P is __________ 
2.7. Consider n-bit (including sign bit) 2’s complement representation of integer 
number. The range of integer values, N, that can be represented is __________ 
= N = __________ 
2.8. Let A, B and C be independent events which occur with probabilities 0.8, 0.5 and 
0.3 respectively. The probability of occurrence of at least one of the event is 
__________ 
2.9. The Hasse diagrams of all the lattices with up to four elements are __________ 
(write all the relevant Hasse diagrams). 
Increasing addresses 
50 150 300 350 600