Recent questions tagged gate1994

22 votes

4 answers

1

GATE1992-04-c
Design a 3-bit counter using D-flip flops such that not more than one flip-flop changes state between any two consecutive states.

Design a 3-bit counter using D-flip flops such that not more than one flip-flop changes state between any two consecutive states.

asked Sep 22, 2015 in Digital Logic Arjun 1.6k views

23 votes

5 answers

2

GATE1992-04-b
A priority encoder accepts three input signals $\text{(A, B and C)}$ and produces a two-bit output $(X_1, X_0 )$ corresponding to the highest priority active input signal. Assume $A$ has the highest priority followed by $B$ and $C$ has the lowest ... none of the inputs are active the output should be $00$, design the priority encoder using $4:1$ multiplexers as the main components.

A priority encoder accepts three input signals $\text{(A, B and C)}$ and produces a two-bit output $(X_1, X_0 )$ corresponding to the highest priority active input signal. Assume $A$ has the highest priority followed by $B$ and $C$ has the lowest priority. If none of the inputs are active the output should be $00$, design the priority encoder using $4:1$ multiplexers as the main components.

asked Sep 22, 2015 in Digital Logic Arjun 2.7k views

27 votes

2 answers

3

GATE1994-28
Consider the resource allocation graph in the figure. Find if the system is in a deadlock state Otherwise, find a safe sequence

Consider the resource allocation graph in the figure. Find if the system is in a deadlock state Otherwise, find a safe sequence

asked Oct 6, 2014 in Operating System Kathleen 6.2k views

17 votes

3 answers

4

GATE1994-27
Draw a precedence graph for the following sequential code. The statements are numbered from $S_1$ to $S_6$ $S_1$ read n $S_2$ i := 1 $S_3$ if i > n next $S_4$ a(i) := i+1 $S_5$ i := i+1 $S_6$ next : write a(i) Can this graph be converted to a concurrent program using parbegin-parend construct only?

Draw a precedence graph for the following sequential code. The statements are numbered from $S_1$ to $S_6$ $S_1$ read n $S_2$ i := 1 $S_3$ if i > n next $S_4$ a(i) := i+1 $S_5$ i := i+1 $S_6$ next : write a(i) Can this graph be converted to a concurrent program using parbegin-parend construct only?

asked Oct 6, 2014 in Operating System Kathleen 2.6k views

24 votes

3 answers

5

GATE1994-26
A queue $Q$ containing $n$ items and an empty stack $S$ are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the TOP of the stack, and the order of all other items ... operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

A queue $Q$ containing $n$ items and an empty stack $S$ are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the TOP of the stack, and the order of all other items are ... operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

asked Oct 6, 2014 in DS Kathleen 3.8k views

20 votes

5 answers

6

GATE1994-25
An array $A$ contains $n$ integers in non-decreasing order, $A[1] \leq A[2] \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $i, j,$ such that $A[i]+A[j]=a$ given integer $M$, if such $i, j$ exist.

An array $A$ contains $n$ integers in non-decreasing order, $A[1] \leq A[2] \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $i, j,$ such that $A[i]+A[j]=a$ given integer $M$, if such $i, j$ exist.

asked Oct 6, 2014 in DS Kathleen 2.1k views

23 votes

1 answer

7

GATE1994-24
An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below: V: Set of all vertices in ... Output(I); Complete the algorithm by specifying the property of vertex $u$ in each case. What is the time complexity of the algorithm?

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below: V: Set of all vertices in the tree; ... ; Output(I); Complete the algorithm by specifying the property of vertex $u$ in each case. What is the time complexity of the algorithm?

asked Oct 6, 2014 in Algorithms Kathleen 2.5k views

5 votes

0 answers

8

GATE1994-23
Suppose we have a computer with single register and only three instructions given below: ... (E)\mid id$}\\ \end{array}$ Write a syntax directed translation to generate code using this grammar for the computer described above.

Suppose we have a computer with single register and only three instructions given below: ... T \rightarrow (E)\mid id$}\\ \end{array}$ Write a syntax directed translation to generate code using this grammar for the computer described above.

asked Oct 6, 2014 in Compiler Design Kathleen 612 views

1 vote

1 answer

9

GATE1994-22
Consider the program below: Program main: var r:integer; procedure two: begin write (r); end procedure one: var r:integer; begin r:=5; two; end begin r:=2; two; one; two; end What is printed by the above program if Static scoping is assumed for all variables; Dynamic scoping is assumed for all variables. Give reasons for your answer.

