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

 Page 1


GATE CS - 1995
  
SECTION - A 
1. This question has 25 parts. Each part carries 1 mark. Choose the correct
alternative for each part.
1.1 A single instruction to clear the lower four bits of the accumulator in 8085 assebly 
language? 
(a) XRI OFH (b) ANI FOH (c) XRI FOH (d) ANI OFH 
1.2 Which of the following statements is true?
(a) ROM is a Read/Write memory 
(b) PC points to the last instruction that was executed 
(c) Stack works on the principle of LIFO 
(d) All instructions affect the flags 
1.3 In a vectored interrupt  
(a) the branch address is assigned to a fixed location in memory 
(b) the interrupt source supplies the branch information to the processor through 
an interrupt vector  
(c) the branch address is obtained from a register in the processor 
(d) none of the above 
1.4 In the following Pascal program segment, what is the value of X after the 
execution of the program segment? 
X:=-10; Y:=20; 
If X > Y then if X < 0 then X:=abs(X) else X:=2*X; 
(a) 10 (b) -20 (c) -10  (d) None 
1.5 Merge sort uses 
(a) Divide and conquer strategy (b) Backtracking approach 
(c) Heuristic search  (d) Greedy approach 
1.6 The principle of locality justifies the use of 
(a) interrupts  (b) DMA 
(c) Polling (d) Cache Memory 
1.7 In a paged segmented scheme of memory management, the segment table itself 
must have a page table because  
(a) the segment table is often too large to fit in one page 
(b) each segment is spread over a number of pages 
Page 2


GATE CS - 1995
  
SECTION - A 
1. This question has 25 parts. Each part carries 1 mark. Choose the correct
alternative for each part.
1.1 A single instruction to clear the lower four bits of the accumulator in 8085 assebly 
language? 
(a) XRI OFH (b) ANI FOH (c) XRI FOH (d) ANI OFH 
1.2 Which of the following statements is true?
(a) ROM is a Read/Write memory 
(b) PC points to the last instruction that was executed 
(c) Stack works on the principle of LIFO 
(d) All instructions affect the flags 
1.3 In a vectored interrupt  
(a) the branch address is assigned to a fixed location in memory 
(b) the interrupt source supplies the branch information to the processor through 
an interrupt vector  
(c) the branch address is obtained from a register in the processor 
(d) none of the above 
1.4 In the following Pascal program segment, what is the value of X after the 
execution of the program segment? 
X:=-10; Y:=20; 
If X > Y then if X < 0 then X:=abs(X) else X:=2*X; 
(a) 10 (b) -20 (c) -10  (d) None 
1.5 Merge sort uses 
(a) Divide and conquer strategy (b) Backtracking approach 
(c) Heuristic search  (d) Greedy approach 
1.6 The principle of locality justifies the use of 
(a) interrupts  (b) DMA 
(c) Polling (d) Cache Memory 
1.7 In a paged segmented scheme of memory management, the segment table itself 
must have a page table because  
(a) the segment table is often too large to fit in one page 
(b) each segment is spread over a number of pages 
GATE CS - 1995
  
(c) segment tables point to page table and not to the physical locations of the 
segment 
(d) the processor’s description base register points to a page table 
1.8 Which of the following page replacement algorithms suffers from Belady’s 
anamoly? 
(a) Optimal replacement   (b) LRU 
(c) FIFO   (d) Both (a) and (c) 
1.9 In some programming languages, an identifier is permitted to be a letter 
following by any number of letters or digits. If L and D denote the sets of letters 
and digits respectively, which of the following expressions defines an identifier? 
(a) ( ) L D
+
? (b) ( )
*
L L D ? (c) ( )
*
. LD (d) ( )
*
. . L LD
1.10 Consider a grammar with the following productions 
S a b b c aB
S S b
S bb ab
S bdb b
? ? ?
??
??
??
The above grammar is: 
(a) Context free (b) Regular 
(c) Context sensitive  (d) LR(k) 
1.11 What are x and y in the following macro definition? 
macro Add x,y 
Load y 
Mul x 
Store y 
end macro 
(a) Variables (b) Identifiers  
(c) Actual parameters (d) Formal parameters 
1.12  What is the distance of the following code 000000, 010101, 000111, 011001, 
111111? 
(a) 2 (b) 3 (c) 4  (d) 1 
1.13 Which of the following strings can definitely be said to be tokens without looking 
at the next input character while compiling a Pascal program? 
I. begin II. program III. <>
Page 3


GATE CS - 1995
  
