GATE CSE 1995 Previous-Year Questions (PYQs)
Section - A (100 Marks)
This question has 25 parts. Each part carries 1 mark. Choose the correct alternative for each part.
(25 x 1)
Question 1.
A single instruction to clear the lower four bits of the accumulator in 8085 assembly language?
(a) XRI OFH
(b) ANI FOH
(c) XRI FOH
(d) ANI OFH
Question 2.
Which or 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
Question 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
Question 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
Question 5.
Merge sort uses
(a) Divide and conquer strategy
(b) Backtracking approach
(c) Heuristic search
(d) Greedy approach
Question 6.
The principle of locality justifies the use of
(a) interrupts
(b) DMA
(c) Polling
(d) Cache Memory
Question 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
(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
Question 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)
Question 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) (L.D)*
(d) L.(L.D)*
Question 10.
Consider a grammar with the following productions
S → aαb|bαc|aB
S → αS|b
S → αbb|ab
bα → bdb|b
The above grammar is:
(a) Context-free
(b) Regular
(c) Context-sensitive
(d) LR(k)
Question 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
Question 12.
What is the distance of the following code?
000000, 010101,101010, 000111, 011001, 111111
(a) 2
(b) 3
(c) 4
(d) 1
Question 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. <>
(a) I
(b) II
(c) III
(d) All of the above
Question 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
Question 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
Question 16.
For merging two sorted lists of sizes m and n into a sorted list of size m + n, we require comparisons of
(a) O(m)
(b) O(n)
(c) O(m + n)
(d) O(log m + log n)
Question 17.
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:
(a) log2n
(b) n−1
(c) n
(d) 2n
Question 18.
The probability that a number selected at random between 100 and 999 (both inclusive) will not contain the digit 7 is:
(a) \(\frac{16}{25}\)
(b) \(\left(\frac9{10}\right)^3\)
(c) \(\frac{27}{75}\)
(d) \(\frac{18}{25}\)
Question 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
Question 20.
The number of elements in the power set P(S) of the set S={{Φ},1,{2,3}} is:
(a) 2
(b) 4
(c) 8
(d) None of the above
Question 21.
In the interval [0,π], the equation x = cos x has
(a) No solution
(b) Exactly one solution
(c) Exactly two solutions
(d) An infinite number of solutions
Question 22.
If at every point of a certain curve, the slope of the tangent equals \(\frac{-2x}y\) the curve is
(a) a straight line
(b) a parabola
(c) a circle
(d) an ellipse
Question 23.
The value of k for which 4x2 – 8xy + ky2 = 0 does not represent a pair of straight lines (both passing through the origin) is:
(a) 0
(b) 2
(c) 9
(d) 3
Question 24.
The rank of the following (n+1)×(n+1) matrix, where a is a real number is
(a) 1
(b) 2
(c) n
(d) Depends on the value of a
Question 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
This question has 25 parts. Each part carries 2 Marks. Choose the correct alternative for each part.
(25 x 2)
Question 26.
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
Question 27.
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
(c) 12 address, 16 data lines
(d) 12 address, 12 data lines
Question 28.
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
Question 29.
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) \(\sqrt2\)
(c) Run-time error
(d) None of the above
Question 30.
What values of A, B, C and D satisfy the following simultaneous Boolean equations? \(\overline A+AB=0,\;\;AB=AC,\;\;\\AB+A\overline C+CD=\overline{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
Question 31.
The sequence …………… is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for ……………………. unit(s) of time.
Job | Arrival | Burst time |
1 | 0.0 | 9 |
2 | 0.6 | 5 |
3 | 1.0 | 1 |
(a) {3,2,1},1
(b) {2,1,3},0
(c) {3,2,1},0
(d) {1,2,3},5
Question 32.
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 records per page with 1 free main memory frame is recorded as follows. What is the number of page faults?
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370
(a) 13
(b) 8
(c) 7
(d) 10
Question 33.
If the cube roots of unity are 1, ω and ω2, then the roots of the following equation are (x-1)3 + 8 = 0
(a) -1, 1 + 2ω, 1 + 2ω2
(b) 1, 1 – 2ω, 1 – 2ω2
(c) -1, 1 – 2ω, 1 – 2ω2
(d) -1, 1 + 2ω, -1 + 2ω2
Question 34.
A language with string manipulation facilities uses the following operations
head(s): first character of a string
tail(s): all but the first character of a string concat(s1,s2):s1 s2
for the string acbc what will be the output of concat(head(s), head(tail(tail(s))))
(a) ac
(b) bc
(c) ab
(d) cc
Question 35.
A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar
S → xxW {print”1″}
S → y {print”2″}
W → Sz {print”3″}
What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?
(a) 23131
(b) 11233
(c) 11231
(d) 33211
Question 36.
A variant record in Pascal is defined by
type varirec = record
number : integer;
case (var1,var2) of
var1: (x,y : integer);
var2: (p,q: real)
end
end
Suppose an array of 100 records was declared on a machine which uses 4 bytes for an integer and 8 bytes for a real. How much space would the compiler have to reserve for the array?
(a) 2800
(b) 2400
(c) 2000
(d) 1200
Question 37.
The number of 1’s in the binary representation of
(3*4096 + 15*256 + 5*16 + 3) are:
(a) 8
(b) 9
(c) 10
(d) 12
Question 38.
A unit vector perpendicular to both the vectors
a = 2i – 2j + k and b = 1 + j – 2k is:
(a) \(\frac1{\sqrt3}(i+j+k)\)
(b) \(\frac13(i+j-k)\)
(c) \(\frac13(i-j-k)\)
(d) \(\frac1{\sqrt3}(i+j-k)\)
Question 39.
A bag contains 10 white balls and 15 black balls. Two balls are drawn in succession. The probability that one of them is black and the other is white is:
(a) \(\frac23\)
(b) \(\frac45\)
(c) \(\frac12\)
(d) \(\frac21\)
Question 40.
The iteration formula to find the square root of a positive real number b using the Newton Raphson method is
(a) xk+1 = 3(xk + b)/2xk
(b) xk+1 = 3(xk+b)/2xk
(c) xk+1 = xk – 2xk/(\(x_k^2\) + b)
(d) None of the above
Question 41.
In a virtual memory system the address space specified by the address lines of the CUP must be __________ than the physical memory size and _______ than the secondary storage size.
(a) smaller, smaller
(b) smaller, larger
(c) larger, smaller
(d) larger, larger
Question 42.
Let A be the set of all non-singular matrices over real number and let* be the matrix multiplication operation. Then
(a) A is closed under* but < A, *> is not a semigroup
(b) < A, *> is a semigroup but not a monoid
(c) < A, *> is a monoid but not a group
(d) < A, *> is a group but not an abelian group
Question 43.
The solution of differential equation y’’ + 3y’ + 2y = 0 is of the form
(a) C1ex + C2e2x
(b) C1e-x + C2e3x
(c) C1e-x + C2e-2x
(d) C1e-2x + C22-x
Question 44.
If the proposition ¬p ⇒ ν is true, then the truth value of the proposition ¬pV(p⇒q), where ¬is negation, ‘V’ is inclusive or and ⇒ is implication, is
(a) true
(b) multiple valued
(c) false
(d) cannot be determined
Question 45.
Which of the following definitions below generates the same language as L,
where L = {xnyn such that n>=1}?
I. E → xEy|xy
II. xy|(x+xyy+)
III. x+y+
(a) I only
(b) I and II
(c) II and III
(d) II only
Question 46.
The postfix expression for the infix expression
A + B*(C + D)/F + D*E is:
(a) AB + CD + *F/D + E*
(b) ABCD + *F/DE*++
(c) A *B + CD/F *DE++
(d) A + *BCD/F* DE++
Question 47.
Which of the following statements is true?
I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient
III. The worst case complexity for Quicksort is O(n2)
IV. Binary search using a linear linked list is efficient.
(a) I and II
(b) II and III
(c) I and IV
(d) I and III
Question 48.
A finite state machine with the following state table has a single input x and a single out z.
Present state | Next state, z |
|
| x=1 | x=0 |
A | D, 0 | B, 0 |
B | B, 1 | C, 1 |
C | B, 0 | D, 1 |
D | B, 1 | C, 0 |
If the initial state is unknown, then the shortest input sequence to reach the final state C is:
(a) 01
(b) 10
(c) 101
(d) 110
Question 49.
Let ∑ = {0,1}, L = ∑* and R = {0n1n such that n > 0} then the languages L∪R and R are respectively
(a) regular, regular
(b) not regular, regular
(c) regular, not regular
(d) not regular, no regular
Question 50.
A computer system has a 4K word cache organized in block-set-associative manner with 4 blocks per set, 64 words per block. The number of bits in the SET and WORD fields of the main memory address format is:
(a) 15, 40
(b) 6, 4
(c) 7, 2
(d) 4, 6
Question 51.
Consider the following high level program segment. Give the contents of the memory locations for variables W, X, Y and Z after the execution of the program segment. The values of the variables A and B are 5 CH and 92H, respectively. Also indicate error conditions if any.
var
A, B, W, X, Y : unsigned byte;
Z : unsigned integer(each integer is represented by two bytes)
begin
X :=A+B
Y :=abs(bA-b);
W :=A-B
Z :=A*B
End;
Question 52.
(a) Consider the following Pascal function where A and B are non-zero positive integers. What is the value of GET(3,2)?
function GET(A,B:integer);integer;
begin
if B = 0 then
GET:=1
else if A < B then
GET:=0
else
GET:=GET(A-1,B)+GET(A-1,B-1)
end ;
(b) The Pascal procedure given for computing the transpose of an N × N (N>1) matrix A of integers has an error. Find the error and correct it. Assume that the following declaration are made in the main program const
MAXSIZE=20;
type
INTARR=array [1.,MAXSIZE,1..MAXSIZE] of integer;
Procedure TRANSPOSE (var A: INTARR; N : integer);
var
I, J, TMP, integer;
begin
for I:=1 to NO – 1 do
for J:=1 to N do
begin
TMP: = A[I,J];
A[I,J]:=A[J,I];
A(J,I}:=TMP
end
end;
Question 53.
A computer installation has 1000k of main memory. The jobs arrive and finish in the following sequences.
Job 1 requiring 200k arrives
Job 2 requiring 350k arrives
Job 3 requiring 300k arrives
Job 1 finishes
Job 4 requiring 120k arrives
Job 5 requiring 150k arrives
Job 6 requiring 80k arrives
(a) Draw the memory allocation table using Best Fit and First fit algorithms.
(b) Which algorithm performs better for this sequence?
Question 54.
What is the number of binary trees with 3 nodes which when traversed in post order give the sequence A, B, C? Draw all these binary trees.
Question 55.
(a) Determine the number of divisors of 600.
(b) Compute without using power series expansion \(\lim_{x\rightarrow0}\frac{\sin\;x}x\)
Section - B (50 Marks)
Answer any TEN questions.
Question 56.
Construct the LL(1) table for the following grammar.
1. Expr → _Expr
2. Expr → (Expr)
3. Expr → Var Expr Tail
4. ExprTail → _Expr
5. ExprTail → λ
6. Var → Id Var Tail
7. VarTail → (Expr)
8. VarTail → λ
9. Goal → Expr$
Question 56.
C