Dark Mode

Recent questions tagged gatecse-2016-set1

48 votes

6 answers

1

GATE CSE 2016 Set 1 | Question: 43
Consider the transition diagram of a PDA given below with input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\Gamma = \{X,Z\}$. $Z$ is the initial stack symbol. Let $L$ ... on every input $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic context-free

Sandeep Singh asked in Theory of Computation Feb 12, 2016

by Sandeep Singh

16.8k views

65 votes

9 answers

2

GATE CSE 2016 Set 1 | Question: 38
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$ ... integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.

Sandeep Singh asked in DS Feb 12, 2016

by Sandeep Singh

23.9k views

44 votes

11 answers

3

GATE CSE 2016 Set 1 | Question: 35
What will be the output of the following $C$ program? void count (int n) { static int d=1; printf ("%d",n); printf ("%d",d); d++; if (n>1) count (n-1); printf ("%d",d); } void main(){ count (3); } $3 \ 1 \ 2 \ 2 \ 1 \ 3 \ 4 \ 4 \ 4$ $3 \ 1 \ 2 \ 1 \ 1 \ 1 \ 2 \ 2 \ 2$ $3 \ 1 \ 2 \ 2 \ 1 \ 3 \ 4$ $3 \ 1 \ 2 \ 1 \ 1 \ 1 \ 2$

Sandeep Singh asked in Programming in C Feb 12, 2016

by Sandeep Singh

15.4k views

117 votes

6 answers

4

GATE CSE 2016 Set 1 | Question: 40
$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE? If $e$ is the lightest edge of some ... some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.

Sandeep Singh asked in Algorithms Feb 12, 2016

by Sandeep Singh

26.1k views

85 votes

18 answers

5

GATE CSE 2016 Set 1 | Question: 39
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________

Sandeep Singh asked in Algorithms Feb 12, 2016

by Sandeep Singh

35.3k views

24 votes

7 answers

6

GATE CSE 2016 Set 1 | Question: 30
Consider the two cascade $2$ to $1$ multiplexers as shown in the figure . The minimal sum of products form of the output $X$ is $\overline{P} \ \overline {Q}+PQR$ $\overline{P} \ {Q}+QR$ $PQ +\overline{P} \ \overline{Q}R$ $\overline{Q} \ \overline{R} + PQR$

Sandeep Singh asked in Digital Logic Feb 12, 2016

by Sandeep Singh

9.3k views

47 votes

5 answers

7

GATE CSE 2016 Set 1 | Question: 44
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard ... enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.

Sandeep Singh asked in Theory of Computation Feb 12, 2016

by Sandeep Singh

12.4k views

100 votes

21 answers

8

GATE CSE 2016 Set 1 | Question: 54
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of $1$ $\text{megabyte}$ and the maximum output rate is $20$ $\text{megabytes}$ per $\text{second}$. Tokens arrive at a rate to ... to send $12$ $\text{megabytes}$ of data. The minimum time required to transmit the data is _____________ $\text{seconds}$.

Sandeep Singh asked in Computer Networks Feb 12, 2016

by Sandeep Singh

41.9k views

112 votes

7 answers

9

GATE CSE 2016 Set 1 | Question: 50
Consider the following proposed solution for the critical section problem. There are $n$ processes : $P_0....P_{n-1}$. In the code, function $\text{pmax}$ ... in the critical section at any time The bounded wait condition is satisfied The progress condition is satisfied It cannot cause a deadlock

Sandeep Singh asked in Operating System Feb 12, 2016

by Sandeep Singh

47.5k views

91 votes

9 answers

10

GATE CSE 2016 Set 1 | Question: 28
A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$, satisfies the following properties: $f(n)=f(n/2)$ if $n$ is even $f(n)=f(n+5)$ if $n$ is odd Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.

Sandeep Singh asked in Set Theory & Algebra Feb 12, 2016

by Sandeep Singh

21.5k views

45 votes

5 answers

11

GATE CSE 2016 Set 1 | Question: 48
Cylinder a disk queue with requests for $I/O$ to blocks on cylinders $47, 38, 121, 191, 87, 11, 92, 10.$ The C-LOOK scheduling algorithm is used. The head is initially at cylinder number $63$, moving towards larger cylinder ... are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is__________.

