GATE CS question library

Which one of the following statements is $\text{TRUE}$ for all positive functions $f(n)?$

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

Which one of the following statements is $\text{TRUE}?$

Consider the problem of reversing a singly linked list. To take an example, given the linked list below, the reversed linked list should look like Which one of the following statements is $\text{TRUE}$ about the time complexity of algorithms that solve the above problem in $O(1)$ space?

In a relational data model, which one of the following statements is $\text{TRUE}?$

​​​Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_{1}$ and $h_{2}.$ Further suppose our hashing scheme uses $h_{1}$ for the odd keys and $h_{2}$ for the even keys. What is the expected number of keys in a slot?

Consider the following threads, $\text{T}_{1}, \text{T}_{2},$ and $\text{T}_{3}$ executing on a single processor, synchronized using three binary semaphore variables, $\text{S}_{1}, \text{S}_{2},$ and $\text{S}_{3},$ operated upon using standard $\textsf{wait}()$ and $\textsf{signal}().$ The threads can be context switched in any order and at any …

Let $\text{R1}$ and $\text{R2}$ be two $4 – \text{bit}$ registers that store numbers in $2\text{’s}$ complement form. For the operation $\text{R1 + R2},$ which one of the following values of $\text{R1}$ and $\text{R2}$ gives an arithmetic overflow?

Consider the following two statements with respect to the matrices $\textit{A}_{m \times n}, \textit{B}_{n \times m}, \textit{C}_{n \times n}$ and $\textit{D}_{n \times n}.$ Statement $1: tr \text{(AB)} = tr \text{(BA)}$ Statement $2: tr \text{(CD)} = tr \text{(DC)}$ where $tr()$ represents the trace of a matrix. Which one of the following holds?

Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

What is printed by the following $\text{ANSI C}$ program? #include<stdio.h> int main(int argc, char *argv[]) { int x = 1, z[2] = {10, 11}; int *p = NULL; p = &x; *p = 10; p = &z[1]; *(&z[0] + 1) += 3; printf(“%d, %d, %d\n”, x, z[0], z[1]); return 0; }

Consider an enterprise network with two Ethernet segments, a web server and a firewall, connected via three routers as shown below. What is the number of subnets inside the enterprise network?

Let $\text{WB}$ and $\text{WT}$ be two set associative cache organizations that use $\text{LRU}$ algorithm for cache block replacement. $\text{WB}$ is a write back cache and $\text{WT}$ is a write through cache. Which of the following statements is/are $\text{FALSE}?$

Which of the following statements is/are $\text{TRUE}?$

Which of the following statements is/are $\text{TRUE}$ with respect to deadlocks?

Consider the following three relations in a relational database. $\text{Employee} (\underline{\text{eId}},\text{Name}), \; \text{Brand}(\underline{\text{bId}},\text{bName}), \; \text{Own}(\underline{\text{eId}},\underline{\text{bId}})$ Which of the following relational algebra expressions return the set of $\textit{elds}$ who own all the brands?

Which of the following statements is/are $\text{TRUE}$ for a group $\textit{G}?$

Suppose a binary search tree with $1000$ distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with $0,$ the $3^{\text{rd}}$ largest element of the tree is stored at index ______________ .

Consider the augmented grammar with $\{ +, {\ast}, (,),\text{id} \}$ as the set of terminals. $S’ \rightarrow S$ $S \rightarrow S + R\; |\; R$ $R \rightarrow R {\ast} P \;| \;P$ $P \rightarrow (S)\; |\; \text{id}$ If $I_{0}$ is the set of two $\textit{LR}(0)$ items $\{ [S’ \rightarrow S.], [S \rightarrow S. + R] \}$, then …

Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .