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 gate2000
+25
votes
3
answers
1
Gate20002.19
Let $G$ be an undirected graph. Consider a depthfirst traversal of $G$, and let $T$ be the resulting depthfirst search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following statement is ... a leaf in $T$ If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$
asked
Nov 16, 2014
in
Algorithms
by
Daggerhunt
(
105
points)

3k
views
gate2000
algorithms
graphalgorithms
normal
0
votes
0
answers
2
GATE200022
Consider a bank database with only one relation transaction (transno, acctno, date, amount) The amount attribute value is positive for deposits and negative for withdrawals. Define an SQL view TP containing the information (acctno,T1.date,T2.amount) for every pair ... transaction since it was created. To simplify your query, break it up into 2 steps by defining an intermediate view V.
asked
Sep 14, 2014
in
Databases
by
Kathleen
Veteran
(
59.5k
points)

522
views
gate2000
databases
sql
normal
descriptive
+2
votes
0
answers
3
GATE200021
(a) Suppose you are given an empty B+ tree where each node (leaf and internal) can store up to 5 key values. Suppose values 1, 2,.....10 are inserted, in order, into the tree. Show the tree pictorially after 6 insertions, and after all 10 insertions ... Then what approximately is the average number of keys in each leaf level node. in the normal case, and with the insertion as in (b).
asked
Sep 14, 2014
in
Databases
by
Kathleen
Veteran
(
59.5k
points)

584
views
gate2000
databases
btree
normal
descriptive
+16
votes
3
answers
4
GATE200020
a. Fill in the boxes below to get a solution for the readerwriter problem, using a single binary semaphore, mutex (initialized to $1$) and busy waiting. Write the box numbers ($1$, $2$ and $3$), and their contents in your answer book. L1: int R = 0, W = 0; Reader () ... ; ...../*do the write*/ wait( mutex); W=0; signal (mutex); } b. Can the above solution lead to starvation of writers?
asked
Sep 14, 2014
in
Operating System
by
Kathleen
Veteran
(
59.5k
points)

1.5k
views
gate2000
operatingsystem
processsynchronization
normal
descriptive
+11
votes
3
answers
5
GATE200019
Consider the syntax directed translation scheme (SDTS) given in the following. Assume attribute evaluation with bottomup parsing, i.e., attributes are evaluated immediately after a reduction. E$\rightarrow $ E$_{1}$ * T {E.val = E$_{1}$.val * T.val ... the SDTS given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$.
asked
Sep 14, 2014
in
Compiler Design
by
Kathleen
Veteran
(
59.5k
points)

1.1k
views
gate2000
compilerdesign
syntaxdirectedtranslation
normal
descriptive
+4
votes
1
answer
6
GATE200018
Consider the following program is pseudoPascal syntax program main; var x: integer; procedure Q (z: integer); begin z := z+x; writeln(z); end; procedure P (y: integer); var x: integer; begin x := y+2; Q(x); writeln(x); end begin ... is callbyvalue and the scope rule is static scoping? the parameter passing mechanism is callbyreference and the scope rule is dynamic scoping?
asked
Sep 14, 2014
in
Programming
by
Kathleen
Veteran
(
59.5k
points)

923
views
gate2000
programming
parameterpassing
normal
outofsyllabusnow
descriptive
+19
votes
3
answers
7
GATE200017
An array contains four occurrences of $0$, five occurrences of $1$, and three occurrences of $2$ in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent). What is the minimum number of swaps needed to sort ... case? Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.
asked
Sep 14, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.5k
points)

1.3k
views
gate2000
algorithms
sorting
normal
descriptive
+11
votes
2
answers
8
GATE200016
A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array $f [ 0......m]$ with all elements initialized to $0$ fib(n) { if (n > M) error (); if (n == 0) return 1; if (n == 1)return ... values. Write the box number and the corresponding contents in your answer book. What is the time complexity of the resulting program when computing $fib(n)$?
asked
Sep 14, 2014
in
Programming
by
Kathleen
Veteran
(
59.5k
points)

781
views
gate2000
algorithms
normal
descriptive
recursion
+11
votes
1
answer
9
GATE200015
Suppose you are given arrays $p [1......N]$ and $q [1......N]$ both uninitialized, that is, each location may contain an arbitrary value), and a variable count, initialized to $0$. Consider the following procedures $set$ and $is\_set$: set(i) { count = count + ... that if $set(i)$ has not been called for some $i$, then regardless of what $p[i]$ contains, $is\_set(i)$ will return false.
asked
Sep 14, 2014
in
DS
by
Kathleen
Veteran
(
59.5k
points)

830
views
gate2000
datastructure
arrays
easy
descriptive
–1
vote
0
answers
10
GATE200014
Consider the line $y=\frac{n}{m}x$, where $n$ and $m$ are positive integers. If mq  np < 0, then is the point (p,q) above the line, below the line, or on the line? Complete the following function, that returns true if the line segment with endpoints (p,q) and (r,s) intersects the line ... *r)⊏⊐ 0 then clash:= true; 7: if(m*q  n*p)⊏⊐ 0 and (m*s  n*r)⊏⊐ 0 then clash:= true; 8: end;
asked
Sep 14, 2014
in
Others
by
Kathleen
Veteran
(
59.5k
points)

