Courses

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

## GATE : Computer Science and Information Technology (CS) 1998 GATE Paper without solution GATE Notes | EduRev

``` Page 1

GATE CS - 1998

SECTION - A
1. This question consists of 35 THIRTY-FIVE multiple questions of ONE mark each.
For each question, four possible alternatives (A, B, C and D) are given, out of
which ONLY ONE is correct. Indicate the correct answer in the boxes
corresponding to the questions only on the FIRST sheet of the answer book.
1.1 A die is rolled three times. The probability that exactly one odd number turns up
among the three outcomes is
(a)
1
6
(b)
3
8
(c)
1
8
(d)
1
2
1.2 Consider the following set of equations:
2 5
4 8 12
3 6 3 15
x y
x y
x y z
+ =
+ =
+ + =
This set
(a) has unique solution (b) has no solutions
(c) has finite number of solutions (d) has infinite number of solutions
1.3 Which of the following statements applies to the bisection method used for
finding roots of functions:
(a) converges within a few iterations
(b) guaranteed to work for all continuous functions
(c) is faster than the Newton-Raphson method
(d) requires that there be no error in determining the sign of the function.
1.4 Consider the function y x = in the interval [-1,1]. In this interval, the function is
(a) continuous and differentiable
(b) continuous but not differentiable
(c) differentiable but not continuous
(d) neither continuous nor differentiable
1.5 What is the converse of the following assertion?
I stay only if you go
(a) I stay if you go
(b) If I stay then you go
(c) If you do not go then I do not stay
(d) If I do not stay then you go
Page 2

GATE CS - 1998

SECTION - A
1. This question consists of 35 THIRTY-FIVE multiple questions of ONE mark each.
For each question, four possible alternatives (A, B, C and D) are given, out of
which ONLY ONE is correct. Indicate the correct answer in the boxes
corresponding to the questions only on the FIRST sheet of the answer book.
1.1 A die is rolled three times. The probability that exactly one odd number turns up
among the three outcomes is
(a)
1
6
(b)
3
8
(c)
1
8
(d)
1
2
1.2 Consider the following set of equations:
2 5
4 8 12
3 6 3 15
x y
x y
x y z
+ =
+ =
+ + =
This set
(a) has unique solution (b) has no solutions
(c) has finite number of solutions (d) has infinite number of solutions
1.3 Which of the following statements applies to the bisection method used for
finding roots of functions:
(a) converges within a few iterations
(b) guaranteed to work for all continuous functions
(c) is faster than the Newton-Raphson method
(d) requires that there be no error in determining the sign of the function.
1.4 Consider the function y x = in the interval [-1,1]. In this interval, the function is
(a) continuous and differentiable
(b) continuous but not differentiable
(c) differentiable but not continuous
(d) neither continuous nor differentiable
1.5 What is the converse of the following assertion?
I stay only if you go
(a) I stay if you go
(b) If I stay then you go
(c) If you do not go then I do not stay
(d) If I do not stay then you go
GATE CS - 1998

1.6 Suppose A is a finite set with n elements. The number of elements in the largest
equivalence relation of A is
(a) n (b)
2
n (c) 1 (d) n + 1
1.7 Let R
1
and R
2
be two equivalence relations on a set. Consider the following
assertions:
(i)
1 2
R R ? is an equivalence relation
(ii)
1 2
R R n is an equivalence relation
Which of the following is correct?
(a) Both assertions are true
(b) Assertion (i) is true but assertion (ii) is not true
(c) Assertion (ii) is true but assertion (i) is not true
(d) Neither (i) nor (ii) is true
1.8 The number of functions from an m element set to an n element set is
(a) m + n (b)
n
m (c)
m
n (d) m*n
1.9 If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is
represented by B = ((01)*1*)*, which of the following is true?
(a) A ? B (b) B ? A
(c) A and B are incomparable (d) A = B
1.10 Which of the following set can be recognized by a Deterministic Finite state
Automaton?
(a) The numbers 1, 2, 4, 8, ……………. 2
n
, ………… written in binary
(b) The numbers 1, 2, 4, ……………….,2
n
, …………..written in unary
(c) The set of binary string in which the number of zeros is the same as the
number of ones.
(d) The set {1, 101, 11011, 1110111, ………..}
1.11 Regarding the power of recognition of languages, which of the following
statements is false?
(a) The non-deterministic finite-state automata are equivalent to deterministic
finite-state automata.
(b) Non-deterministic Push-down automata are equivalent to deterministic Push-
down automata.
(c) Non-deterministic Turing machines are equivalent to deterministic Push-down
automata.
(d) Non-deterministic Turing machines are equivalent to deterministic Turing
machines.
(e) Multi-tape Turing machines are equivalent to Single-tape Turing machines.
Page 3

GATE CS - 1998

SECTION - A
1. This question consists of 35 THIRTY-FIVE multiple questions of ONE mark each.
For each question, four possible alternatives (A, B, C and D) are given, out of
which ONLY ONE is correct. Indicate the correct answer in the boxes
corresponding to the questions only on the FIRST sheet of the answer book.
1.1 A die is rolled three times. The probability that exactly one odd number turns up
among the three outcomes is
(a)
1
6
(b)
3
8
(c)
1
8
(d)
1
2
1.2 Consider the following set of equations:
2 5
4 8 12
3 6 3 15
x y
x y
x y z
+ =
+ =
+ + =
This set
(a) has unique solution (b) has no solutions
(c) has finite number of solutions (d) has infinite number of solutions
1.3 Which of the following statements applies to the bisection method used for
finding roots of functions:
(a) converges within a few iterations
(b) guaranteed to work for all continuous functions
(c) is faster than the Newton-Raphson method
(d) requires that there be no error in determining the sign of the function.
1.4 Consider the function y x = in the interval [-1,1]. In this interval, the function is
(a) continuous and differentiable
(b) continuous but not differentiable
(c) differentiable but not continuous
(d) neither continuous nor differentiable
1.5 What is the converse of the following assertion?
I stay only if you go
(a) I stay if you go
(b) If I stay then you go
(c) If you do not go then I do not stay
(d) If I do not stay then you go
GATE CS - 1998

1.6 Suppose A is a finite set with n elements. The number of elements in the largest
equivalence relation of A is
(a) n (b)
2
n (c) 1 (d) n + 1
1.7 Let R
1
and R
2
be two equivalence relations on a set. Consider the following
assertions:
(i)
1 2
R R ? is an equivalence relation
(ii)
1 2
R R n is an equivalence relation
Which of the following is correct?
(a) Both assertions are true
(b) Assertion (i) is true but assertion (ii) is not true
(c) Assertion (ii) is true but assertion (i) is not true
(d) Neither (i) nor (ii) is true
1.8 The number of functions from an m element set to an n element set is
(a) m + n (b)
n
m (c)
m
n (d) m*n
1.9 If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is
represented by B = ((01)*1*)*, which of the following is true?
(a) A ? B (b) B ? A
(c) A and B are incomparable (d) A = B
1.10 Which of the following set can be recognized by a Deterministic Finite state
Automaton?
(a) The numbers 1, 2, 4, 8, ……………. 2
n
, ………… written in binary
(b) The numbers 1, 2, 4, ……………….,2
n
, …………..written in unary
(c) The set of binary string in which the number of zeros is the same as the
number of ones.
(d) The set {1, 101, 11011, 1110111, ………..}
1.11 Regarding the power of recognition of languages, which of the following
statements is false?
(a) The non-deterministic finite-state automata are equivalent to deterministic
finite-state automata.
(b) Non-deterministic Push-down automata are equivalent to deterministic Push-
down automata.
(c) Non-deterministic Turing machines are equivalent to deterministic Push-down
automata.
(d) Non-deterministic Turing machines are equivalent to deterministic Turing
machines.
(e) Multi-tape Turing machines are equivalent to Single-tape Turing machines.
GATE CS - 1998

1.12  The string 1101 does not belong to the set represented by
(a) 110*(0 + 1) (b) 1 ( 0 + 1)* 101
(c) (10)* (01)* (00 + 11)* (d) (00 + (11)*0)*
1.13 What happens when a bit-string is XORed with itself n-times as shown:
( ( (
times B B B B n
? ?
? ? ?
? ?
? ?
K
(a) complements when n is even (b) complements when n is odd
(c) divides by 2
n
always
(d) remains unchanged when n is even
1.14 A multiplexor with a 4 bit data select input is a
(a) 4:1 multiplexor (b) 2:1 multiplexor
(c) 16:1 multiplexor (d) 8:1 multiplexor
1.15 The threshold level for logic 1 in the TTL family is
(a) any voltage above 2.5 V
(b) any voltage between 0.8 V and 5.0 V
(c) any voltage below 5.0 V
(d) any voltage below
cc
V but above 2.8 V
1.16 In serial communication employing 8 data bits, a parity bit and 2 stop bits, the
minimum band rate required to sustain a transfer rate of 300 characters per
second is
(a) 2400 band (b) 19200 band
(c) 4800 band (d) 1200 band
1.17 The octal representation of an integer is 3428. If this were to be treated as an
eight-bit integer is an 8085 based computer, its decimal equivalent is
(a) 226 (b) -98 (c) 76 (d) -30
1.18 Which of the following devices should get higher priority in assigning interrupts?
(a) Hard disk   (b) Printer
(c) Keyboard   (d) Floppy disk
1.19 Which of the following addressing modes permits relocation without any change
whatsoever in the code?
Page 4

GATE CS - 1998

SECTION - A
1. This question consists of 35 THIRTY-FIVE multiple questions of ONE mark each.
For each question, four possible alternatives (A, B, C and D) are given, out of
which ONLY ONE is correct. Indicate the correct answer in the boxes
corresponding to the questions only on the FIRST sheet of the answer book.
1.1 A die is rolled three times. The probability that exactly one odd number turns up
among the three outcomes is
(a)
1
6
(b)
3
8
(c)
1
8
(d)
1
2
1.2 Consider the following set of equations:
2 5
4 8 12
3 6 3 15
x y
x y
x y z
+ =
+ =
+ + =
This set
(a) has unique solution (b) has no solutions
(c) has finite number of solutions (d) has infinite number of solutions
1.3 Which of the following statements applies to the bisection method used for
finding roots of functions:
(a) converges within a few iterations
(b) guaranteed to work for all continuous functions
(c) is faster than the Newton-Raphson method
(d) requires that there be no error in determining the sign of the function.
1.4 Consider the function y x = in the interval [-1,1]. In this interval, the function is
(a) continuous and differentiable
(b) continuous but not differentiable
(c) differentiable but not continuous
(d) neither continuous nor differentiable
1.5 What is the converse of the following assertion?
I stay only if you go
(a) I stay if you go
(b) If I stay then you go
(c) If you do not go then I do not stay
(d) If I do not stay then you go
GATE CS - 1998

1.6 Suppose A is a finite set with n elements. The number of elements in the largest
equivalence relation of A is
(a) n (b)
2
n (c) 1 (d) n + 1
1.7 Let R
1
and R
2
be two equivalence relations on a set. Consider the following
assertions:
(i)
1 2
R R ? is an equivalence relation
(ii)
1 2
R R n is an equivalence relation
Which of the following is correct?
(a) Both assertions are true
(b) Assertion (i) is true but assertion (ii) is not true
(c) Assertion (ii) is true but assertion (i) is not true
(d) Neither (i) nor (ii) is true
1.8 The number of functions from an m element set to an n element set is
(a) m + n (b)
n
m (c)
m
n (d) m*n
1.9 If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is
represented by B = ((01)*1*)*, which of the following is true?
(a) A ? B (b) B ? A
(c) A and B are incomparable (d) A = B
1.10 Which of the following set can be recognized by a Deterministic Finite state
Automaton?
(a) The numbers 1, 2, 4, 8, ……………. 2
n
, ………… written in binary
(b) The numbers 1, 2, 4, ……………….,2
n
, …………..written in unary
(c) The set of binary string in which the number of zeros is the same as the
number of ones.
(d) The set {1, 101, 11011, 1110111, ………..}
1.11 Regarding the power of recognition of languages, which of the following
statements is false?
(a) The non-deterministic finite-state automata are equivalent to deterministic
finite-state automata.
(b) Non-deterministic Push-down automata are equivalent to deterministic Push-
down automata.
(c) Non-deterministic Turing machines are equivalent to deterministic Push-down
automata.
(d) Non-deterministic Turing machines are equivalent to deterministic Turing
machines.
(e) Multi-tape Turing machines are equivalent to Single-tape Turing machines.
GATE CS - 1998

1.12  The string 1101 does not belong to the set represented by
(a) 110*(0 + 1) (b) 1 ( 0 + 1)* 101
(c) (10)* (01)* (00 + 11)* (d) (00 + (11)*0)*
1.13 What happens when a bit-string is XORed with itself n-times as shown:
( ( (
times B B B B n
? ?
? ? ?
? ?
? ?
K
(a) complements when n is even (b) complements when n is odd
(c) divides by 2
n
always
(d) remains unchanged when n is even
1.14 A multiplexor with a 4 bit data select input is a
(a) 4:1 multiplexor (b) 2:1 multiplexor
(c) 16:1 multiplexor (d) 8:1 multiplexor
1.15 The threshold level for logic 1 in the TTL family is
(a) any voltage above 2.5 V
(b) any voltage between 0.8 V and 5.0 V
(c) any voltage below 5.0 V
(d) any voltage below
cc
V but above 2.8 V
1.16 In serial communication employing 8 data bits, a parity bit and 2 stop bits, the
minimum band rate required to sustain a transfer rate of 300 characters per
second is
(a) 2400 band (b) 19200 band
(c) 4800 band (d) 1200 band
1.17 The octal representation of an integer is 3428. If this were to be treated as an
eight-bit integer is an 8085 based computer, its decimal equivalent is
(a) 226 (b) -98 (c) 76 (d) -30
1.18 Which of the following devices should get higher priority in assigning interrupts?
(a) Hard disk   (b) Printer
(c) Keyboard   (d) Floppy disk
1.19 Which of the following addressing modes permits relocation without any change
whatsoever in the code?
GATE CS - 1998

1.20 Which of the following is true?
(a) Unless enabled, a CPU will not be able to process interrupts.
(b) Loop instructions cannot be interrupted till they complete.
(c) A processor checks for interrupts before executing a new instruction.
(d) Only level triggered interrupts are possible on microprocessors
1.21 Which one of the following algorithm design techniques is used in finding all pairs
of shortest distances in a graph?
(a) Dynamic programming (b) Backtracking
(c) Greedy   (d) Divide and Conquer
1.22 Give the correct matching for the following pairs:
(a) A – R  B – P  C – Q  D - S (b) A – R  B – P  C – S  D - Q
(c) A – P  B – R  C – S  D - Q (d) A – P  B – S  C – R  D - Q
1.23 How many sub strings of different lengths (non-zero) can be found formed from a
character string of length n?
(a) n (b)
2
n (c) 2
n
(d)
( ) 1
2
n n+
1.24 Which of the following statements is false?
(a) A tree with a n nodes has (n – 1) edges
(b) A labeled rooted binary tree can be uniquely constructed given its postorder
and preorder traversal results.
(c) A complete binary tree with n internal nodes has (n + 1) leaves.
(d) The maximum number of nodes in a binary tree of height h is
( )
1
2 1
h+
-
1.25 In a resident – OS computer, which of the following systems must reside in the
main memory under all situations?
(A) O (log n) (P) Selection
(B) O (n) (Q) Insertion sort
(C) O (n log n) (R) Binary search
(D) O
( )
2
n
(S) Merge sort
Page 5

GATE CS - 1998

SECTION - A
1. This question consists of 35 THIRTY-FIVE multiple questions of ONE mark each.
For each question, four possible alternatives (A, B, C and D) are given, out of
which ONLY ONE is correct. Indicate the correct answer in the boxes
corresponding to the questions only on the FIRST sheet of the answer book.
1.1 A die is rolled three times. The probability that exactly one odd number turns up
among the three outcomes is
(a)
1
6
(b)
3
8
(c)
1
8
(d)
1
2
1.2 Consider the following set of equations:
2 5
4 8 12
3 6 3 15
x y
x y
x y z
+ =
+ =
+ + =
This set
(a) has unique solution (b) has no solutions
(c) has finite number of solutions (d) has infinite number of solutions
1.3 Which of the following statements applies to the bisection method used for
finding roots of functions:
(a) converges within a few iterations
(b) guaranteed to work for all continuous functions
(c) is faster than the Newton-Raphson method
(d) requires that there be no error in determining the sign of the function.
1.4 Consider the function y x = in the interval [-1,1]. In this interval, the function is
(a) continuous and differentiable
(b) continuous but not differentiable
(c) differentiable but not continuous
(d) neither continuous nor differentiable
1.5 What is the converse of the following assertion?
I stay only if you go
(a) I stay if you go
(b) If I stay then you go
(c) If you do not go then I do not stay
(d) If I do not stay then you go
GATE CS - 1998

1.6 Suppose A is a finite set with n elements. The number of elements in the largest
equivalence relation of A is
(a) n (b)
2
n (c) 1 (d) n + 1
1.7 Let R
1
and R
2
be two equivalence relations on a set. Consider the following
assertions:
(i)
1 2
R R ? is an equivalence relation
(ii)
1 2
R R n is an equivalence relation
Which of the following is correct?
(a) Both assertions are true
(b) Assertion (i) is true but assertion (ii) is not true
(c) Assertion (ii) is true but assertion (i) is not true
(d) Neither (i) nor (ii) is true
1.8 The number of functions from an m element set to an n element set is
(a) m + n (b)
n
m (c)
m
n (d) m*n
1.9 If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is
represented by B = ((01)*1*)*, which of the following is true?
(a) A ? B (b) B ? A
(c) A and B are incomparable (d) A = B
1.10 Which of the following set can be recognized by a Deterministic Finite state
Automaton?
(a) The numbers 1, 2, 4, 8, ……………. 2
n
, ………… written in binary
(b) The numbers 1, 2, 4, ……………….,2
n
, …………..written in unary
(c) The set of binary string in which the number of zeros is the same as the
number of ones.
(d) The set {1, 101, 11011, 1110111, ………..}
1.11 Regarding the power of recognition of languages, which of the following
statements is false?
(a) The non-deterministic finite-state automata are equivalent to deterministic
finite-state automata.
(b) Non-deterministic Push-down automata are equivalent to deterministic Push-
down automata.
(c) Non-deterministic Turing machines are equivalent to deterministic Push-down
automata.
(d) Non-deterministic Turing machines are equivalent to deterministic Turing
machines.
(e) Multi-tape Turing machines are equivalent to Single-tape Turing machines.
GATE CS - 1998

1.12  The string 1101 does not belong to the set represented by
(a) 110*(0 + 1) (b) 1 ( 0 + 1)* 101
(c) (10)* (01)* (00 + 11)* (d) (00 + (11)*0)*
1.13 What happens when a bit-string is XORed with itself n-times as shown:
( ( (
times B B B B n
? ?
? ? ?
? ?
? ?
K
(a) complements when n is even (b) complements when n is odd
(c) divides by 2
n
always
(d) remains unchanged when n is even
1.14 A multiplexor with a 4 bit data select input is a
(a) 4:1 multiplexor (b) 2:1 multiplexor
(c) 16:1 multiplexor (d) 8:1 multiplexor
1.15 The threshold level for logic 1 in the TTL family is
(a) any voltage above 2.5 V
(b) any voltage between 0.8 V and 5.0 V
(c) any voltage below 5.0 V
(d) any voltage below
cc
V but above 2.8 V
1.16 In serial communication employing 8 data bits, a parity bit and 2 stop bits, the
minimum band rate required to sustain a transfer rate of 300 characters per
second is
(a) 2400 band (b) 19200 band
(c) 4800 band (d) 1200 band
1.17 The octal representation of an integer is 3428. If this were to be treated as an
eight-bit integer is an 8085 based computer, its decimal equivalent is
(a) 226 (b) -98 (c) 76 (d) -30
1.18 Which of the following devices should get higher priority in assigning interrupts?
(a) Hard disk   (b) Printer
(c) Keyboard   (d) Floppy disk
1.19 Which of the following addressing modes permits relocation without any change
whatsoever in the code?
GATE CS - 1998

1.20 Which of the following is true?
(a) Unless enabled, a CPU will not be able to process interrupts.
(b) Loop instructions cannot be interrupted till they complete.
(c) A processor checks for interrupts before executing a new instruction.
(d) Only level triggered interrupts are possible on microprocessors
1.21 Which one of the following algorithm design techniques is used in finding all pairs
of shortest distances in a graph?
(a) Dynamic programming (b) Backtracking
(c) Greedy   (d) Divide and Conquer
1.22 Give the correct matching for the following pairs:
(a) A – R  B – P  C – Q  D - S (b) A – R  B – P  C – S  D - Q
(c) A – P  B – R  C – S  D - Q (d) A – P  B – S  C – R  D - Q
1.23 How many sub strings of different lengths (non-zero) can be found formed from a
character string of length n?
(a) n (b)
2
n (c) 2
n
(d)
( ) 1
2
n n+
1.24 Which of the following statements is false?
(a) A tree with a n nodes has (n – 1) edges
(b) A labeled rooted binary tree can be uniquely constructed given its postorder
and preorder traversal results.
(c) A complete binary tree with n internal nodes has (n + 1) leaves.
(d) The maximum number of nodes in a binary tree of height h is
( )
1
2 1
h+
-
1.25 In a resident – OS computer, which of the following systems must reside in the
main memory under all situations?
(A) O (log n) (P) Selection
(B) O (n) (Q) Insertion sort
(C) O (n log n) (R) Binary search
(D) O
( )
2
n
(S) Merge sort
GATE CS - 1998

1.26 Which of the following statements is true?
(a) SLR parser is more powerful than LALR
(b) LALR parser is more powerful than Canonical LR parser
(c) Canonical LR parser is more powerful than LALR parser.
(d) The parsers SLR, Canonical CR, and LALR have the same power
1.27 Type checking is normally done during
(a) lexical analysis (b) syntax analysis
(c) syntax directed translation (d) code optimization
1.28 A linker reads four modules whose lengths are 200, 800, 600 and 500 words,
respectively. If they are loaded in that order, what are the relocation constants?
(a) 0, 200, 500, 600   (b) 0, 200, 1000, 1600
(c) 200, 500, 600, 800  (d) 200, 700, 1300, 2100
1.29 Which of the following is an example of a spooled device?
(a) The terminal used to enter the input data for the C program being executed
(b) An output device used to print the output of a number of jobs.
(c) The secondary memory device in a virtual storage system
(d) The swapping area on a disk used by the swapper.
1.30 When the result of a computation depends on the speed of the processes
involved there is said to be
(a) cycle steating    (b) rare condition
(c) a time lock   (d) a deadlock
1.31  A counting semaphore was initialized to 10. Then 6 P (wait) operations and 4V
(signal) operations were completed on this semaphore. The resulting value of the
semaphore is
(a) 0 (b) 8 (c) 10 (d) 12
1.32 A computer has six tape drives, with n processes competing for them. Each
process may need two drives. What is the maximum value of n for the system to
(a) 6 (b) 5 (c) 4 (d) 3
1.33 Given two union compatible relations R
1
(A,B) and R
2
(C,D), what is the result of
the operation R
1
A = CAB = DR
2
?
(a)
1 2
R R ? (b)
1 2
R R × (c)
1 2
R R - (d)
1 2
R R n
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

## Mock Test Series - Computer Science Engg. (CSE) GATE 2020

131 docs|169 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;