GATE CS question library

Which of the following statements is FALSE?

The usual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depth-first traversals of the above graph?

Consider the following three claims: $(n+k)^m = \Theta(n^m)$ where $k$ and $m$ are constants $2^{n+1} = O(2^n)$ $2^{2n+1} = O(2^n)$ Which of the following claims are correct?

Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

Assume that the SLR parser for a grammar G has $n_1$ states and the LALR parser for G has $n_2$ states. The relationship between $n_1$ and $n_2$ is

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

The regular expression $0^*(10^*)^*$ denotes the same set as

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows.$$L = \begin{cases} (0+1)^* & \text{ if } P = NP \\ \phi & otherwise \end{cases}$$Which of the following statements is true?

Ram and Shyam have been asked to show that a certain problem $\Pi$ is $\text{NP-complete}.$ Ram shows a polynomial time reduction from the $\text{3-SAT}$ problem to $\Pi$, and Shyam shows a polynomial time reduction from $\Pi$ to $\text{3-SAT.}$ Which of the following can be inferred from these reductions?

Consider an array multiplier for multiplying two $n$ bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

For a pipelined CPU with a single ALU, consider the following situations The ${j+1}^{st}$ instruction uses the result of the $j^{th}$ instruction as an operand The execution of a conditional jump instruction The $j^{th}$ and ${j+1}^{st}$ instructions require the ALU at the same time. Which of the above can cause a hazard

Assuming all numbers are in $2’s$ complement representation, which of the following numbers is divisible by $11111011$?

Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between

Consider the set $\Sigma^*$ of all strings over the alphabet $\Sigma = \{0, 1\}$. $\Sigma^*$ with the concatenation operator for strings

Let $T(n)$ be the number of different binary search trees on $n$ distinct elements. Then $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, where $x$ is

$n$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

Let $A$ be a sequence of $8$ distinct integers sorted in ascending order. How many distinct pairs of sequences, $B$ and $C$ are there such that each is sorted in ascending order, $B$ has $5$ and $C$ has $3$ elements, and the result of merging $B$ and $C$ gives $A$

Let $P(E)$ denote the probability of the event $E$. Given $P(A) = 1$, $P(B) =\dfrac{1}{2}$, the values of $P(A\mid B)$ and $P(B\mid A)$ respectively are