Sandeep Singh asked in Operating System Feb 12, 2016

by Sandeep Singh

19.3k views

66 votes

10 answers

12

GATE CSE 2016 Set 1 | Question: 27
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n-1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.

Sandeep Singh asked in Combinatory Feb 12, 2016

by Sandeep Singh

28.1k views

32 votes

6 answers

13

GATE CSE 2016 Set 1 | Question: 53
An IP datagram of size $1000$ $\text{bytes }$arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit) is $100$ $\text{bytes }$. Assume that the size of the IP header is $20$ $\text{bytes }.$ The number of fragments that the IP datagram will be divided into for transmission is________.

Sandeep Singh asked in Computer Networks Feb 12, 2016

by Sandeep Singh

16.6k views

68 votes

9 answers

14

GATE CSE 2016 Set 1 | Question: 49
Consider a computer system with ten physical page frames. The system is provided with an access sequence $(a_{1}, a_{2},....,a_{20}, a_{1}, a_{2},...a_{20})$, where each $a_{i}$ is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is_________.

Sandeep Singh asked in Operating System Feb 12, 2016

by Sandeep Singh

18.8k views

54 votes

4 answers

15

GATE CSE 2016 Set 1 | Question: 29
Consider the following experiment. Step 1. Flip a fair coin twice. Step 2. If the outcomes are (TAILS, HEADS) then output $Y$ and stop. Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output $N$ and stop. Step 4. If ... , TAILS), then go to Step $1.$ The probability that the output of the experiment is $Y$ is (up to two decimal places)

Sandeep Singh asked in Probability Feb 12, 2016

by Sandeep Singh

11.7k views

56 votes

4 answers

16

