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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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 gate2005
+8
votes
1
answer
1
GATE200558
Consider the following two problems on undirected graphs: $\alpha$: Given $G(V, E)$, does $G$ have an independent set of size V  $4$? $\beta$: Given $G(V, E)$, does $G$ have an independent set of size $5$? Which one of the following is TRUE? $\alpha$ is ... $\alpha$ is NPcomplete and $\beta$ is in P Both $\alpha$ and $\beta$ are NPcomplete Both $\alpha$ and $\beta$ are in P
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

1.2k
views
gate2005
theoryofcomputation
pnpnpcnph
normal
+21
votes
3
answers
2
GATE200557
Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ is a special symbol $L_3 = \left\{ww \mid w \in \{0, 1\}^* \right\}$ Which one of the following is TRUE? $L_1$ is a deterministic CFL $L_2$ is a deterministic CFL $L_3$ is a CFL, but not a deterministic CFL $L_3$ is a deterministic CFL
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

1.3k
views
gate2005
theoryofcomputation
contextfreelanguage
easy
+18
votes
2
answers
3
GATE200556
Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE? $L_1$' is recursive and $L_2$' is recursively enumerable $L_1$' is recursive and $L_2$' is not recursively enumerable $L_1$' and $L_2$' are recursively enumerable $L_1$' is recursively enumerable and $L_2$' is recursive
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

1.4k
views
gate2005
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
easy
+17
votes
5
answers
4
GATE200555
Consider the languages: $L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$ and $ L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$ Which one of the following statements is FALSE? $L_1 \cap L_2$ is a contextfree language $L_1 \cup L_2$ is a contextfree language $L_1 \text{ and } L_2$ are contextfree languages $L_1 \cap L_2$ is a context sensitive language
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

2.5k
views
gate2005
theoryofcomputation
identifyclasslanguage
normal
+17
votes
2
answers
5
GATE200554
Let $N_f$ and $N_p$ denote the classes of languages accepted by nondeterministic finite automata and nondeterministic pushdown automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic pushdown automata respectively. ... $D_f = N_f \text{ and } D_p = N_p$ $D_f =N_f \text{ and } D_p \subset N_p$
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

790
views
gate2005
theoryofcomputation
easy
nondeterminism
+27
votes
4
answers
6
GATE200553
Consider the machine $M$: The language recognized by $M$ is: $\left\{ w \in \{a, b\}^* \text{  every a in $w$ is followed by exactly two $b$'s} \right\}$ $\left\{w \in \{a, b\}^* \text{  every a in $w$ is followed by at least two $b$'s} \right\}$ ... $ contains the substring $abb$'} \right\}$ $\left\{w \in \{a, b\}^* \text{  $w$ does not contain $aa$' as a substring} \right\}$
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

2.3k
views
gate2005
theoryofcomputation
finiteautomata
normal
+33
votes
3
answers
7
GATE200545
Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE? $P_3$ is decidable if $P_1$ is reducible to $P_3$ $P_3$ is undecidable if $P_3$ is reducible to $P_2$ $P_3$ is undecidable if $P_2$ is reducible to $P_3$ $P_3$ is decidable if $P_3$ is reducible to $P_2$'s complement
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.1k
points)

2.9k
views
gate2005
theoryofcomputation
decidability
normal
+32
votes
1
answer
8
GATE200538
Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: $O\left(V^2\right)$ $O\left(E+V\log V\right)$ $O\left(V\logV\right)$ $O\left(\left(E+V\right)\logV\right)$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.1k
points)

4k
views
gate2005
algorithms
graphalgorithms
normal
+22
votes
3
answers
9
GATE200537
Suppose $T(n) =2T (\frac{n}{2}) + n$, $T(0) = T(1) =1$ Which one of the following is FALSE? $T(n)=O(n^2)$ $T(n)=\Theta(n \log n)$ $T(n)=\Omega(n^2)$ $T(n)=O(n \log n)$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.1k
points)

2.2k
views
gate2005
algorithms
asymptoticnotations
recurrence
normal
+15
votes
6
answers
10
GATE200536
In a complete $k$ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is: $nk$ $(n1)k + 1$ $n(k1) +1$ $n(k1)$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

3.3k
views
gate2005
datastructure
trees
normal
+16
votes
3
answers
11
GATE200535
How many distinct binary search trees can be created out of $4$ distinct keys? $5$ $14$ $24$ $42$
asked
Sep 22, 2014
in
Graph Theory
by
Kathleen
Veteran
(
52.1k
points)

