GATE CS question library

Consider a network with five nodes, $N1$ to $N5$, as shown as below. The network uses a Distance Vector Routing protocol. Once the routes have been stabilized, the distance vectors at different nodes are as follows. N1: $(0, 1, 7, 8, 4)$ N2: $(1, 0, 6, 7, 3)$ N3: $(7, 6, 0, 2, 6)$ N4: $(8, 7, 2, 0, 4)$ N5: $(4, 3, 6, 4, 0)$ Each distance vector …

Consider the following circuit involving three D-type flip-flops used in a certain type of counter configuration. If at some instance prior to the occurrence of the clock edge, $P, Q$ and $R$ have a value $0$, $1$ and $0$ respectively, what shall be the value of $PQR$ after the clock edge?

Consider the following recursive C function that takes two arguments. unsigned int foo(unsigned int n, unsigned int r) { if (n>0) return ((n%r) + foo(n/r, r)); else return 0; } What is the return value of the function $\text{foo}$ when it is called as $\text{foo(345, 10)}$?

The following is the comment written for a C function. /* This function computes the roots of a quadratic equation a.x^2 + b.x + c = 0. The function stores two real roots in *root1 and *root2 and returns the status of validity of roots. It handles four different kinds of cases. (i) When coefficient a is zero irrespective of discriminant (ii) When …

Database table by name $\text{Loan\_Records}$ is given below. …

A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below. Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?

An application loads $100$ libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as $10$ ms. Rotational speed of disk is $6000$ rpm. If all $100$ libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data …

An $8\text{KB}$ direct-mapped write-back cache is organized as multiple blocks, each size of $32\text{-bytes}$. The processor generates $32\text{-bit}$ addresses. The cache controller contains the tag information for each cache block comprising of the following. $1$ valid bit $1$ modified bit As many bits as the minimum needed to identify the …

Definition of a language $L$ with alphabet $\{a\}$ is given as following.$$L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$$What is the minimum number of states needed in a DFA to recognize $L$?

Consider the matrix as given below. $$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 7 \\ 0 & 0 & 3\end{bmatrix}$$ Which one of the following options provides the CORRECT values of the eigenvalues of the matrix?

Consider an instruction pipeline with four stages $\text{(S1, S2, S3 and S4)}$ each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline registers are as given in the figure. What is the approximate speed up of the pipeline in steady state under …

Consider a relational table $r$ with sufficient number of records, having attributes $A_1, A_2, \dots ,A_n$ and let $1 \leq p \leq n$. Two queries $Q1$ and $Q2$ are given below. $Q1: \pi_{A_1, \dots ,A_p} \left(\sigma_{A_p=c}\left(r\right)\right)$ where $c$ is a constant …

Four Matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $p \times q, \:\:q \times r, \:\:r \times s$ and $s \times t$ respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as $((M_1 \times M_2) \times (M_3 \times M_4))$, the total number of scalar multiplications is …

Which of the given options provides the increasing order of asymptotic complexity of functions $f_1, f_2, f_3$ and $f_4$? $f_1(n) = 2^n$ $f_2(n) = n^{3/2}$ $f_3(n) = n \log_2 n$ $f_4(n) = n^{\log_2 n}$

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a, b, c, d,$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers. The …

A deck of $5$ cards (each carrying a distinct number from $1$ to $5$) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number on the second card?

Consider a finite sequence of random values $X=[x_1,x_2,\dots x_n]$. Let $\mu_x$ be the mean and $\sigma_x$ be the standard deviation of $X$. Let another finite sequence $Y$ of equal length be derived from this as $y_i=a*x_i+b$, where $a$ and $b$ are positive constants. Let $\mu_y$ be the mean and $\sigma_y$ be the standard deviation of …

Consider a database table T containing two columns $\text{X}$ and $\text{Y}$ each of type $\text{integer}$. After the creation of the table, one record $\text{(X=1, Y=1)}$ is inserted in the table. Let $\text{MX}$ and $\text{MY}$ denote the respective maximum values of $\text{X}$ and $\text{Y}$ among all records in the table at any point in …

We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

Which one of the following options is CORRECT given three positive integers $x, y$ and $z$, and a predicate $$P\left(x\right) = \neg \left(x=1\right)\wedge \forall y \left(\exists z\left(x=y*z\right) \Rightarrow \left(y=x\right) \vee \left(y=1\right) \right)$$