GATE CSE 1996 Previous-Year Questions (PYQs) with Solution

Let’s Learn about GATE CSE 1996 Previous-Year Questions.

GATE CSE 1996 Previous-Year Questions (PYQs)

Section - A (100 Marks)

Write in your answer book the correct or the most appropriate answer to the following multiple choice questions by writing the corresponding letter a, b, c or d against the sub-question number.

(25 x 1 = 25)

Question 1.

Let A and B be sets and let A^c and B^c denote the complements of the sets A and B. the set (a – b)∪(b – a)∪(a ∩ b) is equal to.

(a) A ∪ B

(b) A^c ∪ B^c

(d) A^c ∩ B^c

Question 2.

Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x divides y. Number of edge as in the Hasse diagram of (X,≤) is

(a) 3

(b) 4

(d) None of the above

Question 3.

Suppose X and Y are sets and |X| and |Y| are their respective cardinalities. It is given that there are exactly 97 functions from X to Y. from this one can conclude that

(a) |X|=1, |Y|=97

(b) |X|=97, |Y|=1

(d) None of the above

Question 4.

Which of the following statements is false?

(a) The set of rational numbers is an abelian group under addition.

(b) The set of integers in an abelian group under addition.

(d) The set of real numbers excluding zero in an abelian group under multiplication.

Question 5.

Two dice are thrown simultaneously. The probability that at least one of them will have 6 facing up is

(a) \(\frac1{36}\)

(b) \(\frac1{3}\)

(d) \(\frac{11}{36}\)

Question 6.

The formula used to compute an approximation for the second derivative of a function f at a point X₀ is

(a) \(\frac{f\left(x_0+h\right)+f\left(x_0-h\right)}2\)

(b) \(\frac{f\left(x_0+h\right)-f\left(x_0-h\right)}{2h}\)

(d) \(\frac{f\left(x_0+h\right)-2f\left(x_0\right)+f\left(x_0-h\right)}{h^2}\)

Question 7.

Let Ax = b be a system of linear equations where A is an m × n matrix and b is a m × 1 column vector and X is a n × 1 column vector of unknows. Which of the following is false?

(a) The system has a solution if and only if, both A and the augmented matrix [A b] have the same rank.

(b) If m < n and b is the zero vector, then the system has infinitely many solutions.

(d) The system will have only a trivial solution when m = n, b is the zero vector and rank (A) = n.

Question 8.

Which two of the following four regular expressions are equivalent? (ε is the empty string).

(i) (00) * (ε + 0)

(ii) (00)*

(iii) 0*

(iv) 0(00)*

(a) (i) and (ii)

(b) (ii) and (iii)

(d) (iii) and (iv)

Question 9.

Which of the following statements is false?

(a) The Halting problem of Turing machines is undecidable.

(b) Determining whether a context-free grammar is ambiguous is undecidbale.

(d) Given two regular grammars G₁and G₂it is undecidable whether L(G₁) = L(G ₂).

Question 10.

Let L ⊆ Σ* where Σ = {a, b}. which of the following is true?

(a) L = {x|x has an equal number of a’s and b’s} is regular

(b) L = {aⁿbⁿ|n≥1 } is regular

(d) L = {a^mbⁿ| m≥1, n≥1} is regular

Question 11.

Which of the following is false?

(a) \(100n\;\log\left(n\right)\;=\;O\left(\frac{n\log\left(n\right)}{100}\right)\)

(b) \(\sqrt{\log\;n}\;=O\left(\log\;\log\;n\right)\)

(d) \(2n\neq O(nk)\)

Question 12.

Consider the following statements:

(i) First-in-first out types of computations are efficiently supported by STACKS.

