Recent questions tagged gateit-2005 / GATE Overflow for GATE CSE

37 votes

3 answers

31

GATE IT 2005 | Question: 62
Two shared resources $R_1$ and $R_2$ are used by processes $P_1$ and $P_2$. Each process has a certain priority for accessing each resource. Let $T_{ij}$ denote the priority of $P_i$ for accessing $R_j$. A process $P_i$ can snatch a resource $R_k$ from process $P_j$ ... that $P_1$ and $P_2$ can never deadlock? (I) and (IV) (II) and (III) (I) and (II) None of the above

Two shared resources $R_1$ and $R_2$ are used by processes $P_1$ and $P_2$. Each process has a certain priority for accessing each resource. Let $T_{ij}$ denote the prior...

Ishrat Jahan

8.9k views

Ishrat Jahan asked Nov 3, 2014

22 votes

5 answers

32

GATE IT 2005 | Question: 61
Consider a $2$-way set associative cache memory with $4$ sets and total $8$ cache blocks $(0-7)$ and a main memory with $128$ blocks $(0-127)$. What memory blocks will be present in the cache after the following sequence of memory block references if LRU policy is used for cache block replacement. ... $9$ $16$ $55$ $0$ $5$ $7$ $9$ $16$ $55$ $3$ $5$ $7$ $9$ $16$ $55$

Consider a $2$-way set associative cache memory with $4$ sets and total $8$ cache blocks $(0-7)$ and a main memory with $128$ blocks $(0-127)$. What memory blocks will be...

Ishrat Jahan

9.1k views

Ishrat Jahan asked Nov 3, 2014

27 votes

1 answer

33

GATE IT 2005 | Question: 60
We wish to schedule three processes $P1$, $P2$ and $P3$ ... scheduling respectively? $30$ sec, $30$ sec $30$ sec, $10$ sec $42$ sec, $42$ sec $30$ sec, $42$ sec

We wish to schedule three processes $P1$, $P2$ and $P3$ on a uniprocessor system. The priorities, CPU time requirements and arrival times of the processes are as shown be...

Ishrat Jahan

5.5k views

Ishrat Jahan asked Nov 3, 2014

56 votes

5 answers

34

GATE IT 2005 | Question: 59
Let $a$ and $b$ be two sorted arrays containing $n$ integers each, in non-decreasing order. Let $c$ be a sorted array containing $2n$ integers obtained by merging the two arrays $a$ and $b$. Assuming the arrays are indexed starting from $0$, consider the following ... Which of the following is TRUE? only I and II only I and IV only II and III only III and IV

Let $a$ and $b$ be two sorted arrays containing $n$ integers each, in non-decreasing order. Let $c$ be a sorted array containing $2n$ integers obtained by merging the two...

Ishrat Jahan

11.9k views

Ishrat Jahan asked Nov 3, 2014

37 votes

4 answers

35

