Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged gatecse-2000
55
votes
4
answers
1
GATE CSE 2000 | Question: 2.19
Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first 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 ... in $T$ If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$
Daggerhunt
asked
in
Algorithms
Nov 16, 2014
by
Daggerhunt
15.3k
views
gatecse-2000
algorithms
graph-algorithms
normal
5
votes
1
answer
2
GATE CSE 2000 | Question: 22
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 ... since it was created. To simplify your query, break it up into 2 steps by defining an intermediate view V.
Kathleen
asked
in
Databases
Sep 14, 2014
by
Kathleen
1.9k
views
gatecse-2000
databases
sql
normal
descriptive
9
votes
2
answers
3
GATE CSE 2000 | Question: 21
(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,\ldots 10$ are inserted, in order, into the tree. Show the tree pictorially after $6$ insertions, and ... what approximately is the average number of keys in each leaf level node. in the normal case, and with the insertion as in (b).
Kathleen
asked
in
Databases
Sep 14, 2014
by
Kathleen
2.8k
views
gatecse-2000
databases
b-tree
normal
descriptive
29
votes
4
answers
4
GATE CSE 2000 | Question: 20
a. Fill in the boxes below to get a solution for the reader-writer 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, ... ...../*do the write*/ wait( mutex); W=0; signal (mutex); } b. Can the above solution lead to starvation of writers?
Kathleen
asked
in
Operating System
Sep 14, 2014
by
Kathleen
8.1k
views
gatecse-2000
operating-system
process-synchronization
normal
descriptive
15
votes
3
answers
5
GATE CSE 2000 | Question: 19
Consider the syntax directed translation scheme $\textsf{(SDTS)}$ ... given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$.
Kathleen
asked
in
Compiler Design
Sep 14, 2014
by
Kathleen
5.7k
views
gatecse-2000
compiler-design
syntax-directed-translation
normal
descriptive
6
votes
2
answers
6
GATE CSE 2000 | Question: 18
Consider the following program is pseudo-Pascal 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); ... is call-by-value and the scope rule is static scoping? the parameter passing mechanism is call-by-reference and the scope rule is dynamic scoping?
Kathleen
asked
in
Programming
Sep 14, 2014
by
Kathleen
2.3k
views
gatecse-2000
programming
parameter-passing
normal
out-of-syllabus-now
descriptive
37
votes
5
answers
7
GATE CSE 2000 | Question: 17
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 ... ? Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.
Kathleen
asked
in
Algorithms
Sep 14, 2014
by
Kathleen
8.1k
views
gatecse-2000
algorithms
sorting
normal
descriptive
24
votes
3
answers
8
GATE CSE 2000 | Question: 16
A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array $f [ 0\ldots m]$ with all elements initialized to $0.$ fib(n) { if (n > M) error (); if (n == 0) return 1; if (n = ... 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)?$
Kathleen
asked
in
Programming
Sep 14, 2014
by
Kathleen
3.4k
views
gatecse-2000
algorithms
normal
descriptive
recursion
20
votes
3
answers
9
GATE CSE 2000 | Question: 15
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 ... $set(i)$ has not been called for some $i$, then regardless of what $p[i]$ contains, $is\_set(i)$ will return false.
Kathleen
asked
in
DS
Sep 14, 2014
by
Kathleen
3.6k
views
gatecse-2000
data-structures
array
easy
descriptive
0
votes
0
answers
10
GATE CSE 2000 | Question: 14
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) ... *r)⊏⊐ 0 then clash:= true; 7: if(m*q - n*p)⊏⊐ 0 and (m*s - n*r)⊏⊐ 0 then clash:= true; 8: end;
Kathleen
asked
in
Others
Sep 14, 2014
by
Kathleen
541
views
gatecse-2000
descriptive
26
votes
2
answers
11
GATE CSE 2000 | Question: 13
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 ... $5 \ 2 * 3 \ 4 + 5 \ 2$ At the end of evaluation
Kathleen
asked
in
DS
Sep 14, 2014
by
Kathleen
5.2k
views
gatecse-2000
data-structures
stack
normal
descriptive
67
votes
8
answers
12
GATE CSE 2000 | Question: 12
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 ... 50% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time.
Kathleen
asked
in
CO and Architecture
Sep 14, 2014
by
Kathleen
12.1k
views
gatecse-2000
co-and-architecture
pipelining
normal
descriptive
6
votes
0
answers
13
GATE CSE 2000 | Question: 11
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: ..... ... 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?
Kathleen
asked
in
CO and Architecture
Sep 14, 2014
by
Kathleen
1.0k
views
gatecse-2000
co-and-architecture
8085-microprocessor
out-of-syllabus-now
descriptive
0
votes
0
answers
14
GATE CSE 2000 | Question: 10
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 ... the data on the bus? Answer by completing the following statement in your answer book: By combining signals.........
Kathleen
asked
in
CO and Architecture
Sep 14, 2014
by
Kathleen
627
views
gatecse-2000
co-and-architecture
8085-microprocessor
out-of-syllabus-now
descriptive
18
votes
3
answers
15
GATE CSE 2000 | Question: 9
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 $I_1, I_2, \ldots$ with $I_1$ as the least significant bit. ... Draw one circuit for each output bit using, altogether, two two-input AND gates, one two-input OR gate and two NOT gates.
Kathleen
asked
in
Digital Logic
Sep 14, 2014
by
Kathleen
2.2k
views
gatecse-2000
digital-logic
min-no-gates
descriptive
26
votes
4
answers
16
GATE CSE 2000 | Question: 8
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$ ... the above notation that accept the language $\left\{0^{n}1^{m} \mid n \leq m \leq 2n\right\}$ by empty stack
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
4.0k
views
gatecse-2000
theory-of-computation
descriptive
pushdown-automata
26
votes
2
answers
17
GATE CSE 2000 | Question: 7
Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the substring $00$ nor the substring $11$. Consider the grammar $S \to aSAb $ $S \to \epsilon $ $A \to bA $ $ A \to \epsilon $ where $S$ ... $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
3.5k
views
gatecse-2000
theory-of-computation
descriptive
regular-language
context-free-language
43
votes
6
answers
18
GATE CSE 2000 | Question: 6
Let $S$ be a set of $n$ elements $\left\{1, 2,\ldots, 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 ... Every vertex in $G$ has the same degree. What is the degree of a vertex in $G$? How many connected components does $G$ have?
Kathleen
asked
in
Set Theory & Algebra
Sep 14, 2014
by
Kathleen
4.8k
views
gatecse-2000
set-theory&algebra
normal
descriptive
set-theory
29
votes
5
answers
19
GATE CSE 2000 | Question: 5
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 ... n distinct elements so that at least one element occurs exactly twice? How many multisets can be constructed from n distinct elements?
Kathleen
asked
in
Combinatory
Sep 14, 2014
by
Kathleen
5.5k
views
gatecse-2000
combinatory
normal
descriptive
24
votes
2
answers
20
GATE CSE 2000 | Question: 4
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.
Kathleen
asked
in
Set Theory & Algebra
Sep 14, 2014
by
Kathleen
3.2k
views
gatecse-2000
set-theory&algebra
descriptive
group-theory
8
votes
1
answer
21
GATE CSE 2000 | Question: 3
Consider the following sequence: $s_1 = s_2 = 1$ and $s_i = 1 + \min \left({s_{i-1}, s_{i-2}}\right) \text{ for } i > 2$. Prove by induction on $n$ that $s_n=⌈\frac{n}{2}⌉$.
Kathleen
asked
in
Set Theory & Algebra
Sep 14, 2014
by
Kathleen
1.2k
views
gatecse-2000
set-theory&algebra
mathematical-induction
descriptive
60
votes
5
answers
22
GATE CSE 2000 | Question: 2.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
Kathleen
asked
in
Databases
Sep 14, 2014
by
Kathleen
14.5k
views
gatecse-2000
databases
sql
normal
53
votes
4
answers
23
GATE CSE 2000 | Question: 2.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 non-empty r and s have no duplicates s has no duplicates and r is non-empty r and s have the same number of tuples
Kathleen
asked
in
Databases
Sep 14, 2014
by
Kathleen
12.9k
views
gatecse-2000
databases
sql
26
votes
5
answers
24
GATE CSE 2000 | Question: 2.24
Given the following relation instance. ... $YZ \rightarrow X$ and $Y \rightarrow Z$ $YZ \rightarrow X$ and $X \rightarrow Z$ $XZ \rightarrow Y$ and $Y \rightarrow X$
Kathleen
asked
in
Databases
Sep 14, 2014
by
Kathleen
9.7k
views
gatecse-2000
databases
database-normalization
easy
28
votes
2
answers
25
GATE CSE 2000 | Question: 2.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.
Kathleen
asked
in
Operating System
Sep 14, 2014
by
Kathleen
18.9k
views
gatecse-2000
operating-system
resource-allocation
normal
33
votes
5
answers
26
GATE CSE 2000 | Question: 2.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
Kathleen
asked
in
Operating System
Sep 14, 2014
by
Kathleen
14.3k
views
gatecse-2000
operating-system
easy
virtual-memory
25
votes
6
answers
27
GATE CSE 2000 | Question: 2.21, ISRO2015-24
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 $*$
Kathleen
asked
in
Compiler Design
Sep 14, 2014
by
Kathleen
8.4k
views
gatecse-2000
operator-precedence
normal
compiler-design
isro2015
25
votes
1
answer
28
GATE CSE 2000 | Question: 2.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$
Kathleen
asked
in
Programming
Sep 14, 2014
by
Kathleen
10.5k
views
gatecse-2000
programming
programming-in-c
easy
30
votes
4
answers
29
GATE CSE 2000 | Question: 2.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 ... , then its removal must disconnect $G$ No minimum spanning tree contains $e_{max}$ $G$ has a unique minimum spanning tree
Kathleen
asked
in
Algorithms
Sep 14, 2014
by
Kathleen
12.4k
views
gatecse-2000
algorithms
spanning-tree
normal
67
votes
10
answers
30
GATE CSE 2000 | Question: 2.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))$
Kathleen
asked
in
Algorithms
Sep 14, 2014
by
Kathleen
18.1k
views
gatecse-2000
algorithms
asymptotic-notations
normal
Page:
1
2
3
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Life happens, just chill and do hardwork
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(648)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(853)
Recent questions tagged gatecse-2000
Recent Blog Comments
What will be upper age limit for upcoming ISRO...
please add GO Classes 2023 Computer Networks...
Please upload 4th Mock Test, due date was 4th Dec.
The counts of answered, marked etc in the exam...
Tests have been sent and all tests will be...