GATE CSE 1989

Question 1
Which of the following problems are un-decidable?
[MSQ]
A
Membership problem in context-free languages.
B
Whether a given context-free language is regular.
C
Whether a finite state automation halts on all inputs.
D
Membership problem for type 0 languages.
Theory of Computation   Undecidability
Question 2
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is
\begin{array}{|l|l|} \hline 0 & \text { S7 } \\ \hline 1 & \text { S1 } \\ \hline 2 & \\ \hline 3 & \text { S4 } \\ \hline 4 & \text { S2 } \\ \hline 5 & \text { } \\ \hline 6 & \text { S5 } \\ \hline 7 & \\ \hline 8 & \text { S6 } \\ \hline 9 & \text { S3 } \\ \hline \end{array}
A
4
B
5
C
6
D
3
Data Structure   Hashing
Question 3
In which of the following case(s) is it possible to obtain different results for call-by-reference and call-by-name parameter passing?
A
Passing an expression as a parameter
B
Passing an array as a parameter
C
Passing a pointer as a parameter
D
Passing as array element as a parameter
C Programming   Function
Question 4
An unrestricted use of the "go to" statement is harmful because of which of the following reason (s):
A
It makes it more difficult to verify programs.
B
It makes programs more inefficient.
C
It makes it more difficult to modify existing programs.
D
It results in the compiler generating longer machine code.
C Programming   Conditional Statement
Question 5
Context-free languages and regular languages are both closed under the operation (s) of :
A
Union
B
Intersection
C
Concatenation
D
Complementation
Theory of Computation   Context Free Language
Question 6
Answer the following questions:
Which of the following problems are undecidable?
A
Membership problem in context-free languages.
B
Whether a given context-free language is regular.
C
Whether a finite state automation halts on all inputs.
D
Membership problem for type 0 languages.
Theory of Computation   Undecidability
Question 7
Answer the following:
Which of the following well-formed formulas are equivalent?
A
P \rightarrow Q
B
\neg Q \rightarrow \neg P
C
\neg P \vee Q
D
\neg Q \rightarrow P
Discrete Mathematics   Propositional Logic
Question 8
Answer the following:
Which of the following statements are FALSE?
A
For poisson distribution, the mean is twice the variance.
B
In queuing theory, if arrivals occur according to poisson distribution, then the inter-arrival time is exponentially distributed.
C
The distribution of waiting time is independent of the service discipline used in selecting the waiting customers for service.
D
If the time between successive arrivals is exponential, then the time between the occurences of every third arrival is also exponential.
Discrete Mathematics   Probability Theory
Question 9
Answer the following:
Which one of the following statements (s) is/are FALSE?
A
Overlaying is used to run a program, which is longer than the address space of the computer.
B
Optimal binary search tree construction can be performed efficiently by using dynamic programming.
C
Depth first search cannot be used to find connected components of a graph.
D
Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.
Data Structure   Binary Tree
There are 9 questions to complete.

Leave a Comment