Questions by Arjun / GATE Overflow for GATE CSE

1 votes

1 answer

161

GATE CSE 2024 | Set 1 | Question: 31
An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array? $82,90,101$ $82,11,93$ $131,11,93$ $131,111,90$

An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?$...

2.3k views

asked Feb 16

3 votes

3 answers

162

GATE CSE 2024 | Set 1 | Question: 32
Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$ Which one of the following options is CORRECT? $T(n)=\Theta(n \log \log n)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta\left(n^2 \log n\right)$ $T(n)=\Theta\left(n^2 \log \log n\right)$

Consider the following recurrence relation:$T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$Whic...

2.1k views

asked Feb 16

0 votes

2 answers

163

GATE CSE 2024 | Set 1 | Question: 33
Consider a binary min-heap containing $105$ distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of $k$ is $53$ $52$ $27$ $1$

Consider a binary min-heap containing $105$ distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of pos...

2.3k views

asked Feb 16

1 votes

3 answers

164

GATE CSE 2024 | Set 1 | Question: 34
The symbol $\rightarrow$ indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE? $(X, Y) \rightarrow(Z, W)$ implies $X \rightarrow(Z, W)$ $(X, Y) \rightarrow(Z, W)$ ... $(X, W) \rightarrow Z$ $(X \rightarrow Y$ and $Y \rightarrow Z)$ implies $X \rightarrow Z$

The symbol $\rightarrow$ indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?$(X, Y) \rightarrow(Z, W)$...

2.2k views

asked Feb 16

4 votes

2 answers

165

GATE CSE 2024 | Set 1 | Question: 35
Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$, rooted at $v$. Which of the following ... the tree $T$ There are no forward-edge in $G$ with respect to the tree $T$ The only edges in $G$ are the edges in $T$

Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth fir...

3.3k views

asked Feb 16

1 votes

1 answer

166

GATE CSE 2024 | Set 1 | Question: 36
Consider the following read-write schedule $\text{S}$ over three transactions $T_{1}, T_{2}$, and $T_{3}$ ... to $\text{S}$? $T_{1} T_{2} T_{3}$ $T_{1} T_{3} T_{2}$ $T_{3} T_{2} T_{1}$ $T_{3} T_{1} T_{2}$

Consider the following read-write schedule $\text{S}$ over three transactions $T_{1}, T_{2}$, and $T_{3}$, where the subscripts in the schedule indicate trans...

2.3k views

asked Feb 16

0 votes

2 answers

167

GATE CSE 2024 | Set 1 | Question: 37
Consider a Boolean expression given by $\text{F(X, Y, Z)}=\sum(3,5,6,7)$. Which of the following statements is/are CORRECT? $\text{F(X, Y, Z)}=\Pi(0,1,2,4)$ $\text{F(X, Y, Z)=X Y+Y Z+X Z}$ $\text{F(X, Y, Z)}$ is independent of input $\text{Y}$ $\text{F(X, Y, Z)}$ is independent of input $\text{X}$

