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 gate2009
GATE 2009 Computer Science & Information Technology Question Paper with Solution
+1
vote
1
answer
1
Gate 2009
$S > aSa\mid bSb \mid a \mid b$; The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of All palindromes All odd length palindromes. Strings that begin and end with the same symbol All even length palindromes I think answer is B & C both but anwer is only B given not C. Why? plz explain .......
asked
Mar 22
in
Theory of Computation
by
Raj Kumar 7
Junior
(
893
points)

51
views
gate
gate2009
theoryofcomputation
contextfreelanguage
+1
vote
0
answers
2
Doubt in pipelining questions.
Consider this question and its selected answer: https://gateoverflow.in/3690/gate2004it47 And this question: https://gateoverflow.in/1314/gate200928 Both questions are somewhat similar. In the first one's answer, instruction $I_1$ (when i = 2), the ... that I am missing? PS. From where can I study this? Hamacher book doesn't contain pipelining in this much detail.
asked
Nov 4, 2017
in
CO & Architecture
by
Rishabh Gupta 2
Boss
(
13.9k
points)

244
views
coandarchitecture
pipelining
gate2004it
gate2009
+20
votes
3
answers
3
GATE200952
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the ... \langle 0, 15, 31 \rangle$ $\langle 0, 16, 30 \rangle$ $\langle 0, 16, 31 \rangle$ $\langle 0, 17, 31 \rangle$
asked
Apr 23, 2016
in
Operating System
by
jothee
Veteran
(
98.5k
points)

1.6k
views
gate2009
operatingsystem
disks
normal
+24
votes
2
answers
4
GATE200954
A subsequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the ... order of $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.
asked
Apr 23, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

2.1k
views
gate2009
normal
algorithms
dynamicprogramming
recursion
+24
votes
3
answers
5
GATE200956
Consider the following relational schema: $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ $\text{Catalog}(\underline {\text{sid:integer, ... schema is in $3NF$ but not in $\text{BCNF}$ The schema is in $2NF$ but not in $3NF$ The schema is not in $2NF$
asked
Apr 23, 2016
in
Databases
by
jothee
Veteran
(
98.5k
points)

3.2k
views
gate2009
databases
sql
databasenormalization
normal
+29
votes
5
answers
6
GATE200958
Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Let $I$ be the ... to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time) $16ms$ $18ms$ $20ms$ $22ms$
asked
Apr 23, 2016
in
Computer Networks
by
jothee
Veteran
(
98.5k
points)

5k
views
gate2009
computernetworks
slidingwindow
normal
+13
votes
2
answers
7
GATE200960
Consider a binary maxheap implemented using an array. What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$ $\left\{14,13,12,10, 8\right\}$ $\left\{14,12,13,8,10\right\}$ $\left\{14,13,8,12,10\right\}$ $\left\{14,13,12,8,10\right\}$
asked
Apr 23, 2016
in
DS
by
jothee
Veteran
(
98.5k
points)

818
views
gate2009
datastructure
heap
normal
+14
votes
2
answers
8
GATE200959
Consider a binary maxheap implemented using an array. Which one of the following array represents a binary maxheap? $\left\{25,12,16,13,10,8,14\right\}$ $\left\{25,14,13,16,10,8,12\right\}$ $\left\{25,14,16,13,10,8,12\right\}$ $\left\{25,14,12,13,10,8,16\right\}$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
59.4k
points)

1.2k
views
gate2009
datastructure
heap
normal
+39
votes
8
answers
9
GATE200957, ISRO201675
Frames of $1000$ $\text{bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $25$ $\text{ms}$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). ... numbers distinctly? Assume that no time gap needs to be given between transmission of two frames. $I$=$2$ $I$=$3$ $I$=$4$ $I$=$5$
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
59.4k
points)