179
views
gate2000
descriptive
+16
votes
1
answer
11
GATE200013
Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of the elements on the stack. To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a sequence of $3$ ... $5 \ 2 * 3 \ 4 +$ After evaluating $5 \ 2 * 3 \ 4 + 5 \ 2$ At the end of evaluation
asked
Sep 14, 2014
in
DS
by
Kathleen
Veteran
(
59.5k
points)

1k
views
gate2000
datastructure
stack
normal
descriptive
+32
votes
3
answers
12
GATE200012
An instruction pipeline has five stages where each stage take 2 nanoseconds and all instruction use all five stages. Branch instructions are not overlapped. i.e., the instruction after the branch is not fetched till the branch instruction is completed. ... and 50% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time.
asked
Sep 14, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.5k
points)

3.2k
views
gate2000
coandarchitecture
pipelining
normal
descriptive
+6
votes
0
answers
13
GATE200011
Consider the following 8085 program segment, where registers B and C contain BCD values: S1: MVI A, 99H MVI D, 00H SUB C ADD B DAA S2: JC S3 MOV E, A MVI A, 99H SUB E MOV E, A JZ S4 MVI D, FFH JMP S4 S3:INC A DAA MOV E, A S4: ......... For ... values in register D and E when control reaches S4. What, in general, is the value of D and E as a function of B and C when control reaches S4?
asked
Sep 14, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.5k
points)

423
views
gate2000
coandarchitecture
8085
outofsyllabusnow
descriptive
0
votes
0
answers
14
GATE200010
Consider the 8085 instruction IN 09H stored as follows: Memory Address Machine Code 3050 3051 DA 09 and the following incomplete timing diagram for the instruction: Write the contents of the boxes, A, B, C and D in hexadecimal in your answer sheet. Do not draw ... put the data on the bus? Answer by completing the following statement in your answer book: By combining signals.........
asked
Sep 14, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.5k
points)

279
views
gate2000
coandarchitecture
8085
outofsyllabusnow
descriptive
+9
votes
2
answers
15
GATE20009
Design a logic circuit to convert a single digit BCD number to the number modulo six as follows (Do not detect illegal input): Write the truth table for all bits. Label the input bits I1, I2, .... with I1 as the least significant bit. Label the output bits ... truth. Draw one circuit for each output bit using, altogether, two twoinput AND gates, one twoinput OR gate and two NOT gates.
asked
Sep 14, 2014
in
Digital Logic
by
Kathleen
Veteran
(
59.5k
points)

490
views
gate2000
digitallogic
minnogates
descriptive
+16
votes
3
answers
16
GATE20008
A push down automation (pda) is given in the following extended notation of finite state diagram: The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form $d$, $s/s'$ where $d$ is the input symbol read and $s, s'$ are the ... in the above notation that accept the language $\left\{0^{n}1^{m} \mid n \leq m \leq 2n\right\}$ by empty stack
asked
Sep 14, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.5k
points)

996
views
gate2000
theoryofcomputation
descriptive
pushdownautomata
+17
votes
2
answers
17
GATE20007
Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the sub string $00$ nor the sub string $11$. Consider the grammar S → aSAb S → ∊ A → bA A → ∊ where $S$, $A$ are nonterminal symbols with ... ib^i$ for some $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?
asked
Sep 14, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.5k
points)

608
views
gate2000
theoryofcomputation
descriptive
regularlanguages
contextfreelanguage
+22
votes
3
answers
18
GATE20006
Let $S$ be a set of $n$ elements $\left\{1, 2,....., n\right\}$ and $G$ a graph with 2$^{n}$ vertices, each vertex corresponding to a distinct subset of $S$. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly ... right)$ Every vertex in $G$ has the same degree. What is the degree of a vertex in $G$? How many connected components does $G$ have?
asked
Sep 14, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.5k
points)

1.1k
views
gate2000
settheory&algebra
normal
descriptive
sets
+12
votes
3
answers
19
GATE20005
A multiset is an unordered collection of elements where elements may repeat any number of times. The size of a multiset is the number of elements in it, counting repetitions. What is the number of multisets of size $4$ that can be constructed from n distinct elements so that at least one element occurs exactly twice? How many multisets can be constructed from n distinct elements?
asked
Sep 14, 2014
in
Combinatory
by
Kathleen
Veteran
(
59.5k
points)

768
views
gate2000
permutationsandcombinations
normal
descriptive
+14
votes
1
answer
20
GATE20004
Let $S= \{0, 1, 2, 3, 4, 5, 6, 7\}$ and $⊗$ denote multiplication modulo $8,$ that is, $x ⊗ y= (xy) \mod 8$ Prove that $( \{ 0, 1\}, ⊗)$ is not a group. Write three distinct groups $(G, ⊗)$ where $G ⊂ S$ and $G$ has $2$ elements.
asked
Sep 14, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.5k
points)