Consider a Boolean expression given by $\text{F(X, Y, Z)}=\sum(3,5,6,7)$.Which of the following statements is/are CORRECT?$\text{F(X, Y, Z)}=\Pi(0,1,2,4)$ $\text{F(X, Y, ...

2.0k views

asked Feb 16

2 votes

2 answers

168

GATE CSE 2024 | Set 1 | Question: 38
Consider the following $\mathrm{C}$ ... the return value is less than $2^{10}$ If the inputs are $x=10, y=20$, then the return value is greater than $2^{20}$

Consider the following $\mathrm{C}$ function definition.int f (int x, int y){ for (int i=0 ; i<y ; i++ ) { x= x + x + y; } return x; }Which of the following stateme...

2.2k views

asked Feb 16

12 votes

3 answers

169

GATE CSE 2024 | Set 1 | Question: 39
Let $A$ be any $n \times m$ matrix, where $m>n$. Which of the following statements is/are TRUE about the system of linear equations $Ax=0$? There exist at least $m-n$ linearly independent solutions to this system There exist $m-n$ ... solution in which at least $m-n$ variables are $0$ There exists a solution in which at least $n$ variables are non-zero

Let $A$ be any $n \times m$ matrix, where $m>n$. Which of the following statements is/are TRUE about the system of linear equations $Ax=0$?There exist at least $m-n...

3.3k views

asked Feb 16

1 votes

1 answer

170

GATE CSE 2024 | Set 1 | Question: 40
Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. ... $4$ are distinguishable in $M$ States $2$ and $5$ are distinguishable in $M$ Any string $w$ with $n_0(w)=n_1(w)$ is in $L(M)$

Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\...

2.4k views

asked Feb 16

0 votes

1 answer

171

GATE CSE 2024 | Set 1 | Question: 41
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE? $G$ contains a complete subgraph with ... $n/k$ $G$ contains at least $k(k-1) / 2$ edges $G$ contains a vertex of degree at least $k$

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic nu...

2.0k views

asked Feb 16

3 votes

2 answers

172

GATE CSE 2024 | Set 1 | Question: 42
Consider the operators $\diamond$ and $\square$ defined by $a \diamond b=a+2 b, a \square b=a b$, for positive integers. Which of the following statements is/are TRUE? Operator $\diamond$ ... $\square$ obeys the distributive law Operator $\square$ over the operator $\diamond$ obeys the distributive law

Consider the operators $\diamond$ and $\square$ defined by $a \diamond b=a+2 b, a \square b=a b$, for positive integers. Which of the following statements is/are TRUE?Ope...

1.8k views

asked Feb 16

1 votes

2 answers

173

GATE CSE 2024 | Set 1 | Question: 43
Consider two set-associative cache memory architectures: $\text{WBC}$, which uses the write back policy, and $\text{WTC}$, which uses the write through policy. Both of them use the $\text{LRU}$ (Least Recently Used) block ... write miss in $\text{WTC}$ always writes the victim cache block to main memory before loading the missed block to the cache

Consider two set-associative cache memory architectures: $\text{WBC}$, which uses the write back policy, and $\text{WTC}$, which uses the write through policy...

2.2k views

asked Feb 16

0 votes

2 answers

174

GATE CSE 2024 | Set 1 | Question: 44
Consider a $512$ GB hard disk with $32$ storage surfaces. There are $4096$ sectors per track and each sector holds $1024$ bytes of data. The number of cylinders in the hard disk is _________.

Consider a $512$ GB hard disk with $32$ storage surfaces. There are $4096$ sectors per track and each sector holds $1024$ bytes of data. The number of cylinders in the ha...

1.6k views

asked Feb 16

0 votes

3 answers

175

GATE CSE 2024 | Set 1 | Question: 45
The baseline execution time of a program on a $2 \mathrm{GHz}$ single core machine is $100$ nanoseconds ( $n s)$. The code corresponding to $90 \%$ of the execution time can be fully parallelized. The overhead for using an ... the parallelized code for an equal amount of time. The number of cores that minimize the execution time of the program is __________.

The baseline execution time of a program on a $2 \mathrm{GHz}$ single core machine is $100$ nanoseconds ( $n s)$. The code corresponding to $90 \%$ of the execution time ...

1.8k views

asked Feb 16

1 votes

2 answers

176

GATE CSE 2024 | Set 1 | Question: 46
A given program has $25 \%$ load/store instructions. Suppose the ideal $\text{CPI}$ (cycles per instruction) without any memory stalls is $2$. The program exhibits $2 \%$ miss rate on instruction cache and $8 \%$ miss rate on data ... rounded off to two decimal places) achieved with a perfect cache (i.e., with NO data or instruction cache misses) is __________.

A given program has $25 \%$ load/store instructions. Suppose the ideal $\text{CPI}$ (cycles per instruction) without any memory stalls is $2$. The program exhibits $2 \%$...

2.6k views

asked Feb 16

1 votes

2 answers

177

GATE CSE 2024 | Set 1 | Question: 47
Consider the following code snippet using the fork () and wait () system calls. Assume that the code compiles and runs correctly, and that the system calls run successfully without any errors. int x=3; while (x>0){ fork (); printf("hello"); wait (NULL) ; X-- ; } The total number of times the printf statement is executed is __________.

Consider the following code snippet using the fork () and wait () system calls. Assume that the code compiles and runs correctly, and that the system calls run successful...

2.4k views

asked Feb 16

2 votes

2 answers

178

GATE CSE 2024 | Set 1 | Question: 48
Consider the entries shown below in the forwarding table of an $\text{IP}$ router. Each entry consists of an $\text{IP}$ prefix and the corresponding next hop router for packets whose destination $\text{IP}$ address matches the prefix. The notation " ... and $10.1.1.205$. The number of packets forwarded via the next hop router $\mathrm{R} 2$ is __________.

Consider the entries shown below in the forwarding table of an $\text{IP}$ router. Each entry consists of an $\text{IP}$ prefix and the corresponding next hop router for ...

2.1k views

asked Feb 16

0 votes

1 answer

179

GATE CSE 2024 | Set 1 | Question: 49
Let $G=(V, \Sigma, S, P)$ be a context-free grammar in Chomsky Normal Form with $\Sigma=\{a, b, c\}$ and $V$ containing $10$ variable symbols including the start symbol $S$. The string $w=a^{30} b^{30} c^{30}$ is derivable from $S$. The number of steps (application of rules) in the derivation $S \rightarrow^* w$ is __________.

Let $G=(V, \Sigma, S, P)$ be a context-free grammar in Chomsky Normal Form with $\Sigma=\{a, b, c\}$ and $V$ containing $10$ variable symbols including the start symbol $...

1.3k views

asked Feb 16

1 votes

2 answers

180

GATE CSE 2024 | Set 1 | Question: 50
The number of edges present in the forest generated by the $\text{DFS}$ traversal of an undirected graph $G$ with $100$ vertices is $40$. The number of connected components in $G$ is __________.

The number of edges present in the forest generated by the $\text{DFS}$ traversal of an undirected graph $G$ with $100$ vertices is $40$. The number of connected componen...

1.8k views

asked Feb 16

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true