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

41 votes

7 answers

31

GATE CSE 2008 | Question: 54
Which of the following are true? A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation Multi-level access link (or display) arrangement is ... activation records II and V only I, III and IV only I, II and V only II, III and V only

Which of the following are true?A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursio...

Kathleen

21.0k views

Kathleen asked Sep 12, 2014

34 votes

2 answers

32

GATE CSE 2008 | Question: 53
Which of the following are regular sets? $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ $\left\{a^nb^m \mid n =2m \right\}$ $\left\{a^nb^m \mid n \neq m \right\}$ $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$ I and IV only I and III only I only IV only

Which of the following are regular sets?$\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$$\left\{a^nb^m \mid n =2m \right\}$$\left\{a^nb^m \mid n \neq m \right\}$$\lef...

Kathleen

9.6k views

Kathleen asked Sep 12, 2014

50 votes

11 answers

33

GATE CSE 2008 | Question: 52
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$

Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$$\epsilon + 0\left(10^*1+00\right)^*0$$\epsilon...

Kathleen

12.7k views

Kathleen asked Sep 12, 2014

66 votes

4 answers

34

GATE CSE 2008 | Question: 51
Match the following: $\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \left\{a^nb^mc^nd^m \mid n\: \geq1, m \geq 1\right\}$} \\\hline \text{F.} & \text{Number of formal ... $\text{E-R, F-P, G-Q, H-S}$ $\text{E-P, F-R, G-S, H-Q}$

Match the following:$$\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \lef...

Kathleen

14.1k views

Kathleen asked Sep 12, 2014

67 votes

4 answers

35

GATE CSE 2008 | Question: 49
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ ...

Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state)$$\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & ...

Kathleen

14.7k views

Kathleen asked Sep 12, 2014

27 votes

5 answers

36

GATE CSE 2008 | Question: 48
Which of the following statements is false? Every NFA can be converted to an equivalent DFA Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine Every regular language is also a context-free language Every subset of a recursively enumerable set is recursive

Which of the following statements is false?Every NFA can be converted to an equivalent DFAEvery non-deterministic Turing machine can be converted to an equivalent determi...

Kathleen

8.7k views

Kathleen asked Sep 12, 2014

41 votes

7 answers

37

GATE CSE 2008 | Question: 47
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$

