GATE CS question library

Consider the equation $(43)_x = (y3)_8$ where $x$ and $y$ are unknown. The number of possible solutions is _____

For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time? …

Which of the following languages are context-free? $L_1: \left\{a^mb^na^nb^m \mid m, n \geq 1\right\}$ $L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$ $L_3: \left\{a^mb^n \mid m = 2n +1 \right\}$

If the following system has non-trivial solution, $px + qy + rz = 0$ $qx + ry + pz = 0$ $rx + py + qz = 0$, then which one of the following options is TRUE?

Consider the following grammar G $S \rightarrow F \mid H$ $F \rightarrow p \mid c$ $H \rightarrow d \mid c$ Where $S$, $F$, and $H$ are non-terminal symbols, $p, d$, and $c$ are terminal symbols. Which of the following statement(s) is/are correct? S1: LL(1) can parse all strings that are generated using grammar G S2: LR(1) can parse all …

Consider the following two C code segments. $Y$ and $X$ are one and two dimensional arrays of size $n$ and $n \times n$ respectively, where $2 \leq n \leq 10$. Assume that in both code segments, elements of $Y$ are initialized to $0$ and each element $X[i][j]$ of array $X$ is initialized to $i+j$. Further assume that when stored in main …

Consider the partial Schedule $S$ involving two transactions $T1$ and $T2$. Only the $\textit{read}$ and the $\textit{write}$ operations have been shown. The $\textit{read}$ operation on data item $P$ is denoted by $\textit{read(P)}$ and $\textit{write}$ operation on data item $P$ is denoted by $\textit{write(P)}$. …

Consider a network connecting two systems located $8000$ $\text{Km}$ apart. The bandwidth of the network is $500 \times 10^6$ $\text{bits}$ per second. The propagation speed of the media is $4 \times 10^6$ $\text{meters}$ per second. It needs to design a Go-Back-$N$ sliding window protocol for this network. The average packet size is $10^7$ …

Consider the following C program #include<stdio.h> int main() { static int a[] = {10, 20, 30, 40, 50}; static int *p[] = {a, a+3, a+4, a+1, a+2}; int **ptr = p; ptr++; printf("%d%d", ptr-p, **ptr); } The output of the program is _______.

Assume that a mergesort algorithm in the worst case takes $30$ seconds for an input of size $64$. Which of the following most closely approximates the maximum input size of a problem that can be solved in $6$ minutes?

Consider a binary tree T that has $200$ leaf nodes. Then the number of nodes in T that have exactly two children are ______.

In a room there are only two types of people, namely $\text{Type 1}$ and $\text{Type 2}$. $\text{Type 1}$ people always tell the truth and $\text{Type 2}$ people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking the …

Suppose $U$ is the power set of the set $S = \{1, 2, 3, 4, 5, 6\}$. For any $T \in U$, let $|T|$ denote the number of elements in $T$ and $T'$ denote the complement of $T$. For any $T, R \in U \text{ let } T \backslash R$ be the set of all elements in $T$ which are not in $R$. Which one of the following is true?

Consider the following statements. TCP connections are full duplex TCP has no option for selective acknowledgement TCP connections are message streams

Consider a software project with the following information domain characteristics for calculation of function point metric. Number of external inputs (I) = 30 Number of external outputs (O) = 60 Number of external inquiries (E) = 23 Number of files (F) = 08 Number of external interfaces (N) = 02 It is given that the complexity weighting factors for I, O, E, …

Consider the relation $X(P,Q,R,S,T,U)$ with the following set of functional dependencies $F = \{ \\ \; \; \{P, R\} \rightarrow \{S, T\}, \\ \; \; \{P, S, U\} \rightarrow \{Q, R\} \\ \; \}$ Which of the following is the trivial functional dependency in $F^+$, where $F^+$ is closure to F?

Consider the following array of elements. $\langle 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 \rangle$ The minimum number of interchanges needed to convert it into a max-heap is

Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)?

Given that hash table $T$ with $25$ slots that stores $2000$ elements, the load factor $a$ for $T$ is _________.

Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?