9.5k
views
gate2009
computernetworks
slidingwindow
normal
isro2016
+26
votes
3
answers
10
GATE200955
Consider the following relational schema: $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ $\text{Catalog}(\underline { ... names of all suppliers who have supplied only nonblue part. Find the names of all suppliers who have not supplied only blue parts.
asked
Sep 22, 2014
in
Databases
by
Kathleen
Veteran
(
59.4k
points)

4.1k
views
gate2009
databases
sql
subqueries
normal
+16
votes
3
answers
11
GATE200953
A subsequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest ... (i,j1\right)\right)$ $\text{expr2} = \max\left(l\left(i1, j1\right), l\left(i,j\right)\right)$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

1.6k
views
gate2009
algorithms
normal
dynamicprogramming
recursion
+24
votes
2
answers
12
GATE200951
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector ... 0, 0, 1 \rangle$, and so on The address $\langle 400, 16, 29 \rangle$ corresponds to sector number: 505035 505036 505037 505038
asked
Sep 22, 2014
in
Operating System
by
Kathleen
Veteran
(
59.4k
points)

3.7k
views
gate2009
operatingsystem
disks
normal
+4
votes
1
answer
13
GATE200950
Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE? The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph. The cyclomatic complexity of ... paths that should be tested during path coverage testing. I and II II and III I and III I, II and III
asked
Sep 22, 2014
in
IS&Software Engineering
by
Kathleen
Veteran
(
59.4k
points)

862
views
gate2009
is&softwareengineering
cyclomaticcomplexity
easy
+8
votes
2
answers
14
GATE200949
Which of the following statements are TRUE? The context diagram should depict the system as a single bubble. External entities should be identified clearly at all levels of DFDs. Control information should not be represented in a DFD. A data store can be connected wither to another data store or to an external entity. II and III II and III I and III I, II and III
asked
Sep 22, 2014
in
IS&Software Engineering
by
Kathleen
Veteran
(
59.4k
points)

1.1k
views
gate2009
is&softwareengineering
normal
dataflowdiagrams
+24
votes
4
answers
15
GATE200948
Let $G(x)$ be the generator polynomial used for CRC checking. What is the condition that should be satisfied by $G(x)$ to detect odd number of bits in error? $G(x)$ contains more than two terms $G(x)$ does not divide $1+x^k$, for any $k$ not exceeding the frame length $1+x$ is a factor of $G(x)$ $G(x)$ has an odd number of terms.
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
59.4k
points)

4.3k
views
gate2009
computernetworks
errordetection
normal
+37
votes
5
answers
16
GATE200947
While opening a $TCP$ connection, the initial sequence number is to be derived using a timeofday (ToD) clock that keeps running even when the host is down. The low order $32$ bits of the counter of the ToD clock is to be used for the initial sequence numbers ... rate at which sequence numbers used for packets of a connection can increase? $0.015$/s $0.064$/s $0.135$/s $0.327$/s
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
59.4k
points)

4.9k
views
gate2009
computernetworks
tcp
difficult
+15
votes
2
answers
17
GATE200946
In the RSA public key cryptosystem, the private and public keys are $(e, n)$ and $(d, n)$ respectively, where $n=p \times q$ and $p$ and $q$ are large primes. Besides, $n$ is public and $p$ and $q$ are private. Let $M$ be an integer such that $0<M< ... \text{ mod }\phi( n)$ Which of the above equations correctly represents RSA cryptosystem? I and II I and III II and IV III and IV
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
59.4k
points)

1.5k
views
gate2009
computernetworks
networksecurity
normal
+36
votes
1
answer
18
GATE200945
Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database: $\pi_{RS}(r)  \pi_{RS} \left (\pi_{RS} (r) \times s  \pi_{RS,S}(r)\right )$ $\left\{t \mid t \in \pi_{RS} (r) \wedge \forall u \ ... right ) \right\}$ Select R.a,R.b From R,S Where R.c = S.c Which of the above queries are equivalent? 1 and 2 1 and 3 2 and 4 3 and 4
asked
Sep 22, 2014
in
Databases
by
Kathleen
Veteran
(
59.4k
points)

4.5k
views
gate2009
databases
relationalcalculus
difficult
+27
votes
9
answers
19
GATE200944
The following key values are inserted into a $B+$  tree in which order of the internal nodes is $3$, and that of the leaf nodes is $2$, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order ... , $4$, $2$, $1$ The maximum number of times leaf nodes would get split up as a result of these insertions is $2$ $3$ $4$ $5$
asked
Sep 22, 2014
in
Databases
by
Kathleen
Veteran
(
59.4k
points)

5.5k
views
gate2009
databases
btree
normal
+13
votes
1
answer
20
GATE200943
Consider two transactions $T_1$ and $T_2$, and four schedules $S_1, S_2, S_3, S_4$, of $T_1$ and $T_2$ as given below: $T_1: R_1[x]W_1[x]W_1[y]$ $T_2: R_2[x]R_2[y]W_2[y]$ $S_1: R_1[x]R_2[x]R_2[y] W_1[x] W_1[y] W_2[y]$ $S_2: R_1[x]R_2[x]R_2[y] ... [x] W_1[y] W_2[y]$ Which of the above schedules are conflictserializable? $S_1 \text{ and } S_2$ $S_2 \text{ and } S_3$ $S_3$ only $S_4$ only
asked
Sep 22, 2014
in
Databases
by
Kathleen
Veteran
(
59.4k
points)