2k
views
gate2005
graphtheory
counting
normal
+13
votes
2
answers
12
GATE200534
A priority queue is implemented as a MaxHeap. Initially, it has $5$ elements. The levelorder traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The levelorder traversal of the heap after the insertion of the elements is: $10, 8, 7, 5, 3, 2, 1$ $10, 8, 7, 2, 3, 1, 5$ $10, 8, 7, 1, 2, 3, 5$ $10, 8, 7, 3, 2, 1, 5$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

1.4k
views
gate2005
datastructure
heap
normal
+17
votes
2
answers
13
GATE200533
Postorder traversal of a given binary search tree, $T$ produces the following sequence of keys $10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29$ Which one of the following sequences of keys can be the result of an inorder traversal of the tree $T$ ... $29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95$ $95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

1.6k
views
gate2005
datastructure
binarytree
easy
+18
votes
5
answers
14
GATE200532
Consider the following C program: double foo (double); /* Line 1 */ int main() { double da, db; //input da db = foo(da); } double foo (double a) { return a; } The above code compiled without any error or ... warning or error some compilerwarnings not leading to unintended results some compilerwarnings due to typemismatch eventually leading to unintended results compiler errors
asked
Sep 22, 2014
in
Programming
by
Kathleen
Veteran
(
52.1k
points)

3.8k
views
gate2005
programming
programminginc
compilerdesign
easy
+16
votes
4
answers
15
GATE200531
Consider the following Cprogram: void foo (int n, int sum) { int k = 0, j = 0; if (n == 0) return; k = n % 10; j = n/10; sum = sum + k; foo (j, sum); printf ("%d,",k); } int main() { int a = 2048, sum = 0; foo(a, sum); printf("%d\n", sum); } What does the ... program print? $\text{8, 4, 0, 2, 14}$ $\text{8, 4, 0, 2, 0}$ $\text{2, 0, 4, 8, 14}$ $\text{2, 0, 4, 8, 0}$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.1k
points)

2.8k
views
gate2005
algorithms
identifyfunction
recursion
normal
+24
votes
4
answers
16
GATE200530
Let r be a relation instance with schema R = (A, B, C, D). We define $r_1 = \pi_{A, B, C} (R)$ and $r_2=\pi_{A, D} (r)$. Let $s =r_1 \: * \: r_2$ where $*$ denotes natural join. Given that the decomposition of $r$ into $r_1$ and $r_2$ is lossy, which one of the following is TRUE? $s \subset r$ $r \cup s =r$ $r \subset s$ $r*s=s$
asked
Sep 22, 2014
in
Databases
by
Kathleen
Veteran
(
52.1k
points)

3.1k
views
gate2005
databases
relationalalgebra
naturaljoin
normal
+20
votes
4
answers
17
GATE200529, UGCNETJune2015III9
Which one of the following statements about normal forms is $\text{FALSE}?$ $\text{BCNF}$ is stricter than $3NF$ Lossless, dependencypreserving decomposition into $3NF$ is always possible Lossless, dependencypreserving decomposition into $\text{BCNF}$ is always possible Any relation with two attributes is in $\text{BCNF}$
asked
Sep 22, 2014
in
Databases
by
Kathleen
Veteran
(
52.1k
points)

2.7k
views
gate2005
databases
databasenormalization
easy
ugcnetjune2015iii
+31
votes
5
answers
18
GATE200528
Which of the following is a key factor for preferring $B^+$trees to binary search trees for indexing database relations? Database relations have a large number of records Database relations are sorted on the primary key $B^+$trees require less memory than binary search trees Data transfer form disks is in blocks
asked
Sep 22, 2014
in
Databases
by
Kathleen
Veteran
(
52.1k
points)

3.8k
views
gate2005
databases
btree
normal
+10
votes
3
answers
19
GATE200527
An organization has a class $B$ network and wishes to form subnets for $64$ departments. The subnet mask would be: $255.255.0.0$ $255.255.64.0$ $255.255.128.0$ $255.255.252.0$
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
52.1k
points)

4.2k
views
gate2005
computernetworks
subnetting
normal
+14
votes
4
answers
20
GATE200526
In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed through multiple bridges. Why is the spanning ... bridgerouting? For shortest path routing between LANs For avoiding loops in the routing paths For fault tolerance For minimizing collisions
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
52.1k
points)