GATE IT 2005 | Question: 58
Let $a$ be an array containing $n$ integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference is a specified number $S > 0$. i = 0; j = 1; while (j < n ){ if (E) j++; else if (a[j] - a[i] == S) break; else i+ ... $a[j] - a[i] < S$ $a[i] - a[j] < S$ $a[i] - a[j] > S$

Let $a$ be an array containing $n$ integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference i...

Ishrat Jahan

9.8k views

Ishrat Jahan asked Nov 3, 2014

25 votes

3 answers

36

GATE IT 2005 | Question: 57
What is the output printed by the following program? #include <stdio.h> int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/2, 2*k) - k; } int main () { printf("%d", f(20, 1)); return 0; } $5$ $8$ $9$ $20$

What is the output printed by the following program?#include <stdio.h int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/...

Ishrat Jahan

9.1k views

Ishrat Jahan asked Nov 3, 2014

57 votes

3 answers

37

GATE IT 2005 | Question: 56
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is $4$ $7$ $23$ $99$

Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i...

Ishrat Jahan

10.6k views

Ishrat Jahan asked Nov 3, 2014

27 votes

4 answers

38

GATE IT 2005 | Question: 55
A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is $5, 3, 1, 2, 4, 6, 8, 7.$ ... $1, 2, 3, 4, 8, 7, 6, 5$ $2, 1, 4, 3, 6, 7, 8, 5$ $2, 1, 4, 3, 7, 8, 6, 5$

A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ When the tree is traversed in pre-order and the values in each node printed out, the sequence of value...

Ishrat Jahan

9.3k views

Ishrat Jahan asked Nov 3, 2014

24 votes

2 answers

39

GATE IT 2005 | Question: 54
The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers $1, 2, 3, 4, 5, 6, 7$ in the given order. What will be the contents of ... $1, 3, 2, 5, 4, 7, 6$ $2, 3, 4, 5, 6, 7, 1$

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure....

Ishrat Jahan

8.0k views

Ishrat Jahan asked Nov 3, 2014

56 votes

6 answers

40

GATE IT 2005 | Question: 53
The following$ C$ function takes two ASCII strings and determines whether one is an anagram of the other. An anagram of a string s is a string obtained by permuting the letters in s. int anagram (char *a, char *b) { int count [128], j; for (j = 0; j < 128; j++) count[j] = 0; j ... [j]]++ A: count [a[j++]]++ and B: count[b[j]]-- A: count [a[j]]++ and B: count[b[j++]]--

The following$ C$ function takes two ASCII strings and determines whether one is an anagram of the other. An anagram of a string s is a string obtained by permuting the l...

Ishrat Jahan

12.2k views

Ishrat Jahan asked Nov 3, 2014

71 votes

9 answers

41

GATE IT 2005 | Question: 52
Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE? There exists a cutset in $G$ having ... $e$ cannot be contained in a cycle. All edges in $G$ have the same weight.

Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which ...

Ishrat Jahan

20.8k views

Ishrat Jahan asked Nov 3, 2014

30 votes

5 answers

42

GATE IT 2005 | Question: 51
Let $T(n)$ be a function defined by the recurrence $T(n) = 2T(n/2) + \sqrt n$ for $n \geq 2$ and $T(1) = 1$ Which of the following statements is TRUE? $T(n) = \Theta(\log n)$ $T(n) = \Theta(\sqrt n)$ $T(n) = \Theta(n)$ $T(n) = \Theta(n \log n)$

Let $T(n)$ be a function defined by the recurrence$T(n) = 2T(n/2) + \sqrt n$ for $n \geq 2$ and$T(1) = 1$Which of the following statements is TRUE?$T(n) = \Theta(\log n)$...

Ishrat Jahan

9.4k views

Ishrat Jahan asked Nov 3, 2014

64 votes

7 answers

43

GATE IT 2005 | Question: 50
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h > 0$, then the minimum number of nodes in the tree is $2^{h-1}$ $2^{h-1} + 1$ $2^h - 1$ $2^h$

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h 0$, then the m...

Ishrat Jahan

22.8k views

Ishrat Jahan asked Nov 3, 2014

31 votes

2 answers

44

GATE IT 2005 | Question: 49
An instruction set of a processor has $125$ signals which can be divided into $5$ groups of mutually exclusive signals as follows: Group $1$ $:$ $20$ signals, Group $2$ $:$ $70$ signals, Group $3$ $:$ $2$ signals, Group $4$ ... signals. How many bits of the control words can be saved by using vertical microprogramming over horizontal microprogramming? $0$ $103$ $22$ $55$

An instruction set of a processor has $125$ signals which can be divided into $5$ groups of mutually exclusive signals as follows:Group $1$ $:$ $20$ signals, Group $2$ $:...

Ishrat Jahan

9.4k views

Ishrat Jahan asked Nov 3, 2014

34 votes

5 answers

45

GATE IT 2005 | Question: 48
The circuit shown below implements a $\text{2-input}$ NOR gate using two $2-4$ MUX (control signal $1$ selects the upper input). What are the values of signals $x, y$ and $z$? $1, 0, B$ $1, 0, A$ $0, 1, B$ $0, 1, A$

The circuit shown below implements a $\text{2-input}$ NOR gate using two $2-4$ MUX (control signal $1$ selects the upper input). What are the values of signals $x, y$ and...

Ishrat Jahan

7.7k views

Ishrat Jahan asked Nov 3, 2014

30 votes

5 answers

46

GATE IT 2005 | Question: 47
$(34.4)_{8} × \left ( 23.4 \right )_{8}$ evaluates to $(1053.6)_{8}$ $(1053.2)_{8}$ $(1024.2)_{8}$ None of these

$(34.4)_{8} × \left ( 23.4 \right )_{8}$ evaluates to$(1053.6)_{8}$$(1053.2)_{8}$$(1024.2)_{8}$None of these

Ishrat Jahan

8.2k views

Ishrat Jahan asked Nov 3, 2014

47 votes

2 answers

47

GATE IT 2005 | Question: 46
A line $L$ in a circuit is said to have a $stuck-at-0$ fault if the line permanently has a logic value $0$. Similarly a line $L$ in a circuit is said to have a $stuck-at-1$ fault if the line permanently has a logic value $1$. A circuit is said to have a ... number of distinct multiple $stuck-at$ faults possible in a circuit with $N$ lines is $3^N$ $3^N - 1$ $2^N - 1$ $2$

A line $L$ in a circuit is said to have a $stuck-at-0$ fault if the line permanently has a logic value $0$. Similarly a line $L$ in a circuit is said to have a $stuck-at-...

Ishrat Jahan

7.6k views

Ishrat Jahan asked Nov 3, 2014

24 votes

1 answer

48

GATE IT 2005 | Question: 45
A hardwired CPU uses $10$ control signals $S_1$ to $S_{10}$, in various time steps $T_1$ to $T_5$, to implement $4$ instructions $I_1$ to $I_4$ ... $S_{10} = (I_2 + I_3) \cdot T_2 + I_4 \cdot T_3 + (I_1 + I_3) \cdot T_4 + (I_2 + I_4) \cdot T_5$

A hardwired CPU uses $10$ control signals $S_1$ to $S_{10}$, in various time steps $T_1$ to $T_5$, to implement $4$ instructions $I_1$ to $I_4$ as shown below:$$\begin{ar...

Ishrat Jahan

6.3k views

Ishrat Jahan asked Nov 3, 2014

21 votes

3 answers

49

GATE IT 2005 | Question: 44
We have two designs $D1$ and $D2$ for a synchronous pipeline processor. $D1$ has $5$ pipeline stages with execution times of $3$ nsec, $2$ nsec, $4$ nsec, $2$ nsec and $3$ nsec while the design $D2$ has $8$ pipeline stages each with $2$ nsec ... can be saved using design $D2$ over design $D1$ for executing $100$ instructions? $214$ nsec $202$ nsec $86$ nsec $-200$ nsec

We have two designs $D1$ and $D2$ for a synchronous pipeline processor. $D1$ has $5$ pipeline stages with execution times of $3$ nsec, $2$ nsec, $4$ nsec, $2$ nsec and $3...

Ishrat Jahan

8.3k views

Ishrat Jahan asked Nov 3, 2014

37 votes

5 answers

50

GATE IT 2005 | Question: 43
Which of the following input sequences will always generate a $1$ at the output $z$ ...

Which of the following input sequences will always generate a $1$ at the output $z$ at the end of the third cycle?$\begin{array}{|l|l|}\hline \textbf{A} & \textbf{B} & \t...

Ishrat Jahan

15.3k views

Ishrat Jahan asked Nov 3, 2014

61 votes

8 answers

51

GATE IT 2005 | Question: 42
Two concurrent processes $P1$ and $P2$ use four shared resources $R1, R2, R3$ and $R4$ ... binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed? $1$ $2$ $3$ $4$

Two concurrent processes $P1$ and $P2$ use four shared resources $R1, R2, R3$ and $R4$, as shown below.$$\begin{array}{|l|l|}\hline \textbf{P1} & \textbf{P2} \\ \text...

Ishrat Jahan

12.9k views

Ishrat Jahan asked Nov 3, 2014

75 votes

11 answers

52

GATE IT 2005 | Question: 41
Given below is a program which when executed spawns two concurrent processes : semaphore $X : = 0 ;$ /* Process now forks into concurrent processes $P1$ & $P2$ ... (II) are true. (I) is true but (II) is false. (II) is true but (I) is false Both (I) and (II) are false

Given below is a program which when executed spawns two concurrent processes :semaphore $X : = 0 ;$/* Process now forks into concurrent processes $P1$ & $P2$ */$\begin{ar...

Ishrat Jahan

24.1k views

Ishrat Jahan asked Nov 3, 2014

29 votes

4 answers

53

GATE IT 2005 | Question: 40
A language $L$ satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about $L$ is TRUE? $L$ is necessarily a regular language. $L$ is necessarily a context-free language, but not necessarily a regular language. $L$ is necessarily a non-regular language. None of the above

A language $L$ satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about $L$ is TR...

Ishrat Jahan

15.6k views

Ishrat Jahan asked Nov 3, 2014

64 votes

4 answers

54

GATE IT 2005 | Question: 39
Consider the regular grammar: $S \rightarrow Xa \mid Ya$ $X \rightarrow Za$ $Z \rightarrow Sa \mid \epsilon$ $Y \rightarrow Wa$ $W \rightarrow Sa$ where $S$ is the starting symbol, the set of terminals is $\{a\}$ and the set of non-terminals is ... automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA? $2$ $3$ $4$ $5$

Consider the regular grammar:$S \rightarrow Xa \mid Ya$$X \rightarrow Za$$Z \rightarrow Sa \mid \epsilon$$Y \rightarrow Wa$$W \rightarrow Sa$where $S$ is the starting sym...

Ishrat Jahan

12.2k views

Ishrat Jahan asked Nov 3, 2014

66 votes

5 answers

55

GATE IT 2005 | Question: 38
Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting as well as the accepting state of the PDA. The stack is initialized with one $Z$ before the start of ... $L(P)$ and $N(P)$ are necessarily $Σ^*$. Neither $L(P)$ nor $N(P)$ are necessarily $Σ^*$

Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting ...

Ishrat Jahan

12.4k views

Ishrat Jahan asked Nov 3, 2014

53 votes

4 answers

56

GATE IT 2005 | Question: 37
Consider the non-deterministic finite automaton (NFA) shown in the figure. State $X$ is the starting state of the automaton. Let the language accepted by the NFA with $Y$ as the only accepting state be $L1$. Similarly, let the language accepted by the NFA with $Z$ as ... statements about $L1$ and $L2$ is TRUE? $L1 = L2$ $L1 \subset L2$ $L2 \subset L1$ None of the above

Consider the non-deterministic finite automaton (NFA) shown in the figure.State $X$ is the starting state of the automaton. Let the language accepted by the NFA with $Y$ ...

Ishrat Jahan

16.3k views

Ishrat Jahan asked Nov 3, 2014

50 votes

9 answers

57

GATE IT 2005 | Question: 36
Let $P(x)$ and $Q(x)$ ...

Let $P(x)$ and $Q(x)$ be arbitrary predicates. Which of the following statements is always TRUE?$\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\r...

Ishrat Jahan

14.9k views

Ishrat Jahan asked Nov 3, 2014

18 votes

4 answers

58

GATE IT 2005 | Question: 35
What is the value of $\int_{0}^{2\pi}(x-\pi)^2 (\sin x) dx$ $-1$ $0$ $1$ $\pi$

What is the value of $\int_{0}^{2\pi}(x-\pi)^2 (\sin x) dx$$-1$$0$$1$$\pi$

Ishrat Jahan

6.3k views

Ishrat Jahan asked Nov 3, 2014

31 votes

7 answers

59

GATE IT 2005 | Question: 34
Let $n =$ $p^{2}q$, where $p$ and $q$ are distinct prime numbers. How many numbers m satisfy $1 ≤ m ≤ n$ and $gcd$ $(m, n) = 1?$ Note that $gcd$ $(m, n)$ is the greatest common divisor of $m$ and $n$. $p(q - 1)$ $pq$ $\left ( p^{2}-1 \right ) (q - 1)$ $p(p - 1) (q - 1)$

Let $n =$ $p^{2}q$, where $p$ and $q$ are distinct prime numbers. How many numbers m satisfy $1 ≤ m ≤ n$ and $gcd$ $(m, n) = 1?$ Note that $gcd$ $(m, n)$ is the great...

Ishrat Jahan

8.2k views

Ishrat Jahan asked Nov 3, 2014

45 votes

10 answers

60

GATE IT 2005 | Question: 33
Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $S_2\subset S_1$. What is the maximum cardinality of $C?$ $n$ $n+1$ $2^{n-1} + 1$ $n!$

Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $...

Ishrat Jahan

11.9k views

Ishrat Jahan asked Nov 3, 2014

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