1.2k
views
gate2009
databases
transactions
normal
+21
votes
1
answer
21
GATE200942
Which of the following statements are TRUE? There exist parsing algorithms for some programming languages whose complexities are less than $\Theta(n^3)$ A programming language which allows recursion can be implemented with static storage allocation. No Lattributed definition can be ... at both source language and intermediate code level. I and II I and IV III and IV I, III and IV
asked
Sep 22, 2014
in
Compiler Design
by
Kathleen
Veteran
(
59.4k
points)

3k
views
gate2009
compilerdesign
parsing
normal
+19
votes
6
answers
22
GATE200941
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.4k
points)

2k
views
gate2009
theoryofcomputation
finiteautomata
easy
+27
votes
5
answers
23
GATE200940
Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then $L$ is Not recursive Regular Context free but not regular Recursively enumerable but not context free.
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.4k
points)

2k
views
gate2009
theoryofcomputation
easy
identifyclasslanguage
+24
votes
2
answers
24
GATE200939
In quicksort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

2.7k
views
gate2009
algorithms
sorting
normal
+10
votes
1
answer
25
GATE200938
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskalâ€™s algorithm? (b, e) (e, f) (a, c) (b, c) (f, g) (c, d) (b, e) (e, f) (a, c) (f, g) (b, c) (c, d) (b, e) (a, c) (e, f) (b, c) (f, g) (c, d) (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

1.1k
views
gate2009
algorithms
spanningtree
normal
+17
votes
2
answers
26
GATE200937,ISRODEC201755
What is the maximum height of any AVLtree with $7$ nodes? Assume that the height of a tree with a single node is $0$. $2$ $3$ $4$ $5$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
59.4k
points)

5.9k
views
gate2009
datastructure
binarysearchtree
normal
isrodec2017
+16
votes
2
answers
27
GATE200936
The keys $12, 18, 13, 2, 3, 23, 5$ and $15$ are inserted into an initially empty hash table of length $10$ using open addressing with hash function $h(k) = k \mod 10$ and linear probing. What is the resultant hash table? A B C D $0$ $1$ $2$ $2$ $3$ $23$ $4$ $5$ $15$ ... $5$ $3$ $6$ $23$ $7$ $5$ $8$ $18$ $9$ $15$ $0$ $1$ $2$ $2, 12$ $3$ $13, 3, 23$ $4$ $5$ $5, 15$ $6$ $7$ $8$ $18$ $9$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
59.4k
points)

1k
views
gate2009
datastructure
hashing
normal
+14
votes
2
answers
28
GATE200935
The running time of an algorithm is represented by the following recurrence relation: $T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$ Which one of the following represents the time complexity of the algorithm? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

1.4k
views
gate2009
algorithms
recurrence
timecomplexity
normal
+19
votes
2
answers
29
GATE200934
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because It reduces the memory access time to read or write a memory location. It helps to reduce the size of page table ... It is required by the translation lookaside buffer. It helps to reduce the number of page faults in page replacement algorithms.
asked
Sep 22, 2014
in
Operating System
by
Kathleen
Veteran
(
59.4k
points)

1.7k
views
gate2009
operatingsystem
virtualmemory
easy
+24
votes
9
answers
30
GATE200933
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using testandset instruction as follows: void enter_CS(X) { while(testandset(X)); } void leave_CS(X) { X = 0; } In the above solution, X is a memory location ... than one process can enter CS at the same time Which of the above statements are TRUE? I only I and II II and III IV only
asked
Sep 22, 2014
in
Operating System
by
Kathleen
Veteran
(
59.4k
points)

4k
views
gate2009
operatingsystem
processsynchronization
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
BARC Interview Experience 15th June 2018
COAP Admission and IITD, IITK Interview Experience 2018
MS Interview Experience at IITK
Effect of Academic/ Career Gap during Mtech Placements at IIT/NIT
Gate Rank Improvement
Follow @csegate
Gatecse
Recent questions tagged gate2009
Recent Blog Comments
thanks for the info .but qstn 1.4 time complexity ...
What was your GATE rank and score this time ...
finish all subjects first then start taking all ...
@Arjun sir Address Confirmation mail not ...
Those who pay till today  June 17 can expect the ...
36,075
questions
43,521
answers
123,662
comments
42,747
users