1.6k
views
gate2005
computernetworks
routing
normal
+18
votes
4
answers
21
GATE200525
The maximum window size for data transmission using the selective reject protocol with $n\text{bit}$ frame sequence numbers is: $2^n$ $2^{n1}$ $2^n1$ $2^{n2}$
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
52.1k
points)

3.4k
views
gate2005
computernetworks
slidingwindow
easy
+15
votes
3
answers
22
GATE200524
The address resolution protocol (ARP) is used for: Finding the IP address from the DNS Finding the IP address of the default gateway Finding the IP address that corresponds to a MAC address Finding the MAC address that corresponds to an IP address
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
52.1k
points)

2.2k
views
gate2005
computernetworks
normal
networkaddressing
+18
votes
5
answers
23
GATE200523
Packets of the same session may be routed through different paths in: TCP, but not UDP TCP and UDP UDP, but not TCP Neither TCP nor UDP
asked
Sep 22, 2014
in
Computer Networks
by
Kathleen
Veteran
(
52.1k
points)

5.1k
views
gate2005
computernetworks
tcp
udp
easy
+20
votes
2
answers
24
GATE200522, ISRO201536
Increasing the RAM of a computer typically improves performance because: Virtual Memory increases Larger RAMs are faster Fewer page faults occur Fewer segmentation faults occur
asked
Sep 22, 2014
in
Operating System
by
Kathleen
Veteran
(
52.1k
points)

9.4k
views
gate2005
operatingsystem
pagereplacement
easy
isro2015
+12
votes
5
answers
25
GATE200521
What is the swap space in the disk used for? Saving temporary html pages Saving process data Storing the superblock Storing device drivers
asked
Sep 22, 2014
in
Operating System
by
Kathleen
Veteran
(
52.1k
points)

2.1k
views
gate2005
operatingsystem
disks
easy
+20
votes
2
answers
26
GATE200520
Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instruction privileged. In a CPU with memory mapped I/O, there is ... s) I/O protection is ensured by a hardware trap I/O protection is ensured during system configuration I/O protection is not possible
asked
Sep 22, 2014
in
Operating System
by
Kathleen
Veteran
(
52.1k
points)

3.4k
views
gate2005
operatingsystem
iohandling
normal
+28
votes
6
answers
27
GATE200519
Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line? Neither vectored interrupt nor multiple interrupting devices are possible Vectored interrupts are not possible but ... interrupts and multiple interrupting devices are both possible Vectored interrupts are possible but multiple interrupting devices are not possible
asked
Sep 22, 2014
in
Operating System
by
Kathleen
Veteran
(
52.1k
points)

5k
views
gate2005
operatingsystem
iohandling
normal
+13
votes
2
answers
28
GATE200518
The switching expression corresponding to $f(A,B,C,D)=\Sigma(1, 4, 5, 9, 11, 12)$ is: $BC’D’ + A’C’D + AB’D$ $ABC’ + ACD + B’C’D$ $ACD’ + A’BC’ + AC’D’$ $A’BD + ACD’ + BCD’$
asked
Sep 22, 2014
in
Digital Logic
by
Kathleen
Veteran
(
52.1k
points)

1.4k
views
gate2005
digitallogic
normal
minsumofproductsform
+14
votes
2
answers
29
GATE200517
The hexadecimal representation of (657)8 is: $\text{1AF}$ $\text{D78}$ $\text{D71}$ $\text{32F}$
asked
Sep 22, 2014
in
Digital Logic
by
Kathleen
Veteran
(
52.1k
points)

1.2k
views
gate2005
digitallogic
numberrepresentation
easy
+16
votes
4
answers
30
GATE200516, ISRO200918, ISRO20152
The range of integers that can be represented by an $n$ bit $2’s$ complement number system is: $2^{n1} \text{ to } (2^{n1} 1)$ $(2^{n1} 1) \text{ to } (2^{n1} 1)$ $2^{n1} \text{ to } 2^{n1}$ $(2^{n1} +1) \text{ to } (2^{n1} 1)$
asked
Sep 22, 2014
in
Digital Logic
by
Kathleen
Veteran
(
52.1k
points)

3.9k
views
gate2005
digitallogic
numberrepresentation
easy
isro2009
isro2015
Page:
« prev
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
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
Standard Videos for Graph Theory
Standard Videos for Combinatory
Follow @csegate
Recent questions tagged gate2005
Recent Blog Comments
it's depend upon your shift.
Can previously appeared candidates tell what is...
i have confirmed through application form that...
Thanks I will try that
Yes, since one can't enter the CGPA/Marks until...
50,309
questions
55,743
answers
192,225
comments
90,494
users