SECTION - A 
1. This question has 25 parts. Each part carries 1 mark. Choose the correct
alternative for each part.
1.1 A single instruction to clear the lower four bits of the accumulator in 8085 assebly 
language? 
(a) XRI OFH (b) ANI FOH (c) XRI FOH (d) ANI OFH 
1.2 Which of the following statements is true?
(a) ROM is a Read/Write memory 
(b) PC points to the last instruction that was executed 
(c) Stack works on the principle of LIFO 
(d) All instructions affect the flags 
1.3 In a vectored interrupt  
(a) the branch address is assigned to a fixed location in memory 
(b) the interrupt source supplies the branch information to the processor through 
an interrupt vector  
(c) the branch address is obtained from a register in the processor 
(d) none of the above 
1.4 In the following Pascal program segment, what is the value of X after the 
execution of the program segment? 
X:=-10; Y:=20; 
If X > Y then if X < 0 then X:=abs(X) else X:=2*X; 
(a) 10 (b) -20 (c) -10  (d) None 
1.5 Merge sort uses 
(a) Divide and conquer strategy (b) Backtracking approach 
(c) Heuristic search  (d) Greedy approach 
1.6 The principle of locality justifies the use of 
(a) interrupts  (b) DMA 
(c) Polling (d) Cache Memory 
1.7 In a paged segmented scheme of memory management, the segment table itself 
must have a page table because  
(a) the segment table is often too large to fit in one page 
(b) each segment is spread over a number of pages 
GATE CS - 1995
  
(c) segment tables point to page table and not to the physical locations of the 
segment 
(d) the processor’s description base register points to a page table 
1.8 Which of the following page replacement algorithms suffers from Belady’s 
anamoly? 
(a) Optimal replacement   (b) LRU 
(c) FIFO   (d) Both (a) and (c) 
1.9 In some programming languages, an identifier is permitted to be a letter 
following by any number of letters or digits. If L and D denote the sets of letters 
and digits respectively, which of the following expressions defines an identifier? 
(a) ( ) L D
+
? (b) ( )
*
L L D ? (c) ( )
*
. LD (d) ( )
*
. . L LD
1.10 Consider a grammar with the following productions 
S a b b c aB
S S b
S bb ab
S bdb b
? ? ?
??
??
??
The above grammar is: 
(a) Context free (b) Regular 
(c) Context sensitive  (d) LR(k) 
1.11 What are x and y in the following macro definition? 
macro Add x,y 
Load y 
Mul x 
Store y 
end macro 
(a) Variables (b) Identifiers  
(c) Actual parameters (d) Formal parameters 
1.12  What is the distance of the following code 000000, 010101, 000111, 011001, 
111111? 
(a) 2 (b) 3 (c) 4  (d) 1 
1.13 Which of the following strings can definitely be said to be tokens without looking 
at the next input character while compiling a Pascal program? 
I. begin II. program III. <>
GATE CS - 1995
  
(a) I (b) II (c) III 
(d) All of the above 
1.14 A linker is given object modules for a set of programs that were compiled 
separately. What information need to be included in an object module?  
(a) Object code 
(b) Relocation bits 
(c) Names and locations of all external symbols defined in the object module 
(d) Absolute addresses of internal symbols 
1.15 Which scheduling policy is most suitable for a time shared operating system? 
(a) Shortest Job First   (b) Round Robin 
(c) First Come First Serve (d) Elevator 
1.16 For merging two sorted lists of sizes m and n into a sorted list of size m+n, we 
required comparisons of 
(a) ( ) O m (b) ( ) O n
(c) ( ) O m n + (d) ( ) log log O m n +
1.17 A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is: 
(a) 
2
log n (b) 1 n- (c) n (d) 2
n
 
1.18 The probability that a number selected at random between 100 and 999 (both 
inclusive) will not contain the digit 7 is: 
(a) 
16
25
(b) 
3
9
10
? ?
? ?
? ?
(c) 
27
75
(d) 
18
25
1.19. Let R be a symmetric and transitive relation on a set A. Then 
(a) R is reflexive and hence an equivalence relation  
(b) R is reflexive and hence a partial order  
(c) R is reflexive and hence not an equivalence relation 
(d) None of the above  
1.20. The number of elements in he power set ( ) P S of the set ( ) ( ) { }
,1, 2,3 S f = is:
(a) 2 (b) 4 (c) 8 
(d) None of the above 
Page 4


GATE CS - 1995
  