561
views
gate2000
settheory&algebra
descriptive
groups
+5
votes
1
answer
21
GATE20003
Consider the following sequence: $s_1 = s_2 = 1$ and $s_i = 1 + \min \left({s_{i1}, s_{i2}}\right) \text{ for } i > 2$. Prove by induction on $n$ that $s_n=⌈\frac{n}{2}⌉$.
asked
Sep 14, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.5k
points)

425
views
gate2000
settheory&algebra
mathematicalinduction
descriptive
+31
votes
3
answers
22
GATE20002.26
In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent? $x = 5 \quad not (not (x = 5))$ $x = 5 \quad x > 4$ and $x < 6,$ where $x$ is an integer $x ≠ 5 \quad not (x = 5)$ none of the above
asked
Sep 14, 2014
in
Databases
by
Kathleen
Veteran
(
59.5k
points)

3.2k
views
gate2000
databases
sql
normal
+29
votes
2
answers
23
GATE20002.25
Given relations r(w, x) and s(y, z) the result of select distinct w, x from r, s is guaranteed to be same as r, provided. r has no duplicates and s is nonempty r and s have no duplicates s has no duplicates and r is nonempty r and s have the same number of tuples
asked
Sep 14, 2014
in
Databases
by
Kathleen
Veteran
(
59.5k
points)

3.3k
views
gate2000
databases
sql
+16
votes
3
answers
24
GATE20002.24
Given the following relation instance. X Y Z 1 4 2 1 5 3 1 6 3 3 2 2 Which of the following functional dependencies are satisfied by the instance? XY → Z and Z → Y YZ → X and Y → Z YZ → X and X → Z XZ → Y and Y → X
asked
Sep 14, 2014
in
Databases
by
Kathleen
Veteran
(
59.5k
points)

1.9k
views
gate2000
databases
functionaldependencies
easy
+17
votes
1
answer
25
GATE20002.23
Which of the following is not a valid deadlock prevention scheme? Release all resources before requesting a new resource. Number the resources uniquely and never request a lower numbered resource than the last one requested. Never request a resource after releasing any resource. Request and all required resources be allocated before execution.
asked
Sep 14, 2014
in
Operating System
by
Kathleen
Veteran
(
59.5k
points)

1.8k
views
gate2000
operatingsystem
resourceallocation
normal
+16
votes
2
answers
26
GATE20002.22
Suppose the time to service a page fault is on the average $10$ milliseconds, while a memory access takes $1$ microsecond. Then a $99.99\%$ hit ratio results in average memory access time of $1.9999$ milliseconds $1$ millisecond $9.999$ microseconds $1.9999$ microseconds
asked
Sep 14, 2014
in
Operating System
by
Kathleen
Veteran
(
59.5k
points)

3.2k
views
gate2000
operatingsystem
easy
virtualmemory
+17
votes
2
answers
27
GATE20002.21, ISRO201524
Given the following expression grammar: $$\begin{align} E &\to E * F \mid F + E \mid F \\[1em] F &\to F  F \mid id \end{align}$$ Which of the following is true? $*$ has higher precedence than $+$ $$ has higher precedence than $*$ $+$ and $$ have same precedence $+$ has higher precedence than $*$
asked
Sep 14, 2014
in
Compiler Design
by
Kathleen
Veteran
(
59.5k
points)

3.2k
views
gate2000
grammar
normal
compilerdesign
isro2015
+14
votes
2
answers
28
GATE20002.20
The value of $j$ at the end of the execution of the following C program: int incr (int i) { static int count = 0; count = count + i; return (count); } main () { int i, j; for (i = 0; i <= 4; i++) j = incr (i); } is: $10$ $4$ $6$ $7$
asked
Sep 14, 2014
in
Programming
by
Kathleen
Veteran
(
59.5k
points)

1.2k
views
gate2000
programming
programminginc
easy
+18
votes
3
answers
29
GATE20002.18
Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{max}$ be the edge with maximum weight and $e_{min}$ the edge with minimum weight. Which of the following statements is false? Every minimum spanning tree of $G$ must ... spanning tree, then its removal must disconnect $G$ No minimum spanning tree contains $e_{max}$ $G$ has a unique minimum spanning tree
asked
Sep 14, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.5k
points)

2.8k
views
gate2000
algorithms
spanningtree
normal
+28
votes
4
answers
30
GATE20002.17
Consider the following functions $f(n) = 3n^{\sqrt{n}}$ $g(n) = 2^{\sqrt{n}{\log_{2}n}}$ $h(n) = n!$ Which of the following is true? $h(n)$ is $O(f(n))$ $h(n)$ is $O(g(n))$ $g(n)$ is not $O(f(n))$ $f(n)$ is $O(g(n))$
asked
Sep 14, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.5k
points)

4.1k
views
gate2000
algorithms
asymptoticnotations
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
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
UGC NET JULY 2018 Results
Follow @csegate
Gatecse
Recent questions tagged gate2000
Recent Blog Comments
gate overflow books are awesome; every one should ...
Books are there but don't think any will leave ...
Sir i have placed the order Details are PAYMENT ...
Sir i am placing order for gate overflew book ...
Yes, their tracking system is incomplete. ...
38,094
questions
45,588
answers
132,149
comments
49,126
users