GATE CSE 1992

## GATE CSE

Following algorithm(s) can be used to sort n integers in the range [1....... n3] in O(n) time

View Question
Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [

View Question
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and

View Question
Which of the following problems is not NP-hard?

View Question
Consider the SLR(1) and LALR (1) parsing tables for a context-free grammar. Which of the following statements is/are tru

View Question
Start and stop bits do not contain 'information' but these are used in serial communication for

View Question
Which of the following predicate calculus statements is/are valid?

View Question
Uses Modus ponens $$\left( {A,\,\,A \to B\,|\,\, = B} \right)$$ or resolution to show that the following set is inconsis

View Question
A non-planar graph with minimum number of vertices has

View Question
Which of the following is/are tautology?

View Question
(a) If G is a group of even order, then
show that there exists an element $$a \ne e$$,
the identifier $$g$$, such that

View Question
Maximum number of edges in a planar graph with $$n$$ vertices is _______ .

View Question
Which of the following is an example of a spooled device?

View Question
At a particular time of computation the value of a counting semaphore is 7. Then 20 P operations and 15 V operations wer

View Question
Which page replacement policy sometimes leads to more page faults when size of memory is increased?

View Question
Let the page reference and the working set window be c c d b c e c e a d and 4, respectively. The initial working set at

View Question
A computer system has 6 tape drives, with n process completing for them.
Each process may need 3 tape drives. The maximu

View Question
Which of the following regular expression identities are true?

View Question
If $$G$$ is a context-free grammar and $$w$$ is a string of length $$n$$ in $$L(G),$$ how long is a derivation of $$w$$

View Question
Context-free languages are

View Question
In which of the cases stated below is the following statement true?
“For every non-deterministic machine $${M_1}$$ there

View Question
Which of the following statements is / are true / false?
Union of two recursive languages is recursive

View Question
Which of the following statements is / are true / false?
The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$

View Question
Which of the following statements is / are true / false?
Regular languages are closed under infinite union.

View Question