Question 1 |

Which of the following problems are un-decidable?

[MSQ]

[MSQ]

Membership problem in context-free languages. | |

Whether a given context-free language is regular. | |

Whether a finite state automation halts on all inputs. | |

Membership problem for type 0 languages. |

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}

\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}

4 | |

5 | |

6 | |

3 |

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?

Passing an expression as a parameter | |

Passing an array as a parameter | |

Passing a pointer as a parameter | |

Passing as array element as a parameter |

Question 3 Explanation:

Question 4 |

An unrestricted use of the "go to" statement is harmful because of which of the following reason (s):

It makes it more difficult to verify programs. | |

It makes programs more inefficient. | |

It makes it more difficult to modify existing programs. | |

It results in the compiler generating longer machine code. |

Question 4 Explanation:

Question 5 |

Context-free languages and regular languages are both closed under the operation (s) of :

Union | |

Intersection | |

Concatenation | |

Complementation |

Question 5 Explanation:

Question 6 |

Answer the following questions:

Which of the following problems are undecidable?

Which of the following problems are undecidable?

Membership problem in context-free languages. | |

Whether a given context-free language is regular. | |

Whether a finite state automation halts on all inputs. | |

Membership problem for type 0 languages. |

Question 6 Explanation:

Question 7 |

Answer the following:

Which of the following well-formed formulas are equivalent?

Which of the following well-formed formulas are equivalent?

P \rightarrow Q | |

\neg Q \rightarrow \neg P | |

\neg P \vee Q | |

\neg Q \rightarrow P |

Question 7 Explanation:

Question 8 |

Answer the following:

Which of the following statements are FALSE?

Which of the following statements are FALSE?

For poisson distribution, the mean is twice the variance. | |

In queuing theory, if arrivals occur according to poisson distribution, then the inter-arrival time is exponentially distributed. | |

The distribution of waiting time is independent of the service discipline used in selecting the waiting customers for service. | |

If the time between successive arrivals is exponential, then the time between the occurences of every third arrival is also exponential. |

Question 8 Explanation:

Question 9 |

Answer the following:

Which one of the following statements (s) is/are FALSE?

Which one of the following statements (s) is/are FALSE?

Overlaying is used to run a program, which is longer than the address space of the computer. | |

Optimal binary search tree construction can be performed efficiently by using dynamic programming. | |

Depth first search cannot be used to find connected components of a graph. | |

Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed. |

Question 9 Explanation:

There are 9 questions to complete.