GATE CS question library

Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i=1, \ldots, n$ …

Consider functions $\textsf{Function\_1}$ and $\textsf{Function\_2}$ expressed in pseudocode as follows: Function_1 while n>1 do for i=1 to n do x = x + 1; end for n = ⌊n/2⌋; end while Function_2 for i = 1 to 100 * n do x = x + 1; end for Let $f_{1}(n)$ and $f_{2}(n)$ denote the number of times the statement $\textsf{“x = x + 1”}$ is executed in …

Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) either $A \subsetneq B$ or $B \subsetneq A$. For any vertex $A$ in $G$, the set of all possible orderings in which the …

Consider a computer system with $57$-bit virtual addressing using multi-level tree-structured page tables with $\mathrm{L}$ levels for virtual to physical address translation. The page size is $4 \mathrm{~KB}(1 \mathrm{~KB}=1024 \mathrm{~B})$ and a page table entry at any of the levels occupies $8$ bytes. The value of $\mathrm{L}$ is …

Consider the following two-dimensional array $\text{D}$ in the $\text{C}$ programming language, which is stored in row-major order: int D[128][128]; Demand paging is used for allocating memory and each physical page frame holds $512$ elements of the array $\text{D}.$ The Least Recently Used $\text{(LRU)}$ page-replacement policy is used by the …

Consider a sequence $a$ of elements $a_{0}=1, a_{1}=5, a_{2}=7, a_{3}=8, a_{4}=9$, and $a_{5}=2$. The following operations are performed on a stack $S$ and a queue $Q,$ both of which are initially empty. $\textsf{push}$ the elements of $a$ from $a_{0}$ to $a_{5}$ in that order into $S$. $\textsf{enqueue}$ the elements of $a$ from …

Consider the following table named $\text{Student}$ in a relational database. The primary key of this table is $\text{rollNum}.$ $\text{Student}$ …

Consider the syntax directed translation given by the following grammar and semantic rules. Here $N, I, F$ and $B$ are non-terminals. $N$ is the starting non-terminal, and $\#, \mathbf{0}$ and $\mathbf{1}$ are lexical tokens corresponding to input letters $\text{“\#", “0" and “1"},$ respectively. $X.val$ denotes the synthesized attribute (a …

Consider the language $L$ over the alphabet $\{0,1\}$, given below: $$L=\left\{w \in\{0,1\}^{*} \mid w \text{ does not contain three or more consecutive } 1 \text{ 's }\right\} .$$ The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.

Consider a database of fixed-length records, stored as an ordered file. The database has $25,000$ records, with each record being $100$ bytes, of which the primary key occupies $15$ bytes. The data file is block-aligned in that each data record is fully contained within a block. The database is indexed by a primary index file, which is also stored as a …

An $8$-way set associative cache of size $64 \mathrm{~KB} \;(1 \mathrm{~KB}=1024\; \text{bytes})$ is used in a system with $32$-bit address. The address is sub-divided into $\text{TAG, INDEX},$ and $\text{BLOCK OFFSET.}$ The number of bits in the $\text{TAG}$ is ___________.

The forwarding table of a router is shown below. …

We reached the station late, and _______ missed the train.

Kind : _______ : : Often : Frequently (By word meaning)

A series of natural numbers $F_1, F_2, F_3, F_4, F_5, F_6, F_7, \ldots$ obeys $F_{n+1}=F_n+F_{n-1}$ for all integers $n \geq 2$. If $F_6=37,$ and $F_7=60,$ then what is $F_1 ?$

A survey for a certain year found that $90\%$ of pregnant women received medical care at least once before giving birth. Of these women, $60\%$ received medical care from doctors, while $40\%$ received medical care from other healthcare providers. Given this information, which one of the following statements can be inferred with certainty?

Looking at the surface of a smooth $3$-dimensional object from the outside, which one of the following options is $\text{TRUE}?$

The country of Zombieland is in distress since more than $75 \%$ of its working population is suffering from serious health issues. Studies conducted by competent health experts concluded that a complete lack of physical exercise among its working population was one of the leading causes of their health issues. As one of the measures to address the …

Consider two functions of time $(t),$ $$\begin{gathered} f(t)=0.01 t^2 \\ g(t)=4 t \end{gathered}$$ where $0<t<\infty.$ Now consider the following two statements: For some $t>0, g(t)>f(t)$. There exists a $T,$ such that $f(t)>g(t)$ for all $t>T$. Which one of the following options is $\text{TRUE}?$

Which one of the following sentence sequences creates a coherent narrative? Once on the terrace, on her way to her small room in the corner, she notices the man right away. She begins to pant by the time she has climbed all the stairs. Mina has bought vegetables and rice at the market, so her bags are heavy. He was leaning against the parapet, watching the …