# 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 1 Explanation:
 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 2 Explanation:
 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 3 Explanation:
 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 4 Explanation:
 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 5 Explanation:
 Question 6
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 6 Explanation:
 Question 7
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 7 Explanation:
 Question 8