Consider the program below: Program main: var r:integer; procedure two: begin write (r); end procedure one: var r:integer; begin r:=5; two; end begin r:=2; two; one; two; end What is printed by the above program if Static scoping is assumed for all variables; Dynamic scoping is assumed for all variables. Give reasons for your answer.

asked Oct 6, 2014 in Programming Kathleen 907 views

24 votes

3 answers

10

GATE1994-21
Consider the following recursive function: function fib (n:integer);integer; begin if (n=0) or (n=1) then fib := 1 else fib := fib(n-1) + fib(n-2) end; The above function is run on a computer with a stack of $64$ bytes. Assuming that only ... and an address takes $2$ bytes each, estimate the maximum value of $n$ for which the stack will not overflow. Give reasons for your answer.

Consider the following recursive function: function fib (n:integer);integer; begin if (n=0) or (n=1) then fib := 1 else fib := fib(n-1) + fib(n-2) end; The above function is run on a computer with a stack of $64$ bytes. Assuming that only return ... value and an address takes $2$ bytes each, estimate the maximum value of $n$ for which the stack will not overflow. Give reasons for your answer.

asked Oct 6, 2014 in Programming Kathleen 6.2k views

14 votes

4 answers

11

GATE1994-20
A grammar $G$ is in Chomsky-Normal Form (CNF) if all its productions are of the form $A \to BC$ or $A \to a$, where $A,B$ and $C$, are non-terminals and $a$ is a terminal. Suppose $G$ is a CFG in CNF and $w$ is a string in $L(G)$ of length $n$, then how long is a derivation of $w$ in $G$?

A grammar $G$ is in Chomsky-Normal Form (CNF) if all its productions are of the form $A \to BC$ or $A \to a$, where $A,B$ and $C$, are non-terminals and $a$ is a terminal. Suppose $G$ is a CFG in CNF and $w$ is a string in $L(G)$ of length $n$, then how long is a derivation of $w$ in $G$?

asked Oct 6, 2014 in Compiler Design Kathleen 2.5k views

25 votes

4 answers

12

