GATE CS question library

Consider the following recurrence: $$\begin{array}{} f(1) & = & 1; \\ f(2n) & = & 2f(n) – 1, & \; \text{for}\; n \geq 1; \\ f(2n+1) & = & 2f(n) + 1, & \; \text{for}\; n \geq 1. \end{array}$$ Then, which of the following statements is/are $\text{TRUE}?$

Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?

​​​​​Which of the following is/are the eigenvector(s) for the matrix given below? $$\begin{pmatrix} – 9 & – 6 & – 2 & – 4 \\ – 8 & – 6 & – 3 & – 1 \\ 20 & 15 & 8 & 5 \\ 32 & 21 & 7 & 12 \end{pmatrix}$$

Consider a system with $2 \;\text{KB}$ direct mapped data cache with a block size of $64 \; \text{bytes}.$ The system has a physical address space of $64 \; \text{KB}$ and a word length of $16 \; \text{bits.}$ During the execution of a program, four data words $\text{P, Q, R,}$ and $\text{S}$ are accessed in that order $10$ times …

Consider routing table of an organization’s router shown below: …

Consider the relational database with the following four schemas and their respective instances. Student(sNo, sName, dNo) Dept(dNo, dName) Course(cNo, cName, dNo) Register(sNo, cNo) …

Consider a network with three routers $\text{P, Q, R}$ shown in the figure below. All the links have cost of unity. The routers exchange distance vector routing information and have converged on the routing tables, after which the link $\text{Q-R}$ fails. Assume that $\text{P}$ and $\text{Q}$ send out routing updates at random times, each at the same …

Let $\textit{G(V,E)}$ be a directed graph, where $\textit{V} = \{ 1, 2, 3, 4, 5 \}$ is the set of vertices and $\textit{E}$ is the set of directed edges, as defined by the following adjacency matrix $\textit{A}.$ $$A [i][j] = \left\{\begin{matrix} 1, & 1 \leq j \leq i \leq 5 \\ 0, & \text{otherwise}\end{matrix}\right.$$ $A[i][j] = 1$ …

Consider a $100 \; \text{Mbps}$ link between an earth station (sender) and a satellite (receiver) at an altitude of $2100 \; \text{km}.$ The signal propagates at a speed of $3 \times 10^{8} \; \text{m/s.}$ The time taken $\text{(in milliseconds,} \; \textit{rounded off to two decimal places})$ for the receiver to completely receive a packet of …

Consider the data transfer using $\text{TCP}$ over a $1 \; \text{Gbps}$ link. Assuming that the maximum segment lifetime $\text{(MSL)}$ is set to $60 \; \text{seconds},$ the minimum number of bits required for the sequence number field of the $\text{TCP}$ header, to prevent the sequence number space from wrapping around during the $\text{MSL}$ is …

A processor $\text{X}_{1}$ operating at $2 \; \text{GHz}$ has a standard $5-$stage $\text{RISC}$ instruction pipeline having a base $\text{CPI (cycles per instruction)}$ of one without any pipeline hazards. For a given program $\text{P}$ that has $30 \%$ branch instructions, control hazards incur $2$ cycles stall for every branch. A new …

Consider the queues $Q_{1}$ containing four elements and $Q_{2}$ containing none (shown as the $\textsf{Initial State}$ in the figure). The only operations allowed on these two queues are $\textsf{Enqueue (Q, element)}$ and $\textsf{Dequeue (Q)}.$ The minimum number of $\textsf{Enqueue}$ operations on $Q_{1}$ required to place the elements of …

Consider two files systems $\text{A}$ and $\text{B}$, that use contiguous allocation and linked allocation, respectively. A file of size $100$ blocks is already stored in $\text{A}$ and also in $\text{B}$. Now, consider inserting a new block in the middle of the file (between $50^{th}$ and $51^{st}$ block), whose data is already available in …

Consider a demand paging system with four page frames (initially empty) and $\text{LRU}$ page replacement policy. For the following page reference string $$7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1$$ the page fault rate, defined as the ratio of number of page faults to the number of memory accesses $\textit{(rounded off to one decimal place)}$ is …

Consider the following grammar along with translation rules. …

The ____________ is too high for it to be considered _____________.

A function $y(x)$ is defined in the interval $[0, 1]$ on the $x –$ axis as $$y(x) = \left\{\begin{matrix} 2& \text{if} & 0 \leq x < \frac{1}{3} \\ 3& \text{if}& \frac{1}{3} \leq x < \frac{3}{4} & \\ 1 & \text{if} & \frac{3}{4} \leq x \leq 1& \end{matrix}\right.$$ Which one of the following is the area under the …

Let $r$ be a root of the equation $x^{2} + 2x + 6 = 0.$ Then the value of the expression $(r+2) (r+3) (r+4) (r+5)$ is

Given below are four statements. Statement $1:$ All students are inquisitive. Statement $2:$ Some students are inquisitive. Statement $3:$ No student is inquisitive. Statement $4:$ Some students are not inquisitive. From the given four statements, find the two statements that $\text{CANNOT BE TRUE}$ simultaneously, assuming that there is at least …

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters. From the additional plates given in the options, which one of the combinations of additional plates would allow the player to construct a five-letter palindrome. The player should use all the five plates exactly …