The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged gate2006
GATE 2006 questions from Computer Science & Engineering
+12
votes
1
answer
1
GATE200677
Statement for Linked Answer Questions 76 & 77: A $3$ary max heap is like a binary max heap, but instead of $2$ children, nodes have $3$ children. A $3$ary heap can be represented by an array as follows: The root is stored in the first location, $a[0]$, nodes in the next level, from left to right, is ... 3, 2, 1$ $10, 9, 4, 5, 7, 6, 8, 2, 1, 3$ $10, 8, 6, 9, 7, 2, 3, 4, 1, 5$
asked
Nov 27, 2016
in
DS
by
Arjun
Veteran
(
363k
points)

984
views
gate2006
datastructure
heap
normal
+11
votes
4
answers
2
GATE200685
The grammar $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \varepsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$ generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In that grammar what is the length of the derivation (number of steps starting from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$ $max (l,m) + 2$ $l + m + 2$ $l + m + 3$ $max (l,m) + 3$
asked
Nov 7, 2016
in
Compiler Design
by
jothee
Veteran
(
106k
points)

704
views
gate2006
compilerdesign
grammar
normal
+1
vote
2
answers
3
GATE200685
Find the grammar that generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In that grammar what is the length of the derivation (number of steps starring from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$ $max (l,m) + 2$ $l + m + 2$ $l + m + 3$ $max (l,m) + 3$
asked
Nov 7, 2016
in
Compiler Design
by
jothee
Veteran
(
106k
points)

363
views
gate2006
compilerdesign
grammar
normal
+10
votes
1
answer
4
GATE200683
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the ... Let host $H1$ send out a broadcast ping packet. Which of the following options represents the correct forwarding table on $B3$?
asked
Nov 7, 2016
in
Computer Networks
by
jothee
Veteran
(
106k
points)

1.4k
views
gate2006
computernetworks
bridges
normal
+20
votes
3
answers
5
GATE200673
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
asked
Apr 24, 2016
in
Graph Theory
by
jothee
Veteran
(
106k
points)

1.8k
views
gate2006
graphtheory
normal
graphconnectivity
+30
votes
4
answers
6
GATE200672
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n2}$ $2^{n3}\times 3$ $2^{n1}$
asked
Apr 24, 2016
in
Graph Theory
by
jothee
Veteran
(
106k
points)

2.8k
views
gate2006
graphtheory
normal
degreeofgraph
+12
votes
4
answers
7
GATE200675
Consider two cache organizations. First one is $32$ $kB$ $2$way set associative with $32$ $byte$ block size, the second is of same size but direct mapped. The size of an address is $32$ $bits$ in both cases . A $2$to$1$ multiplexer has latency of $0.6 ns$ while a $k ... is $h_1$ while that of direct mapped is $h_2$. The value of $h_2$ is: $2.4$ $ns$ $2.3$ $ns$ $1.8$ $ns$ $1.7$ $ns$
asked
Apr 24, 2016
in
CO & Architecture
by
jothee
Veteran
(
106k
points)

1.9k
views
gate2006
coandarchitecture
cachememory
normal
+22
votes
3
answers
8
GATE200679
Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set ... is disabled at the beginning of the barrier and reenabled at the end. The variable process_left is made private instead of shared
asked
Apr 24, 2016
in
Operating System
by
jothee
Veteran
(
106k
points)

1.9k
views
gate2006
operatingsystem
processsynchronization
normal
+14
votes
3
answers
9
GATE200681
A CPU has a $32$ $KB$ direct mapped cache with $128$ byteblock size. Suppose $A$ is two dimensional array of size $512 \times512$ with elements that occupy $8bytes$ each. Consider the following two $C$ code segments, $P1$ and $P2$. $P1$: for (i=0; i<512; i++) { for (j=0; j<512; ... $P2$ be $M2$. The value of the ratio $\frac{M_{1}}{M_{2}}$: $0$ $\frac{1}{16}$ $\frac{1}{8}$ $16$
asked
Apr 23, 2016
in
CO & Architecture
by
jothee
Veteran
(
106k
points)

1.7k
views
coandarchitecture
cachememory
normal
gate2006
+25
votes
4
answers
10
GATE200684
Which one of the following grammars generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$? $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid a\mid b$ $A\rightarrow aA\mid \varepsilon$ $B\rightarrow Bb\mid \varepsilon$ $S\ ... $B\rightarrow Bb\mid \varepsilon$ $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \varepsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$
asked
Sep 26, 2014
in
Compiler Design
by
Rucha Shelke
Active
(
3.7k
points)

2.1k
views
gate2006
compilerdesign
grammar
normal
theoryofcomputation
+25
votes
4
answers
11
GATE200682
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root ... B1, B3, B5, B2, B4}$ $\text{B1, B5, B2, B3, B4}$ $\text{B1, B3, B4, B5, B2}$
asked
Sep 26, 2014
in
Computer Networks
by
Rucha Shelke
Active
(
3.7k
points)

5.3k
views
gate2006
computernetworks
bridges
normal
+18
votes
7
answers
12
GATE200680
A CPU has a $32 KB$ direct mapped cache with $128$ byteblock size. Suppose A is two dimensional array of size $512 \times512$ with elements that occupy $8$bytes each. Consider the following two C code segments, $P1$ and $P2$. P1: for (i=0; i<512; i++) { ... cache misses experienced by $P1$ be $M_{1}$and that for $P2$ be $M_{2}$. The value of $M_{1}$ is: $0$ $2048$ $16384$ $262144$
asked
Sep 26, 2014
in
CO & Architecture
by
Rucha Shelke
Active
(
3.7k
points)

3.4k
views
gate2006
coandarchitecture
cachememory
normal
+35
votes
3
answers
13
GATE200678
Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the ... to $10$ need not be inside a critical section The barrier implementation is correct if there are only two processes instead of three.
asked
Sep 26, 2014
in
Operating System
by
Rucha Shelke
Active
(
3.7k
points)

4.4k
views
gate2006
operatingsystem
processsynchronization
normal
+15
votes
2
answers
14
GATE200676
Statement for Linked Answer Questions 76 & 77: A $3$ary max heap is like a binary max heap, but instead of $2$ children, nodes have $3$ children. A $3$ary heap can be represented by an array as follows: The root is stored in the first location, $a[0]$, nodes in the next level, from left to right, is ... , 3, 5, 6, 8, 9$ $9, 6, 3, 1, 8, 5$ $9, 3, 6, 8, 5, 1$ $9, 5, 6, 8, 3, 1$
asked
Sep 26, 2014
in
DS
by
Rucha Shelke
Active
(
3.7k
points)

1.1k
views
gate2006
datastructure
heap
normal
+28
votes
3
answers
15
GATE200674
Consider two cache organizations. First one is $32 \hspace{0.2cm} KB$ $2way$ set associative with $32 \hspace{0.2cm} byte$ block size, the second is of same size but direct mapped. The size of an address is $32 \hspace{0.2cm} bits$ in both cases . A $2to1$ multiplexer has latency of $0. ... . The value of $h_1$ is: $2.4 \text{ ns} $ $2.3 \text{ ns}$ $1.8 \text{ ns}$ $1.7 \text{ ns}$
asked
Sep 26, 2014
in
CO & Architecture
by
Rucha Shelke
Active
(
3.7k
points)

5.8k
views
gate2006
coandarchitecture
cachememory
normal
+29
votes
4
answers
16
GATE200671
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
asked
Sep 26, 2014
in
Graph Theory
by
Rucha Shelke
Active
(
3.7k
points)

3.3k
views
gate2006
graphtheory
normal
degreeofgraph
+14
votes
2
answers
17
GATE200670
The following functional dependencies are given: $ AB\rightarrow CD,AF\rightarrow D,DE\rightarrow F,$$C\rightarrow G,F\rightarrow E,G\rightarrow A $ Which one of the following options is false? $ \left \{ CF \right \}^{*}=\left \{ ACDEFG \right \}$ $ \left \{ BG \right \}^{*}=\left \ ... \{ AF \right \}^{*}=\left \{ ACDEFG \right \}$ $ \left \{ AB \right \}^{*}=\left \{ ABCDG \right \}$
asked
Sep 26, 2014
in
Databases
by
Rucha Shelke
Active
(
3.7k
points)

1.7k
views
gate2006
databases
functionaldependencies
normal
+18
votes
6
answers
18
GATE200669
Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Assume that amounts 6000, ... Plan 1 executes faster than Plan 2 for all databases For x = 9000, Plan I executes slower than Plan 2 for all databases
asked
Sep 26, 2014
in
Databases
by
Rucha Shelke
Active
(
3.7k
points)

2.4k
views
gate2006
databases
sql
normal
+29
votes
4
answers
19
GATE200668
Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. ... for which Query3 returns strictly fewer rows than Query2 There exist databases for which Query4 will encounter an integrity violation at runtime
asked
Sep 26, 2014
in
Databases
by
Rucha Shelke
Active
(
3.7k
points)

3.6k
views
gate2006
databases
sql
normal
+37
votes
3
answers
20
GATE200667
Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. Ties are not broke but ranks are skipped: if ... assigning ranks using ODBC. Which two of the above statements are correct? 2 and 5 1 and 3 1 and 4 3 and 5
asked
Sep 26, 2014
in
Databases
by
Rucha Shelke
Active
(
3.7k
points)

4.4k
views
gate2006
databases
sql
normal
+31
votes
1
answer
21
GATE200666
Consider the following snapshot of a system running $n$ processes. Process $i$ is holding $x_i$ instances of a resource $R$, $ 1\leq i\leq n$ . Currently, all instances of $R$ are occupied. Further, for all $i$, process $i$ has placed a request for an additional $y_i$ instances while holding the $x_i$ ... geq \min_{k\neq p,q}y_{k}$ $ \max(x_{p},x_{q})>1$ $ \min(x_{p},x_{q})>1$
asked
Sep 26, 2014
in
Operating System
by
Rucha Shelke
Active
(
3.7k
points)

3.6k
views
gate2006
operatingsystem
resourceallocation
normal
+20
votes
6
answers
22
GATE200665
Consider three processes, all arriving at time zero, with total execution time of $10$, $20$ and $30$ units, respectively. Each process spends the first $\text{20%}$ of execution time doing I/O, the next $\text{70%}$ of time doing computation, and the last $\text{10%}$ of time ... what percentage of time does the CPU remain idle? $\text{0%}$ $\text{10.6%}$ $\text{30.0%}$ $\text{89.4%}$
asked
Sep 26, 2014
in
Operating System
by
Rucha Shelke
Active
(
3.7k
points)

3.7k
views
gate2006
operatingsystem
processschedule
normal
+17
votes
2
answers
23
GATE200664
Consider three processes (process id $0$, $1$, $2$ respectively) with compute time bursts $2$, $4$ and $8$ time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turn around time is: $13$ units $14$ units $15$ units $16$ units
asked
Sep 26, 2014
in
Operating System
by
Rucha Shelke
Active
(
3.7k
points)

2.5k
views
gate2006
operatingsystem
processschedule
normal
+37
votes
4
answers
24
GATE200663, UGCNETJune2012III45
A computer system supports $32$bit virtual addresses as well as $32$bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the ... made more efficient now Hardware support for memory management is no longer needed CPU scheduling can be made more efficient now
asked
Sep 26, 2014
in
Operating System
by
Rucha Shelke
Active
(
3.7k
points)

4.7k
views
gate2006
operatingsystem
virtualmemory
normal
ugcnetjune2012iii
+25
votes
1
answer
25
GATE200662, ISRO201650
A CPU generates $32$bit virtual addresses. The page size is $4$ KB. The processor has a translation lookaside buffer (TLB) which can hold a total of $128$ page table entries and is $4$way set associative. The minimum size of the TLB tag is: $\text{11 bits}$ $\text{13 bits}$ $\text{15 bits}$ $\text{20 bits}$
asked
Sep 26, 2014
in
Operating System
by
Rucha Shelke
Active
(
3.7k
points)

6.9k
views
gate2006
operatingsystem
virtualmemory
normal
isro2016
+53
votes
4
answers
26
GATE200661
The atomic fetchandset $x, y$ instruction unconditionally sets the memory location $x$ to $1$ and fetches the old value of $x$ in $y$ without allowing any intervening access to the memory location $x$. Consider the following implementation of $P$ and $V$ ... pair of normal load/store can be used The implementation of $V$ is wrong The code does not implement a binary semaphore
asked
Sep 26, 2014
in
Operating System
by
Rucha Shelke
Active
(
3.7k
points)

5.5k
views
gate2006
operatingsystem
processsynchronization
normal
+9
votes
1
answer
27
GATE200660
Consider the following C code segment. for (i = 0, i < n; i++) { for (j = 0; j < n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } } Which one of the following is false? The code ... invariant computation There is scope of common subexpression elimination in this code There is scope of strength reduction in this code There is scope of dead code elimination in this code
asked
Sep 26, 2014
in
Compiler Design
by
Rucha Shelke
Active
(
3.7k
points)

1.5k
views
gate2006
compilerdesign
codeoptimization
outofsyllabusnow
+19
votes
3
answers
28
GATE200659
Consider the following translation scheme. $ S\rightarrow ER$ $ R\rightarrow ^{*}E\left \{ print('*'); \right \} R\mid \varepsilon $ $ E\rightarrow F+E\left \{ print('+'); \right \}\mid F $ $ F\rightarrow (S)\mid id \left \{ print(id.value); \right \} $ Here id is a token that ... an input '$2 * 3 + 4$', this translation scheme prints $2 * 3 + 4$ $2 * +3 \ 4$ $2 \ 3 * 4 +$ $2 \ 3 \ 4+*$
asked
Sep 26, 2014
in
Compiler Design
by
Rucha Shelke
Active
(
3.7k
points)

1.9k
views
gate2006
compilerdesign
grammar
normal
+9
votes
3
answers
29
GATE200658
Consider the following grammar: $S\rightarrow FR$ $ R\rightarrow * S\mid \varepsilon $ $ F\rightarrow id $ In the predictive parser table, M, of the grammar the entries M[S,id] and M[R,\$] respectively are $ \left \{ S\rightarrow FR \right \} $ and $ \left \{ R\ ... \rightarrow {*}S\right \} $ $ \left \{ F\rightarrow id \right \} $ and $ \left \{ R\rightarrow \varepsilon \right \} $
asked
Sep 26, 2014
in
Compiler Design
by
Rucha Shelke
Active
(
3.7k
points)

1.3k
views
gate2006
compilerdesign
parsing
normal
+33
votes
2
answers
30
GATE200657
Consider this C code to swap two integers and these five statements: the code void swap (int *px, int *py) { *px = *px  *py; *py = *px + *py; *px = *py  *px; } S1: will generate a compilation error S2: may generate a segmentation fault ... swap procedure correctly for some but not all valid input pointers S5: may add or subtract integers and pointers S1 S2 and S3 S2 and S4 S2 and S5
asked
Sep 26, 2014
in
Programming
by
Rucha Shelke
Active
(
3.7k
points)

3.6k
views
gate2006
programming
programminginc
normal
Page:
1
2
3
next »
Quick search syntax
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
Recent Posts
SCREENSHOT
Basic LaTeX guide
IIT Madras Phd
Databases GO Classroom
Happy Birthday Sir Arjun
Follow @csegate
Gatecse
Recent questions tagged gate2006
Recent Blog Comments
Sir for final year student who have exam in...
I guess you meant while chasing :) Anyway those...
I'll write a post on how to best...
@Gaurav Go through all the previous yr questions,...
42,609
questions
48,606
answers
155,767
comments
63,774
users