GATE1994-19
(a) Given a set: $S = \left\{x \mid \text{ there is an x-block of 5's in the decimal expansion of } \pi\right\}$ (Note: $x$-$block$ is a maximal block of $x$ successive $5$ ... Given that a language $L_1$ is regular and and that the language $L_1 \cup L_2$ is regular, is the language $L_2$ always regular? Prove your answer.

(a) Given a set: $S = \left\{x \mid \text{ there is an x-block of 5's in the decimal expansion of } \pi\right\}$ (Note: $x$-$block$ is a maximal block of $x$ successive $5$'s) Which of the following statements is true with respect to $S$? No ... b) Given that a language $L_1$ is regular and and that the language $L_1 \cup L_2$ is regular, is the language $L_2$ always regular? Prove your answer.

asked Oct 6, 2014 in Theory of Computation Kathleen 2.9k views

15 votes

2 answers

13

GATE1994-18
State whether the following statements are True or False with reasons for your answer A subroutine cannot always be used to replace a macro in an assembly language program. A symbol declared as ‘external’ in an assembly language program is assigned an address outside the program by the assembler itself.

State whether the following statements are True or False with reasons for your answer A subroutine cannot always be used to replace a macro in an assembly language program. A symbol declared as ‘external’ in an assembly language program is assigned an address outside the program by the assembler itself.

asked Oct 6, 2014 in Compiler Design Kathleen 1.3k views

9 votes

4 answers

14

GATE1994-17
State whether the following statements are True or False with reasons for your answer: Coroutine is just another name for a subroutine. A two pass assembler uses its machine opcode table in the first pass of assembly.

State whether the following statements are True or False with reasons for your answer: Coroutine is just another name for a subroutine. A two pass assembler uses its machine opcode table in the first pass of assembly.

asked Oct 6, 2014 in Compiler Design Kathleen 1.4k views

3 votes

0 answers

15

GATE1994-16
Every element $a$ of some ring $(R, +, o)$ satisfies the equation $a\;o\;a=a$. Decide whether or not the ring is commutative.

Every element $a$ of some ring $(R, +, o)$ satisfies the equation $a\;o\;a=a$. Decide whether or not the ring is commutative.

asked Oct 6, 2014 in Set Theory & Algebra Kathleen 308 views

15 votes

2 answers

16

GATE1994-15
Use the patterns given to prove that $\sum\limits_{i=0}^{n-1} (2i+1) = n^2$ (You are not permitted to employ induction) Use the result obtained in (a) to prove that $\sum\limits_{i=1}^{n} i = \frac{n(n+1)}{2}$

Use the patterns given to prove that $\sum\limits_{i=0}^{n-1} (2i+1) = n^2$ (You are not permitted to employ induction) Use the result obtained in (a) to prove that $\sum\limits_{i=1}^{n} i = \frac{n(n+1)}{2}$

asked Oct 6, 2014 in Combinatory Kathleen 894 views

26 votes

6 answers

17

GATE1994-14
Consider $B^+$ - tree of order $d$ shown in figure. (A $B^+$ - tree of order $d$ contains between $d$ and $2d$ keys in each node) Draw the resulting $B^+$ - tree after $100$ is inserted in the figure below. For a $B^+$ - tree of order $d$ with $n$ leaf nodes, the number of nodes accessed during a search is $O(-)$.

Consider $B^+$ - tree of order $d$ shown in figure. (A $B^+$ - tree of order $d$ contains between $d$ and $2d$ keys in each node) Draw the resulting $B^+$ - tree after $100$ is inserted in the figure below. For a $B^+$ - tree of order $d$ with $n$ leaf nodes, the number of nodes accessed during a search is $O(-)$.

asked Oct 6, 2014 in Databases Kathleen 4.9k views

16 votes

3 answers

18

GATE1994-13
Consider the following relational schema: COURSES (cno, cname) STUDENTS (rollno, sname, age, year) REGISTERED_FOR (cno, rollno) The underlined attributes indicate the primary keys for the relations. The year' attribute for the STUDENTS relation indicates the year in which ... have registered for cno 322. Write a SQL query to print the age and year of the youngest student in each year.

Consider the following relational schema: COURSES (cno, cname) STUDENTS (rollno, sname, age, year) REGISTERED_FOR (cno, rollno) The underlined attributes indicate the primary keys for the relations. The year' attribute for the STUDENTS relation indicates the year in which the ... who have registered for cno 322. Write a SQL query to print the age and year of the youngest student in each year.

asked Oct 6, 2014 in Databases Kathleen 2.8k views

19 votes

3 answers

19

GATE1994-12
Assume that a CPU has only two registers $R_1$ and $R_2$ and that only the following instruction is available $XOR \: R_i, R_j;\{R_j \leftarrow R_i \oplus R_j, \text{ for } i, j =1, 2\}$ Using this XOR instruction, find an instruction sequence in order to ... $R_1$ and $R_2$ The line p of the circuit shown in figure has stuck at 1 fault. Determine an input test to detect the fault.

Assume that a CPU has only two registers $R_1$ and $R_2$ and that only the following instruction is available $XOR \: R_i, R_j;\{R_j \leftarrow R_i \oplus R_j, \text{ for } i, j =1, 2\}$ Using this XOR instruction, find an instruction sequence in order to ... registers $R_1$ and $R_2$ The line p of the circuit shown in figure has stuck at 1 fault. Determine an input test to detect the fault.

asked Oct 6, 2014 in CO and Architecture Kathleen 1.9k views

21 votes

2 answers

20

GATE1994-11
Find the contents of the flip-flop $Q_2, Q_1$ and $Q_0$ in the circuit of figure, after giving four clock pulses to the clock terminal. Assume $Q_2Q_1Q_0=000$ initially.

Find the contents of the flip-flop $Q_2, Q_1$ and $Q_0$ in the circuit of figure, after giving four clock pulses to the clock terminal. Assume $Q_2Q_1Q_0=000$ initially.

asked Oct 6, 2014 in Digital Logic Kathleen 2.6k views

0 votes

0 answers

21

GATE1994-10

asked Oct 6, 2014 in CO and Architecture Kathleen 228 views

23 votes

6 answers

22

GATE1994-9
Following $7$ ... (assuming that at most $1$ bit could be corrupted). If the message contains an error find the bit which is erroneous and gives correct message.

Following $7$ ... (assuming that at most $1$ bit could be corrupted). If the message contains an error find the bit which is erroneous and gives correct message.

asked Oct 6, 2014 in Computer Networks Kathleen 3.7k views

25 votes

3 answers

23

GATE1994-8
A rooted tree with $12$ nodes has its nodes numbered $1$ to $12$ in pre-order. When the tree is traversed in post-order, the nodes are visited in the order $3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1$. Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.

A rooted tree with $12$ nodes has its nodes numbered $1$ to $12$ in pre-order. When the tree is traversed in post-order, the nodes are visited in the order $3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1$. Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.

asked Oct 6, 2014 in DS Kathleen 3.7k views

4 votes

2 answers

24

GATE1994-7
An array $A$ contains $n$ integers in locations $A[0], A[1], \dots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1\leq K \leq n-1$. An incomplete algorithm for doing this in linear time, without using another array is given below. ... A[j]:=____; j:=(j+K) mod n; if j<min then min:=j; end; A[(n+i-K)mod n]:=____; i:=______; end;

An array $A$ contains $n$ integers in locations $A[0], A[1], \dots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1\leq K \leq n-1$. An incomplete algorithm for doing this in linear time, without using another array is given below. Complete ... A[j]:=____; j:=(j+K) mod n; if j<min then min:=j; end; A[(n+i-K)mod n]:=____; i:=______; end;

asked Oct 6, 2014 in Algorithms Kathleen 1.6k views

15 votes

2 answers

25

GATE1994-6
What function of $x$, $n$ is computed by this program? Function what(x, n:integer): integer: Var value : integer begin value := 1 if n > 0 then begin if n mod 2 =1 then value := value * x; value := value * what(x*x, n div 2); end; what := value; end;

What function of $x$, $n$ is computed by this program? Function what(x, n:integer): integer: Var value : integer begin value := 1 if n > 0 then begin if n mod 2 =1 then value := value * x; value := value * what(x*x, n div 2); end; what := value; end;

asked Oct 6, 2014 in Algorithms Kathleen 1.3k views

14 votes

3 answers

26

GATE1994-5
A $3-\text{ary}$ tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a $3-\text{ary}$ tree with $n$ internal nodes is $2(n-1)$.

A $3-\text{ary}$ tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a $3-\text{ary}$ tree with $n$ internal nodes is $2(n-1)$.

asked Oct 6, 2014 in DS Kathleen 3.8k views

24 votes

1 answer

27

GATE1994-4
Let $*$ be a Boolean operation defined as $A*B = AB + \overline{A}\;\overline{B}$. If $C=A*B$ then evaluate and fill in the blanks: $A*A=$____ $C*A=$____ Solve the following boolean equations for the values of $A, B$ and $C$: $AB+\overline{A}C=1$ $AC+B=0$

Let $*$ be a Boolean operation defined as $A*B = AB + \overline{A}\;\overline{B}$. If $C=A*B$ then evaluate and fill in the blanks: $A*A=$____ $C*A=$____ Solve the following boolean equations for the values of $A, B$ and $C$: $AB+\overline{A}C=1$ $AC+B=0$

asked Oct 6, 2014 in Digital Logic Kathleen 2.2k views

15 votes

2 answers

28

GATE1994-3.13
Let $p$ and $q$ be propositions. Using only the Truth Table, decide whether $p \Longleftrightarrow q$ does not imply $p \to \lnot q$ is True or False.

Let $p$ and $q$ be propositions. Using only the Truth Table, decide whether $p \Longleftrightarrow q$ does not imply $p \to \lnot q$ is True or False.

asked Oct 6, 2014 in Mathematical Logic Kathleen 3.2k views

12 votes

3 answers

29

GATE1994-3.12
Find the inverse of the matrix $\begin{bmatrix} 1 & 0 & 1 \\ -1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}$

Find the inverse of the matrix $\begin{bmatrix} 1 & 0 & 1 \\ -1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}$

asked Oct 6, 2014 in Linear Algebra Kathleen 2.4k views

20 votes

5 answers

30

GATE1994-3.11
State True or False with reason Logical data independence is easier to achieve than physical data independence

State True or False with reason Logical data independence is easier to achieve than physical data independence

asked Oct 6, 2014 in Databases Kathleen 3.8k views

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

GO Book for GATECSE 2022

Subjects

Network Sites

Recent questions tagged gate1994

Log In

Register

GO Book for GATECSE 2022

Recent Posts

Subjects

Recent Blog Comments

Network Sites

Recent questions tagged gate1994