(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.

(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.

(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

(a) (ii) and (iii) are true

(b) (i) and (ii) are true

(d) (ii) and (iv) are true

Question 13.

An advantage of chained hash table (external hashing) over the open addressing scheme is

(a) Worst case complexity of search operations is less?

(b) Space used is less

(d) None of the above

Question 14.

In the balanced binary tree in Fig. given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?

(a) 1

(b) 3

(d) 8

Question 15.

Which of the following sequences denotes the post order traversal sequence of the tree of question14?

(a) f e g c d b a

(b) g c b d a f e

(d) f e d g c b a

Question 16.

Relative mode of addressing is most relevant to writing

(a) coroutines

(b) position – independent code

(d) interrupt handlers

Question 17.

The pass numbers for each of the following activities

(i) object code generation

(ii) literals added to literal table

(iii) listing printed

(iv) address resolution of local symbols

That occur in a two pass assembler respectively are

(a) 1, 2, 1, 2

(b) 2, 1, 2, 1

(d) 1, 2, 2, 2

Question 18.

The process state transition diagram in Fig. is representative of

(a) a batch operating system

(b) an operating system with a preemptive scheduler

(d) a uni-programmed operating system.

Question 19.

A critical section is a program segment

(a) which should run in a certain specified amount of time

(b) which avoids deadlocks

(d) which must be enclosed by a pair of semaphore operations, P and V

Question 20.

Which of the following is an example of spooled device?

(a) A line printer used to print the output of a number of jobs.

(b) A terminal used to enter input data to a running program.

(d) A graphic display device.

Question 21.

A ROM is sued to store the table for multiplication of two 8-bit unsigned integers. The size of ROM required is

(a) 256 × 16

(b) 64K × 8

(d) 64K × 16

Question 22.

Number of machine cycles required for RET instruction in 8085 microprocessor is

(a) 1

(b) 2

(d) 5

Question 23.

Both’s algorithm for integer multiplication gives worst performance when the multiplier pattern is

(a) 101010 ……1010

(b) 100000 ……0001

(d) 011111 ……1110

Question 24.

For the daisy chain scheme of connecting I/O devices, which of the following statements is true?

(a) It gives non-uniform priority to various devices.

(b) It gives uniform priority to all devices.

(d) It requires a separate interrupt pin on the processor for each device.

Question 25.

Consider the following floating-point number representation.

GATE CSE 1996 Previous-Year Questions 25

The exponent is in 2’s complement representation and mantissa is in the sign magnitude representation. The range of the magnitude of the normalized numbers in this representation is

(a) 0 to 1

(b) 0.5 to 1

(d) 0.5 to (1 – 2 ^-23)

Write in your answer book the correct or the most appropriate answer to the following multiple choice questions by writing the corresponding letter a, b, c or d against the sub-question number.

(25 x 2 = 50)

Question 26.

Let R denotes the set of real numbers. Let f:R×R → R×R be a bijective function defined by f(x,y)=(x+y,x-y). the inverse function of f is given by

(a) \(f^{-1}\left(x,y\right)=\left(\frac1{x+y},\frac1{x-y}\right)\)

(b) \(f^{-1}\left(x,y\right)=\left(x-y,x+y\right)\)

(d) \(f^{-1}\left(x,y\right)=\left(2\left(x-y\right),3\left(x+y\right)\right)\)

Question 27.

Let R be a non-empty relation on a collection of sets defined by A R B if and only if A∩B=φ. Then, (pick the true statement)

(a) R is reflexive and transitive

(b) R is symmetric and not transitive

Question 28.

Which of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one way implication and ↔ as two way implication.

(a) (x → y) ∧ x) → y

(b) ((~ x → y)∧(~ x ∧ ~ y)) → x

(d) ((x ∨ y) ↔ (~ x → ~ y))

Question 29.

Which one of the following is false?

(a) The set of all bijective functions on a finite set forms a group under function composition.

(b) The set {1,2, ……., p –1} forms a group under multiplication mod p where p is a prime number.

(d) A subset s ≠ φ of G is a subgroup of the group <G, *> if and only if for any pair of elements a, b ∈ s, a* b^-1 ∈ s.

Question 30.

The Newton-Raphson iteration formula for finding \(\sqrt[3]c\) where c > 0 is,

(a) \(x_{n+1}=\frac{2x_n^3+\sqrt[3]c}{3x_n^2}\)

(b) \(x_{n+1}=\frac{2x_n^3-\sqrt[3]c}{3x_n^2}\)

(d) \(x_{n+1}=\frac{2x_n^3-c}{3x_n^2}\)

Question 31.

The matrices \(\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}\) and \(\begin{bmatrix}a&0\\0&b\end{bmatrix}\) commute under multiplication

(a) if a = b or θ = nπ, is an integer

(b) always

(d) if a cos θ ≠ b sin θ

Question 32.

The probability that top and bottom cards of a randomly shuffled deck are both aces in

(a) \(\frac4{52}\times\frac4{52}\)

(b) \(\frac4{52}\times\frac3{52}\)

(d) \(\frac4{52}\times\frac4{51}\)

Question 33.

If L₁ and L₂ are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

(a) L₁, L₂

(b) L₁ ∩ L₂

(d) L₁ ∪ L₂

Question 34.

Define a context free languages L ⊆ {0,1}^*

init (L) = {u/uv ∈ L for some ν in {{0,1}} (in other words, init(L) is the set of prefixes of L)

Let L {w/w is nonempty and has on equal number of 0’s and 1’s Then init (L) is

(a) the set of all binary strings with unequal number of 0’s and 1’s

(b) the set of all binary strings including the null string

(d) None of the above

Question 35.

The grammar whose productions are

<stmt> → if id then <stmt>

<stmt> → if id then <stmt> else <stmt>

<stmt> → id:=id

is ambiguous because

(a) the sentence

if a then if b then c:=d

(b) the left most and right most derivations of the sentence

if a then if b then c:=d

give rise top different parse trees

if a then if b then c:=d else c:=f

has more than two parse trees

(d) the sentence

if a then if then c:=d else c:=f

has two parse trees

Question 36.

The minimum number of interchanges needed to convert the array 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70

into a heap with the maximum element at the root is

(a) 0

(b) 1

(d) 3

Question 37.

The recurrence relation

\(T\left(1\right)=2\)

\(T\left(n\right)=3T\left(\frac n4\right)+n\)

has the solution, T(n) equal to

(a) \(O\left(n\right)\)

(b) \(O\left(\log\;n\right)\)

(d) None of the above

Question 38.

The average number of key comparisons done on a successful sequential search in list of length it is

(a) \(\log\;n\)

(b) \(\frac{n-1}2\)

(d) \(\frac{n+1}2\)

Question 39.

A binary search tree is generated by inserting in order the following integers:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is

(a) (4, 7)

(b) (7, 4)

(d) (3, 8)

Question 40.

Quick-sort is run on two inputs shown below to sort in ascending order

(i) 1,2,3 ……n

(ii) n, n – 1, n – 2, …… 2, 1

Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

(a) C₁ < C₂

(b) C₁ > C₂

(d) we cannot say anything for arbitrary n.

Question 41.

Which of the following macros can put a macro assembler into an infinite loop?

(i). MACRO M1, X

IF EQ, X: if X=0 then ….

M1 X + 1

ENDC

IF NE, X: if X ≠ O then ……

WORD X: address (X) is stored here

ENDC

ENDM

(ii). MACRO M2,X

IF EQ, X

M2 X

ENDC

IF NE, X

WORD X + 1

ENDC

ENDM

(a) (ii) only

(b) (i) only

(d) None of the above

Question 42.

The correct matching for the following pairs is

(A). Activation record	(1). Linking loader
(B). Location counter	(2). Garbage collection
(C). Reference counts	(3). Subroutine call
(D). Address relocation	(4). Assembler

(a) A – 3 B – 4 C – 1 D – 2

(b) A – 4 B – 3 C – 1 D – 2

(d) A – 3 B – 4 C – 2 D – 1

Question 43.

A 1000 Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes 200 Kbytes and 260 Kbytes respectively. The smallest allocation request in Kbytes that could be denied is for

(a) 151

(b) 181

(d) 541

Question 44.

A solution to the Dining Philosophers Problem which avoids deadlock is;

(a) ensure that all philosophers pick up the left fork before the right fork

(b) ensure that all philosophers pick up the right fork before the left fork

(c) ensure that one particular philosopher picks up the left fork before the right fork, and that all other philosophers pick up the right fork before the left fork

(d) None of the above

Question 45.

Four jobs to be executed on a single processor system arrive at time 0⁺ in the order A, B, C, D. Their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is

(a) 10

(b) 4

(d) 9

Question 46.

Consider the circuit in Fig., which has a four-bit binary number b₃b₂b₁b₀ as input and a five-bit binary number d₄d₃d₂d₁d₀ as output. The circuit implements:

GATE CSE 1996 Previous-Year Questions 46

(a) Binary to Hex conversion

(b) Binary to BCD conversion

(d) Binary to radix-12 conversion.

Question 47.

Consider the circuit in Fig. f implements

(a) \(\overline A\;\overline B\;C\;+\;\overline AB\;\overline C\;+\;ABC\)

(b) \(A\;+\;B\;+\;C\)

(d) \(AB\;+\;BC\;+\:CA\)

Question 48.

Consider the following state table in Fig. for a sequential machine. The number of states in the minimized machine will be

GATE CSE 1996 Previous-Year Questions 48

(a) 4

(b) 3

(d) 1

Question 49.

What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given in Fig.

(a) \(B\overline D\;+\;\overline BD\)

(b) \(\left(B+\overline C+D\right)\left(\overline B+C+\overline D\right)\)

(d) \(\left(B+\overline D\right)\left(\overline B+D\right)\)

Question 50.

A microprogram control unit is required to generate a total of 25 control signals. Assume that during any microinstruction, at most two control signals are active. Minimum number of bits required in the control word to generate the required control signals will be

(a) 2

(b) 25

(d) 12

Question 51.

Let f be a function defined by

Find the values for the constants a; b; c and d so that f is continuous and differentiable everywhere on the real line.

Question 52.

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.

(a) 61 52 14 17 40 43

(b) 2 3 50 40 60 43

(d) 81 61 52 14 41 43

(e) 17 77 27 66 18 43

Question 53.

A logic network has two data inputs A and B, and two control inputs C₀ and C₁. It implements the function F according to the following table.

C₁ C₂	F
0 0	\(\overline{A+B}\)
0 1	\(A+B\)
1 0	\(A\oplus B\)
1 0	\(AB\)

Implement the circuit using one 4 to AB Multiplexor, one 2-input Exclusive OR gate, one 2-input AND gate, one 2-input OR gate and one Inverter.

Question 54.

An 8085 based system has an output port with address 00H. Consider the following assembly language program.

ORG 0100H

MVI A, 00H

LXI H, 0105H

OUT 00H

INR A

PCHL

HLT

(a) What does the program do with respect to the output port 00H?

(b) Show the waveforms at the three least significant bits of the port 00H.

Question 55.

A demand paged virtual memory system uses 16 bit virtual address, page size of 256 bytes, and has 1 Kbyte of main memory. LRU page replacement is implemented using list, whose current status (page numbers in decimal) is

For each hexadecimal address in the address sequence given below,

00FF, 010D, 10FF, 11B0

indicate,

(i) the new status of the list

(ii) page faults, if any, and

(iii) page replacements, if any.

Section - B (50 Marks)

Answer any TEN questions from this section. All questions carry equal marks.

Question 56.

Let F be the collection of all functions f:{1,2,3} → {1,2,3}. If f and g ∈ F, define an equivalence relation ~ by f ~ g if and only if f(3) = g.

(a) Find the number of equivalence classes defined by ~

(b) Find the number of elements in each equivalence class.

Question 57.

The Fibonacci sequence {f₁, f₂, f₃ ……f_n} is defined by the following recurrence:

f_n+2 = f_n+1 + f_n, n ≥ 1; f₂ =1: f₁ =1:

Prove by induction that every third element of the sequence is even.

Question 58.

Let \(A=\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}\) and \(B=\begin{bmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{bmatrix}\) be two matrices such that

AB = I. Let and CD = 1. Express the elements of D in terms of the elements of B.

Question 59.

Let G be a context-free grammar where G = ({S, A, B, C}, {a, b, d}, P,S) with the productions in P given below.

S → ABAC

A → aA | ε

B → bB | ε

C → d

(ε denoted the null string). Transform the grammar G to an equivalent context-free grammar G that has no ε productions and no unit productions. (A unit production is of the form x → y, and y are non terminals).

Question 60.

Given below are the transition diagrams for two finite state machines M₁ and M₂ recognizing languages L₁ and L₂ respectively.

GATE CSE 1996 Previous-Year Questions 60

(a) Display the transition diagram for a machine that recognizes L₁₁ L₂, obtained from transition diagrams for M₁ and M₂ by adding only and transitions and no new states.

(b) Modify the transition diagram obtained in part (a) obtain a transition diagram for a machine that recognizes (L₁ L₂) by adding only ε transitions and no new states.

(Final states are enclosed in double circles).

Question 61.

Let Q = ({q₁, q₂}, {a,b}, {a, b, Z}, δ, qi, Z, φ) be a pushdown automaton accepting by empty stack, for the language which is the set of all nonempty even palindromes over the set {a,b}. Below is an incomplete specification of the transition function δ. Complete the specification. The top of stack is assumed to be at the right end of the string representing stack contents.

(1) δ(q₁,a,Z) = {(q₁,Za)}

(2) δ(q₁,b,Z) = {(q₁,Zb)}

(3) δ(q₁,a,a) = {………,……..}

(4) δ(q₁,b,b) = {……….,………}

(5) δ(q₂,a,a) = {(q₂,ε)}

(6) δ(q₂,b,b) = {(q₂,ε)}

(7) δ(q₂,ε,Z) = {(q₂,ε)}

GATE CSE 1996 Previous-Year Questions (PYQs)

Section - A (100 Marks)

Write in your answer book the correct or the most appropriate answer to the following multiple choice questions by writing the corresponding letter a, b, c or d against the sub-question number.

(25 x 1 = 25)

Question 1.

Question 2.

Question 3.

Question 4.

Question 5.

Question 6.

Question 7.

Question 8.

Question 9.

Question 10.

Question 11.

Question 12.

Question 13.

Question 14.

Question 15.

Question 16.

Question 17.

Question 18.

Question 19.

Question 20.

Question 21.

Question 22.

Question 23.

Question 24.

Question 25.

Write in your answer book the correct or the most appropriate answer to the following multiple choice questions by writing the corresponding letter a, b, c or d against the sub-question number.

(25 x 2 = 50)

Question 26.

Question 27.

Question 28.

Question 29.

Question 30.

Question 31.

Question 32.

Question 33.

Question 34.

Question 35.

Question 36.

Question 37.

Question 38.

Question 39.

Question 40.

Question 41.

Question 42.

Question 43.

Question 44.

Question 45.

Question 46.

Question 47.

Question 48.

Question 49.

Question 50.

Question 51.

Question 52.

Question 53.

Question 54.

Question 55.

Section - B (50 Marks)

Answer any TEN questions from this section. All questions carry equal marks.

Question 56.

Question 57.

Question 58.

Question 59.

Question 60.

Question 61.

Question 62.

Question 63.

Question 64.

Question 65.

Question 66.

Question 67.

Question 68.

Question 69.

Question 70.

Question 71.

Question 72.