We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is$\Theta(...

Kathleen

21.8k views

Kathleen asked Sep 12, 2014

129 votes

6 answers

38

GATE CSE 2008 | Question: 46
You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm ... $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ None of the above, as the tree cannot be uniquely determined

You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P...

Kathleen

39.1k views

Kathleen asked Sep 12, 2014

63 votes

11 answers

39

GATE CSE 2008 | Question: 45
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices

Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance toonly vertex $a$only vertices $...

Kathleen

27.7k views

Kathleen asked Sep 12, 2014

19 votes

2 answers

40

GATE CSE 2008 | Question: 44
The subset-sum problem is defined as follows: Given a set $S$ of $n$ positive integers and a positive integer $W$, determine whether there is a subset of $S$ whose elements sum to $W$. An algorithm $Q$ solves this problem in $O(nW)$ time. ... input is encoded in binary The subset sum problem belongs to the class $\text{NP}$ The subset sum problem is $\text{NP-hard}$

The subset-sum problem is defined as follows: Given a set $S$ of $n$ positive integers and a positive integer $W$, determine whether there is a subset of $S$ whose elemen...

Kathleen

13.4k views

Kathleen asked Sep 12, 2014

46 votes

4 answers

41

GATE CSE 2008 | Question: 43
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let $T(n)$ be the number of comparisons required to sort $n$ elements. Then $T(n) \leq 2T(n/5) + n$ $T(n) \leq T(n/5) + T(4n/5) + n$ $T(n) \leq 2T(4n/5) + n$ $T(n) \leq 2T(n/2) + n$

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fi...

Kathleen

16.4k views

Kathleen asked Sep 12, 2014

50 votes

6 answers

42

GATE CSE 2008 | Question: 41
A B-tree of order $4$ is built from scratch by $10$ successive insertions. What is the maximum number of node splitting operations that may take place? $3$ $4$ $5$ $6$

A B-tree of order $4$ is built from scratch by $10$ successive insertions. What is the maximum number of node splitting operations that may take place?$3$$4$$5$$6$

Kathleen

21.9k views

Kathleen asked Sep 12, 2014

79 votes

7 answers

43

GATE CSE 2008 | Question: 40
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is $\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is$\Theta(n)$$\Theta(\log n)...

Kathleen

36.7k views

Kathleen asked Sep 12, 2014

39 votes

5 answers

44

GATE CSE 2008 | Question: 39
Consider the following functions: $f(n) = 2^n$ $g(n) = n!$ $h(n) = n^{\log n}$ Which of the following statements about the asymptotic behavior of $f(n)$, $g(n)$ and $h(n)$ ... $h\left(n\right)=O\left(f\left(n\right)\right); g\left(n\right) = \Omega\left(f\left(n\right)\right)$

Consider the following functions:$f(n) = 2^n$$g(n) = n!$$h(n) = n^{\log n}$Which of the following statements about the asymptotic behavior of $f(n)$, $g(n)$ and $h(n)$ is...

Kathleen

16.4k views

Kathleen asked Sep 12, 2014

51 votes

7 answers

45

GATE CSE 2008 | Question: 38
In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is: before effective address calculation has started during effective address calculation after effective address calculation has completed after data cache lookup has completed

In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is:before effective address calculation has starteddur...

Kathleen

19.4k views

Kathleen asked Sep 12, 2014

39 votes

3 answers

46

GATE CSE 2008 | Question: 37, ISRO2009-38
The use of multiple register windows with overlap causes a reduction in the number of memory accesses for: Function locals and parameters Register saves and restores Instruction fetches $\text{I}$ only $\text{II}$ only $\text{III}$ only $\text{I}, \text{II}$ and $\text{III}$

The use of multiple register windows with overlap causes a reduction in the number of memory accesses for:Function locals and parametersRegister saves and restoresInstruc...

Kathleen

19.4k views

Kathleen asked Sep 12, 2014

55 votes

2 answers

47

GATE CSE 2008 | Question: 36
Which of the following are NOT true in a pipelined processor? Bypassing can handle all RAW hazards Register renaming can eliminate all register carried WAR hazards Control hazard penalties can be eliminated by dynamic branch prediction I and II only I and III only II and III only I, II and III

Which of the following are NOT true in a pipelined processor?Bypassing can handle all RAW hazardsRegister renaming can eliminate all register carried WAR hazardsControl h...

Kathleen

22.1k views

Kathleen asked Sep 12, 2014

61 votes

3 answers

48

GATE CSE 2008 | Question: 35
For inclusion to hold between two cache levels $L_1$ and $L_2$ in a multi-level cache hierarchy, which of the following are necessary? $L_1$ must be write-through cache $L_2$ must be a write-through cache The associativity of $L_2$ must be greater than that of $L_1$ The ... be at least as large as the $L_1$ cache IV only I and IV only I, II and IV only I, II, III and IV

For inclusion to hold between two cache levels $L_1$ and $L_2$ in a multi-level cache hierarchy, which of the following are necessary?$L_1$ must be write-through cache$L_...

Kathleen

24.6k views

Kathleen asked Sep 12, 2014

41 votes

3 answers

49

GATE CSE 2008 | Question: 34
Which of the following must be true for the RFE (Return From Exception) instruction on a general purpose processor? It must be a trap instruction It must be a privileged instruction An exception cannot be allowed to occur during execution of an RFE instruction I only II only I and II only I, II and III only

Which of the following must be true for the RFE (Return From Exception) instruction on a general purpose processor?It must be a trap instructionIt must be a privileged in...

Kathleen

11.9k views

Kathleen asked Sep 12, 2014

58 votes

4 answers

50

GATE CSE 2008 | Question: 33, ISRO2009-80
Which of the following is/are true of the auto-increment addressing mode? It is useful in creating self-relocating code If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation The amount of increment depends on the size of the data item accessed I only II only III only II and III only

Which of the following is/are true of the auto-increment addressing mode?It is useful in creating self-relocating codeIf it is included in an Instruction Set Architecture...

Kathleen

18.5k views

Kathleen asked Sep 12, 2014

23 votes

4 answers

51

GATE CSE 2008 | Question: 32
For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to non-uniform distribution of requests arm starting and stopping inertia higher capacity of tracks on the periphery of the platter use of unfair arm scheduling policies

For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due tonon-uniform distribution of requestsarm star...

Kathleen

13.5k views

Kathleen asked Sep 12, 2014

31 votes

7 answers

52

GATE CSE 2008 | Question: 31
$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent? $P ∨ \neg Q$ $\neg(\neg P ∧ Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$ Only I and II Only I, II and III Only I, II and IV All of I, II, III and IV

$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent?$P ∨ \neg Q$$\neg(\neg P ∧ Q)$$(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P �...

Kathleen

8.4k views

Kathleen asked Sep 12, 2014

71 votes

5 answers

53

GATE CSE 2008 | Question: 30
Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ ...

Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown autom...

Kathleen

14.2k views

Kathleen asked Sep 12, 2014

52 votes

3 answers

54

GATE CSE 2008 | Question: 29
Let $X$ be a random variable following normal distribution with mean $+1$ and variance $4$. Let $Y$ be another normal variable with mean $-1$ and variance unknown. If $P (X \leq -1) = P (Y \geq 2)$ , the standard deviation of $Y$ is $3$ $2$ $\sqrt{2}$ $1$

Let $X$ be a random variable following normal distribution with mean $+1$ and variance $4$. Let $Y$ be another normal variable with mean $-1$ and variance unknown. If $P ...

Kathleen

23.7k views

Kathleen asked Sep 11, 2014

31 votes

3 answers

55

GATE CSE 2008 | Question: 28
How many of the following matrices have an eigenvalue 1? $\left[\begin{array}{cc}1 & 0 \\0 & 0 \end{array} \right]\left[\begin{array}{cc}0 & 1 \\0 & 0 \end{array} \right] \left[\begin{array}{cc}1 & -1 \\1 & 1 \end{array} \right]$ and $\left[\begin{array}{cc}-1 & 0 \\1 & -1 \end{array} \right]$ one two three four

How many of the following matrices have an eigenvalue 1?$\left[\begin{array}{cc}1 & 0 \\0 & 0 \end{array} \right]\left[\begin{array}{cc}0 & 1 \\0 & 0 \end{array} \right] ...

Kathleen

8.7k views

Kathleen asked Sep 11, 2014

37 votes

8 answers

56

GATE CSE 2008 | Question: 27
Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is $0.6$. If she studies mathematics on a day, then the probability that she studies computer ... what is the probability that she studies computer science on Wednesday? $0.24$ $0.36$ $0.4$ $0.6$

Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next da...

Kathleen

7.8k views

Kathleen asked Sep 11, 2014

31 votes

4 answers

57

GATE CSE 2008 | Question: 26
If $P, Q, R$ are Boolean variables, then $(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$ simplifies to $P.\bar{Q}$ $P.\bar{R}$ $P.\bar{Q} + R$ $P.\bar{R} + Q$

If $P, Q, R$ are Boolean variables, then$(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$ simplifies to$P.\bar{Q}$$P.\bar{R}$$P.\bar{Q} + R$$P.\bar{R} + Q$

Kathleen

10.6k views

Kathleen asked Sep 11, 2014

36 votes

2 answers

58

GATE CSE 2008 | Question: 25
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve $3x^4-16x^3+24x^2+37$ is $0$ $1$ $2$ $3$

A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve $3x^4-16x^3+24x^2+37$ is$0$$1$$2$$3...

Kathleen

8.5k views

Kathleen asked Sep 11, 2014

17 votes

8 answers

59

GATE CSE 2008 | Question: 24
Let $P =\sum \limits_ {i\;\text{odd}}^{1\le i \le 2k} i$ and $Q = \sum\limits_{i\;\text{even}}^{1 \le i \le 2k} i$, where $k$ is a positive integer. Then $P = Q - k$ $P = Q + k$ $P = Q$ $P = Q + 2k$

Let $P =\sum \limits_ {i\;\text{odd}}^{1\le i \le 2k} i$ and $Q = \sum\limits_{i\;\text{even}}^{1 \le i \le 2k} i$, where $k$ is a positive integer. Then$P = Q - k$$P = Q...

Kathleen

6.0k views

Kathleen asked Sep 11, 2014

39 votes

7 answers

60

GATE CSE 2008 | Question: 23
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertex-cover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$

Which of the following statements is true for every planar graph on $n$ vertices?The graph is connectedThe graph is EulerianThe graph has a vertex-cover of size at most $...

Kathleen

65.1k views

Kathleen asked Sep 11, 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