GATE CS question library

Let $P, Q, R$ and $S$ be the attributes of a relation in a relational schema. Let $X \rightarrow Y$ indicate functional dependency in the context of a relational database, where $X, Y \subseteq\{P, Q, R, S\}$. Which of the following options is/are always true?

In the context of relational database normalization, which of the following statements is/are true?

Consider the function $f: \mathbb{R} \rightarrow \mathbb{R}$ defined as follows: $$f(x)=\left\{\begin{array}{lr} c_{1} e^{x}-c_{2} \log _{\mathrm{e}}\left(\frac{1}{x}\right), & \text{ if } x>0 \\ 3 & \text{ otherwise } \end{array}\right.$$ where $c_{1}, c_{2} \in \mathbb{R}$. If $f$ is continuous at $x=0$, then $c_{1}+c_{2}=$ …

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with $23$ nodes is $\_\_\_\_$.(answer in integer)

Consider the following program in C: #include <stdio.h> void func(int i, int j) { if(i < j) { int i = 0; while (i < 10) { j += 2; i++; } } printf("%d", i); } int main() { int i = 9, j = 10; func(i, j); return 0; } The output of the program is $\_\_\_\_\_\_$. (answer in integer) Note: Assume that the program compiles and runs successfully.

Consider a system consisting of $k$ instances of a resource $R$, being shared by $5$ processes. Assume that each process requires a maximum of two instances of resource $R$ and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance. The …

Consider the real valued variables $X, Y$ and $Z$ represented using the IEEE $754$ singleprecision floating-point format. The binary representations of $X$ and $Y$ in hexadecimal notation are as follows: $$X: 35 \mathrm{C} 00000 \quad Y: 34 \mathrm{A} 00000$$ Let $Z=X+Y$. Which one of the following is the binary representation of $Z$, in …

Consider a $2$-bit saturating up/down counter that performs the saturating up count when the input $P$ is $0$, and the saturating down count when $P$ is $1$. The Next State table of the counter is as shown. The counter is built as a synchronous sequential circuit using D flip-flops. InputCureent StateNext State …

The size of the physical address space of a processor is $2^{32}$ bytes. The capacity of a cache memory unit is $2^{23}$ bytes. The cache block size is $128$ bytes. The cache memory unit can be built as a direct mapped cache or as a $K$-way set-associative cache, where $K=2^{L}$ and $L \in\{1,2,3\}$. Let the length of the TAG field be $M$ bits …

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head. struct node{ int elt; struct node *next; }; int getListSize (struct node *head) { if( E1 ) return 1; return E2; } Which one of the following options gives the correct replacements for the expressions …

Let $P$ be the set of all integers from $1$ to $15$. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path. Let $s \in V$ be a vertex in $G$. For every $u \in V$ and for every $k \geq 0$, let $d_{k}(u)$ denote the weight of a shortest path (in terms …

Consider the control flow graph shown in the figure. Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B$4$ and B$5$? Note: All the variables are integers.

Consider a relational database schema with two relations $R(P, Q)$ and $S(X, Y)$. Let $E=\{\langle u\rangle \mid \exists v \exists w\langle u, v\rangle \in R \wedge\langle v, w\rangle \in S\}$ be a tuple relational calculus expression. Which one of the following relational algebraic expressions is equivalent to $E$ ?

A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism's slow-start threshold is set to $10000$ segments. Assume that the round-trip time is fixed at $1$ millisecond. Assume that the sender always has data to send, the segments are numbered from $1$, and no …

Consider the implementation of sliding window protocol over a lossless link, with a window size of $W$ frames, where each frame is of size $1000$ bits (including header). The bandwidth of the link is $100 \mathrm{kbps}\left(1 \mathrm{k}=10^{3}\right)$ and the one-way propagation delay is $100$ milliseconds. Assume that processing times at the sender …

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be defined as follows: $$f(x)=\left(\frac{|x|}{2}-x\right)\left(x-\frac{|x|}{2}\right)$$ Which of the following statements is/are true?

Let $G(V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{\prime} \subseteq V$ such that for every $(u, v) \in E, u \in V^{\prime}$ or $v \in V^{\prime}$. Let the size of the smallest vertex cover in $G$ be $k$. Let $S$ be any vertex cover of size $k$. For a vertex $v \in V$, which of the following constraints …

Consider a Boolean function $F$ with the following minterm expression: $$F(P, Q, R, S)=\sum m(1,2,3,4,5,7,10,12,13,14)$$ Which of the following options is/are the minimal sum-of-products expression(s) of $F$ ?

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?