SECTION - A 
1. This question has 25 parts. Each part carries 1 mark. Choose the correct
alternative for each part.
1.1 A single instruction to clear the lower four bits of the accumulator in 8085 assebly 
language? 
(a) XRI OFH (b) ANI FOH (c) XRI FOH (d) ANI OFH 
1.2 Which of the following statements is true?
(a) ROM is a Read/Write memory 
(b) PC points to the last instruction that was executed 
(c) Stack works on the principle of LIFO 
(d) All instructions affect the flags 
1.3 In a vectored interrupt  
(a) the branch address is assigned to a fixed location in memory 
(b) the interrupt source supplies the branch information to the processor through 
an interrupt vector  
(c) the branch address is obtained from a register in the processor 
(d) none of the above 
1.4 In the following Pascal program segment, what is the value of X after the 
execution of the program segment? 
X:=-10; Y:=20; 
If X > Y then if X < 0 then X:=abs(X) else X:=2*X; 
(a) 10 (b) -20 (c) -10  (d) None 
1.5 Merge sort uses 
(a) Divide and conquer strategy (b) Backtracking approach 
(c) Heuristic search  (d) Greedy approach 
1.6 The principle of locality justifies the use of 
(a) interrupts  (b) DMA 
(c) Polling (d) Cache Memory 
1.7 In a paged segmented scheme of memory management, the segment table itself 
must have a page table because  
(a) the segment table is often too large to fit in one page 
(b) each segment is spread over a number of pages 
GATE CS - 1995
  
(c) segment tables point to page table and not to the physical locations of the 
segment 
(d) the processor’s description base register points to a page table 
1.8 Which of the following page replacement algorithms suffers from Belady’s 
anamoly? 
(a) Optimal replacement   (b) LRU 
(c) FIFO   (d) Both (a) and (c) 
1.9 In some programming languages, an identifier is permitted to be a letter 
following by any number of letters or digits. If L and D denote the sets of letters 
and digits respectively, which of the following expressions defines an identifier? 
(a) ( ) L D
+
? (b) ( )
*
L L D ? (c) ( )
*
. LD (d) ( )
*
. . L LD
1.10 Consider a grammar with the following productions 
S a b b c aB
S S b
S bb ab
S bdb b
? ? ?
??
??
??
The above grammar is: 
(a) Context free (b) Regular 
(c) Context sensitive  (d) LR(k) 
1.11 What are x and y in the following macro definition? 
macro Add x,y 
Load y 
Mul x 
Store y 
end macro 
(a) Variables (b) Identifiers  
(c) Actual parameters (d) Formal parameters 
1.12  What is the distance of the following code 000000, 010101, 000111, 011001, 
111111? 
(a) 2 (b) 3 (c) 4  (d) 1 
1.13 Which of the following strings can definitely be said to be tokens without looking 
at the next input character while compiling a Pascal program? 
I. begin II. program III. <>
GATE CS - 1995
  
(a) I (b) II (c) III 
(d) All of the above 
1.14 A linker is given object modules for a set of programs that were compiled 
separately. What information need to be included in an object module?  
(a) Object code 
(b) Relocation bits 
(c) Names and locations of all external symbols defined in the object module 
(d) Absolute addresses of internal symbols 
1.15 Which scheduling policy is most suitable for a time shared operating system? 
(a) Shortest Job First   (b) Round Robin 
(c) First Come First Serve (d) Elevator 
1.16 For merging two sorted lists of sizes m and n into a sorted list of size m+n, we 
required comparisons of 
(a) ( ) O m (b) ( ) O n
(c) ( ) O m n + (d) ( ) log log O m n +
1.17 A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is: 
(a) 
2
log n (b) 1 n- (c) n (d) 2
n
 
1.18 The probability that a number selected at random between 100 and 999 (both 
inclusive) will not contain the digit 7 is: 
(a) 
16
25
(b) 
3
9
10
? ?
? ?
? ?
(c) 
27
75
(d) 
18
25
1.19. Let R be a symmetric and transitive relation on a set A. Then 
(a) R is reflexive and hence an equivalence relation  
(b) R is reflexive and hence a partial order  
(c) R is reflexive and hence not an equivalence relation 
(d) None of the above  
1.20. The number of elements in he power set ( ) P S of the set ( ) ( ) { }
,1, 2,3 S f = is:
(a) 2 (b) 4 (c) 8 
(d) None of the above 
GATE CS - 1995
  
1.21. In the interval 0,p ? ?
? ?
 the equation cos x x = has
(a) No solution  (b) Exactly one solution 
(c) Exactly two solutions (d) An infinite number of solutions 
1.22. If at every point of a certain curve, the slope of the tangent equals 
2x
y
-
the 
curve is 
(a) a straight line (b) a parabola 
(c) a circle (d) an ellipse 
1.23. The value of k for which 
2 2
4 8 0 x xy ky - + = does not represent a pair of straight 
lines (both passing through the origin) is: 
(a) 0 (b) 2 (c) 9 (d) 3 
1.24. The rank of the following ( ) ( ) 1 1 n n + × + matrix, where a is a real number is
2
2
2
1
1
1
n
n
n
a a a
a a a
a a a
? ?
? ?
? ?
? ?
? ?
? ?
? ?
? ?
L
L
M M M M
M M M M
L
(a) 1 (b) 2 (c) n 
(d) Depends on the value of a 
1.25 The minimum number of edges in a connected cyclic graph on n vertices is: 
(a) n - 1 (b) n (c) n + 1 
(d) None of the above 
2. This question has 25 parts. Each part carries 2 Marks. Choose the correct
alternative for each part.
2.1 A sequence of two instructions that multiplies the contents of the DE register pair 
by 2 and stores the result in the HL register pair (in 8085 assembly language) is: 
(a) XCHG and DAD B   (b) XTHL and DAD H  
(c) PCHL and DAD D   (d) XCHG and DAD H 
2.2. The capacity of a memory unit is defined by the number of words multiplied by 
the number of bits/word. How many separate address and data lines are needed 
for a memory of 4 K × 16? 
(a) 10 address, 16 data lines (b) 11 address, 8 data lines 
Page 5


GATE CS - 1995
  
SECTION - A 
1. This question has 25 parts. Each part carries 1 mark. Choose the correct
alternative for each part.
1.1 A single instruction to clear the lower four bits of the accumulator in 8085 assebly 
language? 
(a) XRI OFH (b) ANI FOH (c) XRI FOH (d) ANI OFH 
1.2 Which of the following statements is true?
(a) ROM is a Read/Write memory 
(b) PC points to the last instruction that was executed 
(c) Stack works on the principle of LIFO 
(d) All instructions affect the flags 
1.3 In a vectored interrupt  
(a) the branch address is assigned to a fixed location in memory 
(b) the interrupt source supplies the branch information to the processor through 
an interrupt vector  
(c) the branch address is obtained from a register in the processor 
(d) none of the above 
1.4 In the following Pascal program segment, what is the value of X after the 
execution of the program segment? 
X:=-10; Y:=20; 
If X > Y then if X < 0 then X:=abs(X) else X:=2*X; 
(a) 10 (b) -20 (c) -10  (d) None 
1.5 Merge sort uses 
(a) Divide and conquer strategy (b) Backtracking approach 
(c) Heuristic search  (d) Greedy approach 
1.6 The principle of locality justifies the use of 
(a) interrupts  (b) DMA 
(c) Polling (d) Cache Memory 
1.7 In a paged segmented scheme of memory management, the segment table itself 
must have a page table because  
(a) the segment table is often too large to fit in one page 
(b) each segment is spread over a number of pages 
GATE CS - 1995
  
(c) segment tables point to page table and not to the physical locations of the 
segment 
(d) the processor’s description base register points to a page table 
1.8 Which of the following page replacement algorithms suffers from Belady’s 
anamoly? 
(a) Optimal replacement   (b) LRU 
(c) FIFO   (d) Both (a) and (c) 
1.9 In some programming languages, an identifier is permitted to be a letter 
following by any number of letters or digits. If L and D denote the sets of letters 
and digits respectively, which of the following expressions defines an identifier? 
(a) ( ) L D
+
? (b) ( )
*
L L D ? (c) ( )
*
. LD (d) ( )
*
. . L LD
1.10 Consider a grammar with the following productions 
S a b b c aB
S S b
S bb ab
S bdb b
? ? ?
??
??
??
The above grammar is: 
(a) Context free (b) Regular 
(c) Context sensitive  (d) LR(k) 
1.11 What are x and y in the following macro definition? 
macro Add x,y 
Load y 
Mul x 
Store y 
end macro 
(a) Variables (b) Identifiers  
(c) Actual parameters (d) Formal parameters 
1.12  What is the distance of the following code 000000, 010101, 000111, 011001, 
111111? 
(a) 2 (b) 3 (c) 4  (d) 1 
1.13 Which of the following strings can definitely be said to be tokens without looking 
at the next input character while compiling a Pascal program? 
I. begin II. program III. <>
GATE CS - 1995
  
