GATE 1992 CSE & IT
24 questions across 1 session
A computer system has 6 tape drives, with n process completing for them. Each process may need 3 tape drives. The maximum value of n for which the system is guaranteed to be deadlo...
Which of the following statements is / are true / false? Union of two recursive languages is recursive
Uses Modus ponens $$\left( {A,\,\,A \to B\,|\,\, = B} \right)$$ or resolution to show that the following set is inconsistent: (1) $$Q\left( x \right) \to P\left( x \right)V \sim R\...
Which of the following is an example of a spooled device?
Which page replacement policy sometimes leads to more page faults when size of memory is increased?
Which of the following is/are tautology?
Which of the following predicate calculus statements is/are valid?
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is _______.
Which of the following problems is not NP-hard?
Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an input for which Quicksort tak...
Following algorithm(s) can be used to sort n integers in the range [1....... n 3 ] in O(n) time
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 time $$t = 0$$ contains the pages {a, d, e}, where a was re...
(a) If G is a group of even order, then show that there exists an element $$a \ne e$$, the identifier $$g$$, such that $${a^2} = e$$ (b) Consider the set of integers $$\left\{ {1,2...
Consider the SLR(1) and LALR (1) parsing tables for a context-free grammar. Which of the following statements is/are true?
Maximum number of edges in a planar graph with $$n$$ vertices is _______ .
Start and stop bits do not contain 'information' but these are used in serial communication for
At a particular time of computation the value of a counting semaphore is 7. Then 20 P operations and 15 V operations were completed on this semaphore. The resulting value of the se...
A non-planar graph with minimum number of vertices has
Context-free languages are
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$$ in $$G,$$ if $$G$$ is Chomsky normal form?
Which of the following regular expression identities are true?
Which of the following statements is / are true / false? Regular languages are closed under infinite union.
In which of the cases stated below is the following statement true? “For every non-deterministic machine $${M_1}$$ there exists an equivalent deterministic machine $${M_2}$$ recogn...
Which of the following statements is / are true / false? The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$ is prime$$\left. \, \right\}$$ is not regular