Dark Mode

Recent questions tagged gatecse-2000

63 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

18.4k views

6 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

2.5k views

12 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

3.9k views

31 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. int R = 0, W = ... ...../*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

9.7k views

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

7.9k views

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 in C Sep 14, 2014

3.0k views

42 votes

6 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

10.9k views

26 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 in C Sep 14, 2014

4.7k views

21 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

4.8k views

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

691 views

27 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

6.2k views

71 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

17.3k views

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

1.3k views

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

836 views

19 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

2.9k views

27 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

5.1k views

27 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

4.6k views

47 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

6.3k views

33 votes

6 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

7.8k views

28 votes

3 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

4.1k views

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

1.5k views

63 votes

4 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

18.6k views

57 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

16.2k views

30 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

14.5k views

30 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

22.1k views

35 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

18.1k views

27 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

10.7k views

29 votes

2 answers

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 in C Sep 14, 2014

14.9k views

38 votes

5 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

15.5k views

79 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

22.7k views

Page:

1
2
3
next »

Recent questions tagged gatecse-2000