Gate (CS) 2001 Paper without Solution | GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Computer Science Engineering (CSE) PDF Download

 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 correct