GATE CSE 2016 Set 1 | Question: 37
An operator $delete(i)$ for a binary heap data structure is to be designed to delete the item in the $i$-th node. Assume that the heap is implemented in an array and $i$ refers to the $i$-th index of the array. If the heap tree has depth $d$ (number of edges on the path from the root ... $O(d)$ but not $O(1)$ $O(2^d)$ but not $O(d)$ $O(d \ 2^d)$ but not $O(2^d)$

Sandeep Singh asked in DS Feb 12, 2016

by Sandeep Singh

15.2k views

59 votes

8 answers

17

GATE CSE 2016 Set 1 | Question: 42
Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$

Sandeep Singh asked in Theory of Computation Feb 12, 2016

by Sandeep Singh

26.6k views

30 votes

1 answer

18

GATE CSE 2016 Set 1 | Question: 34
The following function computes the maximum value contained in an integer array $P[ \ ]$ of size $n$ $(n>=1)$. int max (int *p,int n) { int a = 0, b=n-1; while (__________) { if (p[a]<= p[b]) {a = a+1;} else {b = b-1;} } return p[a]; } The missing loop condition is: $a\ \ != n$ $b\ \ != 0$ $b>(a+1)$ $b\ \ != a$

Sandeep Singh asked in Programming in C Feb 12, 2016

by Sandeep Singh

11.1k views

64 votes

4 answers

19

GATE CSE 2016 Set 1 | Question: 51
Consider the following two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects $\{O_1,\ldots,O_k \}$. This is done in the following ... freedom guarantee neither serializability nor deadlock-freedom guarantee serializability but not deadlock-freedom guarantee deadlock-freedom but not serializability.

Sandeep Singh asked in Databases Feb 12, 2016

by Sandeep Singh

21.4k views

69 votes

4 answers

20

GATE CSE 2016 Set 1 | Question: 36
What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed? a = 3; void n(x) { x = x * a; print (x); } void m(y) { a = 1 ; a = y - a; n(a); print (a); } void main () { m(a); } $6,2$ $6,6$ $4,2$ $4,4$

Sandeep Singh asked in Compiler Design Feb 12, 2016

by Sandeep Singh

23.9k views

26 votes

2 answers

21

GATE CSE 2016 Set 1 | Question: 46
Consider the following Syntax Directed Translation Scheme $( SDTS )$, with non-terminals $\{S,A \}$ and terminals $\{a,b \}$. $S \to aA \quad \{\text{print }1\}$ $S \to a \quad \{\text{print }2\}$ $A \to Sb \quad \{\text{print }3\}$ Using the above $SDTS$ ... printed by a bottom-up parser, for the input $aab$ is: $1 \ 3 \ 2 $ $2 \ 2 \ 3 $ $2 \ 3 \ 1 $ syntax error

Sandeep Singh asked in Compiler Design Feb 12, 2016

by Sandeep Singh

10.5k views

43 votes

6 answers

22

GATE CSE 2016 Set 1 | Question: 31
The size of the data count register of a $\text{DMA}$ controller is $16\;\text{bits}$. The processor needs to transfer a file of $29,154$ kilobytes from disk to main memory. The memory is byte addressable. The minimum number of times ... needs to get the control of the system bus from the processor to transfer the file from the disk to main memory is _________.

Sandeep Singh asked in CO and Architecture Feb 12, 2016

by Sandeep Singh

18.5k views

35 votes

4 answers

23

GATE CSE 2016 Set 1 | Question: 45
The attribute of three arithmetic operators in some programming language are given below. ... $2-5+1-7*3$ in this language is ________.

Sandeep Singh asked in Compiler Design Feb 12, 2016

by Sandeep Singh

10.0k views

58 votes

11 answers

24

GATE CSE 2016 Set 1 | Question: 55
A sender uses the Stop-and-Wait $\text{ARQ}$ protocol for reliable transmission of frames. Frames are of size $1000$ ... $100$ milliseconds. Assuming no frame is lost, the sender throughput is ________ bytes/ second.

Sandeep Singh asked in Computer Networks Feb 12, 2016

by Sandeep Singh

26.2k views

27 votes

4 answers

25

GATE CSE 2016 Set 1 | Question: 52
Consider that $B$ wants to send a message $m$ that is digitally signed to $A$. Let the pair of private and public keys for $A$ and $B$ be denoted by ${K_{x}}^-$ and ${K_{x}}^+$ for $x=A, B$, respectively. Let $K_{x}(m)$ represent the operation of encrypting $m$ with a ... $\left\{m, {K_{A}}^-(H(m))\right\}$ $\left\{m, {K_{A}}^+(m)\right\}$

Sandeep Singh asked in Computer Networks Feb 12, 2016

by Sandeep Singh

8.5k views

57 votes

17 answers

26

GATE CSE 2016 Set 1 | Question: 26
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.

Sandeep Singh asked in Combinatory Feb 12, 2016

by Sandeep Singh

25.7k views

73 votes

8 answers

27

GATE CSE 2016 Set 1 | Question: 32
The stage delays in a $4$-stage pipeline are $800, 500, 400$ and $300$ picoseconds. The first stage (with delay $800$ picoseconds) is replaced with a functionality equivalent design involving two stages with respective delays $600$ and $350$ picoseconds. The throughput increase of the pipeline is ___________ percent.

Sandeep Singh asked in CO and Architecture Feb 12, 2016

by Sandeep Singh

25.6k views

32 votes

3 answers

28

GATE CSE 2016 Set 1 | Question: 47
Consider a computer system with $40$-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires $48$ bits, then the size of the per-process page table is __________ megabytes.

Sandeep Singh asked in Operating System Feb 12, 2016

by Sandeep Singh

13.5k views

85 votes

9 answers

29

GATE CSE 2016 Set 1 | Question: 33
Consider a carry look ahead adder for adding two $n$-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is $\Theta (1)$ $\Theta (\log(n))$ $\Theta (\sqrt{n})$ $\Theta (n)$)

Sandeep Singh asked in Digital Logic Feb 12, 2016

by Sandeep Singh

30.9k views

143 votes

12 answers

30

GATE CSE 2016 Set 1 | Question: 41
Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $Top(S)$ returns the element at the top of $S$ without removing ... = Pop(S); Enqueue (Q, x); end end The maximum possible number of iterations of the while loop in the algorithm is _______.

Sandeep Singh asked in DS Feb 12, 2016

by Sandeep Singh

34.7k views

Page:

1
2
3
next »

Recent questions tagged gatecse-2016-set1