(a) I (b) II (c) III 
(d) All of the above 
1.14 A linker is given object modules for a set of programs that were compiled 
separately. What information need to be included in an object module?  
(a) Object code 
(b) Relocation bits 
(c) Names and locations of all external symbols defined in the object module 
(d) Absolute addresses of internal symbols 
1.15 Which scheduling policy is most suitable for a time shared operating system? 
(a) Shortest Job First   (b) Round Robin 
(c) First Come First Serve (d) Elevator 
1.16 For merging two sorted lists of sizes m and n into a sorted list of size m+n, we 
required comparisons of 
(a) ( ) O m (b) ( ) O n
(c) ( ) O m n + (d) ( ) log log O m n +
1.17 A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is: 
(a) 
2
log n (b) 1 n- (c) n (d) 2
n
 
1.18 The probability that a number selected at random between 100 and 999 (both 
inclusive) will not contain the digit 7 is: 
(a) 
16
25
(b) 
3
9
10
? ?
? ?
? ?
(c) 
27
75
(d) 
18
25
1.19. Let R be a symmetric and transitive relation on a set A. Then 
(a) R is reflexive and hence an equivalence relation  
(b) R is reflexive and hence a partial order  
(c) R is reflexive and hence not an equivalence relation 
(d) None of the above  
1.20. The number of elements in he power set ( ) P S of the set ( ) ( ) { }
,1, 2,3 S f = is:
(a) 2 (b) 4 (c) 8 
(d) None of the above 
GATE CS - 1995
  
1.21. In the interval 0,p ? ?
? ?
 the equation cos x x = has
(a) No solution  (b) Exactly one solution 
(c) Exactly two solutions (d) An infinite number of solutions 
1.22. If at every point of a certain curve, the slope of the tangent equals 
2x
y
-
the 
curve is 
(a) a straight line (b) a parabola 
(c) a circle (d) an ellipse 
1.23. The value of k for which 
2 2
4 8 0 x xy ky - + = does not represent a pair of straight 
lines (both passing through the origin) is: 
(a) 0 (b) 2 (c) 9 (d) 3 
1.24. The rank of the following ( ) ( ) 1 1 n n + × + matrix, where a is a real number is
2
2
2
1
1
1
n
n
n
a a a
a a a
a a a
? ?
? ?
? ?
? ?
? ?
? ?
? ?
? ?
L
L
M M M M
M M M M
L
(a) 1 (b) 2 (c) n 
(d) Depends on the value of a 
1.25 The minimum number of edges in a connected cyclic graph on n vertices is: 
(a) n - 1 (b) n (c) n + 1 
(d) None of the above 
2. This question has 25 parts. Each part carries 2 Marks. Choose the correct
alternative for each part.
2.1 A sequence of two instructions that multiplies the contents of the DE register pair 
by 2 and stores the result in the HL register pair (in 8085 assembly language) is: 
(a) XCHG and DAD B   (b) XTHL and DAD H  
(c) PCHL and DAD D   (d) XCHG and DAD H 
2.2. The capacity of a memory unit is defined by the number of words multiplied by 
the number of bits/word. How many separate address and data lines are needed 
for a memory of 4 K × 16? 
(a) 10 address, 16 data lines (b) 11 address, 8 data lines 
GATE CS - 1995
     (c) 12 address, 16 data lines (d) 12 
address, 12 data lines 
2.3. Assume that X and Y are non-zero positive integers. What does the following 
Pascal program segment do? 
while X <>Y do 
if  X > Y then 
 X:=X – Y 
else 
 Y:=Y – X; 
    write(X); 
(a) Computes the LCM of two numbers 
(b) Divides the larger number by the smaller number 
(c) Computes the GCD of two numbers 
(d) None of the above  
2.4. What is the value of X printed by the following program? 
program COMPUTE (input, output); 
var 
X:integer; 
procedure FIND (X:real); 
begin 
X:=sqrt(X); 
end; 
begin 
X:=2 
Find(X) 
Writeln(X) 
end 
(a) 2 (b) 2 
(c) Run time error (d) None of the above 
2.5. What values of A, B, C and D satisfy the following simultaneous Boolean 
equations? 
0, , A AB AB AC AB AC CD CD + = = + + =
(a) A = 1, B = 0, C = 0, D = 1 (b) A = 1, B = 1, C = 0, D = 0 
(c) A = 1, B = 0, C = 1, D = 1 (d) A = 1, B = 0, C = 0, D = 0