# GATE CSE 1999

 Question 1
Suppose that the expectation of a random variable X is 5. Which of the following statements is true?
 A There is a sample point at which X has the value 5. B There is a sample point at which X has value greater than 5. C There is a sample point at which X has a value greater than equal to 5. D None of the above
Discrete Mathematics   Probability Theory
Question 1 Explanation:
 Question 2
The number of binary relations on a set with n elements is:
 A $n^2$ B $2^n$ C $2^{n^2}$ D None of the above
Discrete Mathematics   Relation
Question 2 Explanation:
 Question 3
The number of binary strings of n zeros and k ones in which no two ones are adjacent is
 A $^{n-1}C_k$ B $^nC_k$ C $^nC_{k+1}$ D None of the above
Discrete Mathematics   Combination
Question 3 Explanation:
 Question 4
Consider the regular expression (0 + 1) (0+1) ... n times. The minimum state finite automaton that recognizes the language represented by this regular expression contains
 A n states B n+1 states C n+2 states D None of the above
Theory of Computation   Finite Automata
Question 4 Explanation:
 Question 5
Context-free languages are closed under:
 A Union, intersection B Union, Kleene closure C Intersection, complement D Complement, Kleene closure
Theory of Computation   Context Free Language
Question 5 Explanation:
 Question 6
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?
 A $L_1 = L_2$ B $L_1 \supset L_2$ C $L_1 \subset L_2$ D None
Theory of Computation   Push-down Automata
Question 6 Explanation:
 Question 7
Which of the following expressions is not equivalent to $\bar{x}$?
 A x NAND x B x NOR x C x NAND 1 D x NOR 1
Digital Logic   Boolean Algebra
Question 7 Explanation:
 Question 8
Which of the following functions implements the Karnaugh map shown below?

 A $\bar{A}B + CD$ B $D(C+A)$ C $AD+\bar{A}B$ D $(C+D) (\bar{C}+D) + (A+B)$
Digital Logic   Boolean Algebra
Question 8 Explanation:
 Question 9
Listed below are some operating system abstractions (in the left column) and the hardware components (in the right column)
$\small \begin{array}{cl|cl}\hline \text{(A)}& \text{Thread} & \text{1.}& \text{Interrupt} \\\hline \text{(B)}& \text{Virtual address space} & \text{2.}& \text{Memory} \\\hline \text{(C)} &\text{File system} & \text{3.} &\text{CPU} \\\hline \text{(D)} &\text{Signal} & \text{4.}& \text{Disk} \\\hline \end{array}$
 A (A) - 2 (B) - 4 (C) - 3 (D) - 1 B (A) - 1 (B) - 2 (C) - 3 (D) - 4 C (A) - 3 (B) - 2 (C) - 4 (D) - 1 D (A) - 4 (B) - 1 (C) - 2 (D) - 3
Operating System   Memory Management
Question 9 Explanation:
 Question 10
Which of the following disk scheduling strategies is likely to give the best throughput?
 A Farthest cylinder next B Nearest cylinder next C First come first served D Elevator algorithm
Operating System   Disk Scheduling
Question 10 Explanation:
There are 10 questions to complete.