GATE CS question library

Let $f(x)$ be a polynomial and $g(x)=f'(x)$ be its derivative. If the degree of $(f(x)+f(-x))$ is $10$, then the degree of $(g(x) - g(-x))$ is __________.

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Consider the following expressions: $false$ $Q$ $true$ $P\vee Q$ $\neg Q\vee P$ The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$ is ___________.

B+ Trees are considered BALANCED because.

The value printed by the following program is _______. void f (int * p, int m) { m = m + 5; *p = *p + m; return; } void main () { int i=5, j=10; f (&i, j); printf ("%d", i+j); }

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{\text{th}}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________

The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? Quicksort runs in $\Theta (n^2)$ time Bubblesort runs in $\Theta (n^2)$ time Mergesort runs in $\Theta (n)$ time Insertion sort runs in $\Theta (n)$ time

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: $\Theta \left(N\right)$ delete, …

Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires.

The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

Suppose a database schedule $S$ involves transactions $T_1,\ldots,T_n$ . Construct the precedence graph of $S$ with vertices representing the transactions and edges representing the conflicts. If $S$ is serializable, which one of the following orderings of the vertices of the precedence graph is guaranteed to yield a serial schedule?

Suppose that the eigenvalues of matrix $A$ are $1, 2, 4$. The determinant of $\left(A^{-1}\right)^{T}$ is _________.

Let $X$ be the number of distinct $16$-bit integers in $2's$ complement representation. Let $Y$ be the number of distinct $16$-bit integers in sign magnitude representation Then $X - Y$ is______.

A processor has $40$ distinct instruction and $24$ general purpose registers. A $32$-bit instruction word has an opcode, two registers operands and an immediate operand. The number of bits available for the immediate operand field is_______.

Consider the systems, each consisting of $m$ linear equations in $n$ variables. If $m < n$, then all such systems have a solution. If $m > n$, then none of these systems has a solution. If $m = n$, then there exists a system which has a solution. Which one of the following is CORRECT?

In an Ethernet local area network, which one of the following statements is TRUE?

Language $L_{1}$ is defined by the grammar: $S_{1} \rightarrow a S_{1} b \mid \varepsilon$ Language $L_{2}$ is defined by the grammar: $S_{2} \rightarrow a b S_{2} \mid \varepsilon$ Consider the following statements: P: $L_{1}$ is regular Q: $L_{2}$ is regular Which one of the following is TRUE?

Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than $100$ hours given that it is of Type $1$ is $0.7$, and given that it is of Type $2$ is $0.4$. The probability that an LED bulb chosen uniformly at random lasts more than $100$ hours is _________.