Recent questions tagged gatecse-2006 / GATE Overflow for GATE CSE

23 votes

3 answers

31

GATE CSE 2006 | Question: 55
Consider these two functions and two statements S1 and S2 about them. int work1(int *a, int i, int j) { int x = a[i+2]; a[j] = x+1; return a[i+2] - 3; } int work2(int *a, int i, int j) { int t1 = i+2; int t2 = a[t1]; a[j] = ... CPU time) of work2 compared to work1 S1 is false and S2 is false S1 is false and S2 is true S1 is true and S2 is false S1 is true and S2 is true

Consider these two functions and two statements S1 and S2 about them. int work1(int *a, int i, int j) { int x = a[i+2]; a[j] = x+1; return a[i+2] - 3; }int work2(int *a, ...

Rucha Shelke

10.4k views

Rucha Shelke asked Sep 26, 2014

66 votes

10 answers

32

GATE CSE 2006 | Question: 54
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ ... time in the key comparison mode Takes $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number

Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a...

Rucha Shelke

29.4k views

Rucha Shelke asked Sep 26, 2014

44 votes

3 answers

33

GATE CSE 2006 | Question: 53
Consider the following C-function in which $a[n]$ and $b[m]$ are two sorted integer arrays and $c[n+m]$ be another integer array, void xyz(int a[], int b [], int c []){ int i,j,k; i=j=k=0; while ((i<n) && (j<m)) if (a[i] < b[j]) c[k++] = ... $b[m-1]\leq a[i]$ if $j=m$ only (i) only (ii) either (i) or (ii) but not both neither (i) nor (ii)

Consider the following C-function in which $a[n]$ and $b[m]$ are two sorted integer arrays and $c[n+m]$ be another integer array,void xyz(int a[], int b [], int c []){ in...

Rucha Shelke

11.6k views

Rucha Shelke asked Sep 26, 2014

44 votes

4 answers

34

GATE CSE 2006 | Question: 52
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$

The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?$\T...

Rucha Shelke

53.4k views

Rucha Shelke asked Sep 26, 2014

58 votes

7 answers

35

GATE CSE 2006 | Question: 51, ISRO2016-34
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$

Consider the following recurrence:$ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$Which one of the following is true?$ T(n)=\Theta (\log\log n)$$ T(n)=\Theta (\log n)$$ T(n...

Rucha Shelke

28.6k views

Rucha Shelke asked Sep 26, 2014

18 votes

4 answers

36

GATE CSE 2006 | Question: 50
A set $X$ can be represented by an array $x[n]$ as follows: $x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & \text{otherwise} \end{cases}$ Consider the following algorithm in which $x$, $y$, and $z$ are Boolean arrays of size $n$: algorithm zzz ... set $Z$ computed by the algorithm is: $(X\cup Y)$ $(X\cap Y)$ $(X-Y)\cap (Y-X)$ $(X-Y)\cup (Y-X)$

A set $X$ can be represented by an array $x[n]$ as follows: $x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & \text{otherwise} \end{cases}$Consider the ...

Rucha Shelke

5.1k views

Rucha Shelke asked Sep 26, 2014

88 votes

8 answers

37

GATE CSE 2006 | Question: 49
An implementation of a queue $Q$, using two stacks $S1$ and $S2$, is given below: void insert (Q, x) { push (S1, x); } void delete (Q) { if (stack-empty(S2)) then if (stack-empty(S1)) then { print( Q is empty ); return; } else while (!(stack-empty(S1))){ x=pop ... and $2m\leq y\leq 2n $ $ 2m\leq x<2n $ and $2m\leq y\leq n+m $ $ 2m\leq x<2n $ and $2m\leq y\leq 2n $

An implementation of a queue $Q$, using two stacks $S1$ and $S2$, is given below: void insert (Q, x) { push (S1, x); } void delete (Q) { if (stack-empty(S2)) then if (sta...

Rucha Shelke

33.0k views

Rucha Shelke asked Sep 26, 2014

90 votes

12 answers

38

GATE CSE 2006 | Question: 48
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$ ... exist a cycle in $G$ containing $u$ and $ν$ There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $...

Rucha Shelke

21.1k views

Rucha Shelke asked Sep 26, 2014

21 votes

2 answers

39

GATE CSE 2006 | Question: 47
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? $(a-b),(d-f),(b-f),(d-c),(d-e)$ $(a-b),(d-f),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(b-f),(d-e),(d-c)$

Consider the following graph:Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? $(a-...

Rucha Shelke

9.6k views

Rucha Shelke asked Sep 26, 2014

47 votes

8 answers

40

GATE CSE 2006 | Question: 46
Station $A$ needs to send a message consisting of $9$ packets to Station $B$ using a sliding window (window size $3$) and go-back-$n$ error control strategy. All packets are ready and immediately available for transmission. If every $5$th packet that $A$ ... what is the number of packets that $A$ will transmit for sending the message to $B$? $12$ $14$ $16$ $18$

Station $A$ needs to send a message consisting of $9$ packets to Station $B$ using a sliding window (window size $3$) and go-back-$n$ error control strategy. All packets ...

Rucha Shelke

41.4k views

Rucha Shelke asked Sep 26, 2014

38 votes

4 answers

41

GATE CSE 2006 | Question: 45
Two computers $C1$ and $C2$ are configured as follows. $C1$ has IP address $203.197.2.53$ and netmask $255.255.128.0$. $C2$ has IP address $203.197.75.201$ and netmask $255.255.192.0$. Which one of the following statements is true? $C1$ and ... $C2$ assumes $C1$ is on a different network $C1$ and $C2$ both assume they are on different networks.

Two computers $C1$ and $C2$ are configured as follows. $C1$ has IP address $203.197.2.53$ and netmask $255.255.128.0$. $C2$ has IP address $203.197.75.201$ and netmask $2...

Rucha Shelke

14.5k views

Rucha Shelke asked Sep 26, 2014

55 votes

12 answers

42

GATE CSE 2006 | Question: 44
Station $A$ uses $32\; \text{byte}$ packets to transmit messages to Station $B$ using a sliding window protocol. The round trip delay between A and $B$ is $80\; \text{milliseconds}$ and the bottleneck bandwidth on the path between $A$ and $B$ is $128\; \text{kbps}$ . What is the optimal window size that $A$ should use? $20$ $40$ $160$ $320$

Station $A$ uses $32\; \text{byte}$ packets to transmit messages to Station $B$ using a sliding window protocol. The round trip delay between A and $B$ is $80\; \text{mil...

Rucha Shelke

26.9k views

Rucha Shelke asked Sep 26, 2014

44 votes

5 answers

43

GATE CSE 2006 | Question: 43
Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction bbs reg, pos, label jumps to label if bit in position pos of register operand reg is one. A register is $32$ -bits wide and the bits are numbered $0$ to $31,$ bit ... $ mask\leftarrow \text{0xffffffff} << pos$ $ mask\leftarrow pos $ $ mask\leftarrow \text{0xf}$

Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction “bbs reg, pos, label” jumps to label if bit in position pos of register operand reg...

Rucha Shelke

11.1k views

Rucha Shelke asked Sep 26, 2014

50 votes

9 answers

44

GATE CSE 2006 | Question: 42
A CPU has a five-stage pipeline and runs at $1$ GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new ... : $\text{1.0 second}$ $\text{1.2 seconds}$ $\text{1.4 seconds}$ $\text{1.6 seconds}$

A CPU has a five-stage pipeline and runs at $1$ GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the...

Rucha Shelke

21.2k views

Rucha Shelke asked Sep 26, 2014

45 votes

4 answers

45

GATE CSE 2006 | Question: 41
A CPU has a cache with block size $64$ bytes. The main memory has $k$ banks, each bank being $c$ bytes wide. Consecutive $c$ − byte chunks are mapped on consecutive banks with wrap-around. All the $k$ banks can be accessed in parallel, but two ... the latency of retrieving a cache block starting at address zero from main memory is: $92$ ns $104$ ns $172$ ns $184$ ns

A CPU has a cache with block size $64$ bytes. The main memory has $k$ banks, each bank being $c$ bytes wide. Consecutive $c$ − byte chunks are mapped on consecutive ban...

Rucha Shelke

14.2k views

Rucha Shelke asked Sep 26, 2014

91 votes

7 answers

46

GATE CSE 2006 | Question: 40
Consider numbers represented in 4-bit Gray code. Let $ h_{3}h_{2}h_{1}h_{0}$ be the Gray code representation of a number $n$ and let $ g_{3}g_{2}g_{1}g_{0}$ be the Gray code of $ (n+1)(modulo 16)$ ... $ g_{3}(h_{3}h_{2}h_{1}h_{0})=\sum (0,1,6,7,10,11,12,13) $

Consider numbers represented in 4-bit Gray code. Let $ h_{3}h_{2}h_{1}h_{0}$ be the Gray code representation of a number $n$ and let $ g_{3}g_{2}g_{1}g_{0}$ be the Gray...

Rucha Shelke

20.5k views

Rucha Shelke asked Sep 26, 2014

54 votes

6 answers

47

GATE CSE 2006 | Question: 39
We consider the addition of two $2's$ complement numbers $ b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $ c_{n-1}c_{n-2}\dots c_{0}$ and the ... $ c_{out}\oplus c_{n-1}$ $ a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$

We consider the addition of two $2's$ complement numbers $ b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers i...

Rucha Shelke

18.7k views

Rucha Shelke asked Sep 26, 2014

61 votes

4 answers

48

GATE CSE 2006 | Question: 38
Consider a Boolean function $ f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $ i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle $ ... $ wx\overline{y} \overline{z}, xz, w\overline{x}yz$ $ wx\overline{y}, wyz, wxz, \overline{w}xz, x\overline{y}z, xyz$

Consider a Boolean function $ f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors...

Rucha Shelke

21.1k views

Rucha Shelke asked Sep 26, 2014

33 votes

7 answers

49

GATE CSE 2006 | Question: 37
Consider the circuit in the diagram. The $\oplus$ operator represents Ex-OR. The D flip-flops are initialized to zeroes (cleared). The following data: $100110000$ is supplied to the “data” terminal in nine clock cycles. After that the values of $q_{2}q_{1}q_{0}$ are: $000$ $001$ $010$ $101$

Consider the circuit in the diagram. The $\oplus$ operator represents Ex-OR. The D flip-flops are initialized to zeroes (cleared).The following data: $100110000$ is suppl...

Rucha Shelke

15.8k views

Rucha Shelke asked Sep 22, 2014

70 votes

6 answers

50

GATE CSE 2006 | Question: 36
Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ ...

Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ the carry in, the function that represents the carry generate function when these two numbers ...

Rucha Shelke

15.1k views

Rucha Shelke asked Sep 22, 2014

34 votes

2 answers

51

GATE CSE 2006 | Question: 35
Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$ $x\bar{z}+xy+\bar{y}z$ $x\bar{z}+xy+\overline{yz}$ $xz+xy+\overline{yz}$ $xz+x\bar{y}+\bar{y}z$

Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$$x\bar{z}+xy+\bar{y}z$$x\bar{z}+xy+\overline{yz}$$xz+xy+\overline...

Rucha Shelke

9.7k views

Rucha Shelke asked Sep 22, 2014

93 votes

8 answers

52

GATE CSE 2006 | Question: 34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$

Rucha Shelke

34.3k views

Rucha Shelke asked Sep 22, 2014

57 votes

2 answers

53

GATE CSE 2006 | Question: 33
Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false? $L_1 \cap L_2$ is a deterministic CFL $L_3 \cap L_1$ is recursive $L_1 \cup L_2$ is context free $L_1 \cap L_2 \cap L_3$ is recursively enumerable

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the followi...

Rucha Shelke

12.5k views

Rucha Shelke asked Sep 18, 2014

64 votes

4 answers

54

GATE CSE 2006 | Question: 32, ISRO2016-35
Consider the following statements about the context free grammar $G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $ $G$ is ambiguous $G$ produces all strings with equal number of $a$'s ... combination below expresses all the true statements about $G$? I only I and III only II and III only I, II and III

Consider the following statements about the context free grammar$$G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $$$G...

Rucha Shelke

28.8k views

Rucha Shelke asked Sep 18, 2014

8 votes

2 answers

55

GATE CSE 2006 | Question: 31
Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? Both DHAM$_3$ ... NP-hard, but DHAM$_3$ is not DHAM$_3$ is NP-hard, but SHAM$_3$ is not Neither DHAM$_3$ nor SHAM$_3$ is NP-hard

Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian...

Rucha Shelke

4.6k views

Rucha Shelke asked Sep 18, 2014

53 votes

3 answers

56

GATE CSE 2006 | Question: 30
For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let $L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$Which ... following statements is true? $L$ is recursively enumerable, but not recursive $L$ is recursive, but not context-free $L$ is context-free, but not regular $L$ is regular

For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let$$L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod ...

Rucha Shelke

7.7k views

Rucha Shelke asked Sep 18, 2014

83 votes

8 answers

57

GATE CSE 2006 | Question: 29
If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$'s in $s$ and $n_1(s)$ the number of $1$'s in $s$. Which one of the following languages is not regular? $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime } \right \}$ ... $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$

If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$’s in $s$ and $n_1(s)$ the number of $1$’s in $s$. Which one of the following languages i...

Rucha Shelke

19.6k views

Rucha Shelke asked Sep 18, 2014

37 votes

8 answers

58

GATE CSE 2006 | Question: 28
A logical binary relation $\odot$ ... $(\sim A\odot B)$ $\sim(A \odot \sim B)$ $\sim(\sim A\odot\sim B)$ $\sim(\sim A\odot B)$

A logical binary relation $\odot$, is defined as follows: $$\begin{array}{|l|l|l|} \hline \textbf{A} & \textbf{B}& \textbf{A} \odot \textbf{B}\\\hline \text{True} & \text...

Rucha Shelke

5.9k views

Rucha Shelke asked Sep 18, 2014

45 votes

3 answers

59

GATE CSE 2006 | Question: 27
Consider the following propositional statements: $P_1: ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))$ $P_2: ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))$ Which one of the following is true? $P_1$ is a tautology, but not $P_2$ $P_2$ is a tautology, but not $P_1$ $P_1$ and $P_2$ are both tautologies Both $P_1$ and $P_2$ are not tautologies

Consider the following propositional statements:$P_1: ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))$$P_2: ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))$Which one of...

Rucha Shelke

8.5k views

Rucha Shelke asked Sep 18, 2014

54 votes

6 answers

60

GATE CSE 2006 | Question: 26
Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened. ...

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or ...

Rucha Shelke

9.3k views

Rucha Shelke asked Sep 18, 2014

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