The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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 gate1994
0
votes
1
answer
1
GATE1994
The number of substrings(of all lengths inclusive) that can be formed from character string of length n is $a)n$ $b)n^{2}$ $c)\frac{n\left ( n1 \right )}{2}$ $d)\frac{n\left ( n+1 \right )}{2}+1$
asked
May 16, 2018
in
Theory of Computation
by
anji
(
29
points)

257
views
theoryofcomputation
numericalanswers
gate1994
+13
votes
4
answers
2
GATE199204c
Design a 3bit counter using Dflip flops such that not more than one flipflop changes state between any two consecutive states.
asked
Sep 22, 2015
in
Digital Logic
by
Arjun
Veteran
(
400k
points)

799
views
gate1994
digitallogic
flipflop
+12
votes
1
answer
3
GATE199204b
A priority encoder accepts three input signals $\text{(A, B and C)}$ and produces a twobit output $(X1, X0 )$ 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.
asked
Sep 22, 2015
in
Digital Logic
by
Arjun
Veteran
(
400k
points)

1k
views
gate1994
digitallogic
multiplexer
+21
votes
2
answers
4
GATE199428
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
by
Kathleen
Veteran
(
59.9k
points)

2.2k
views
gate1994
operatingsystem
resourceallocation
normal
+15
votes
3
answers
5
GATE199427
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 parbeginparend construct only?
asked
Oct 6, 2014
in
Operating System
by
Kathleen
Veteran
(
59.9k
points)

1.3k
views
gate1994
operatingsystem
processsynchronization
normal
+20
votes
2
answers
6
GATE199426
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.
asked
Oct 6, 2014
in
DS
by
Kathleen
Veteran
(
59.9k
points)

1.3k
views
gate1994
datastructure
queues
stack
normal
+15
votes
4
answers
7
GATE199425
An array $A$ contains $n$ integers in nondecreasing 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
by
Kathleen
Veteran
(
59.9k
points)

869
views
gate1994
datastructure
arrays
normal
+20
votes
1
answer
8
GATE199424
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?
asked
Oct 6, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.9k
points)

1.1k
views
gate1994
algorithms
graphalgorithms
normal
+4
votes
0
answers
9
GATE199423
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.
asked
Oct 6, 2014
in
Compiler Design
by
Kathleen
Veteran
(
59.9k
points)

381
views
gate1994
compilerdesign
grammar
syntaxdirectedtranslation
descriptive
+1
vote
1
answer
10
GATE199422
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
by
Kathleen
Veteran
(
59.9k
points)

450
views
gate1994
programming
variablebinding
normal
outofsyllabusnow
+13
votes
3
answers
11
GATE199421
Consider the following recursive function: function fib (n:integer);integer; begin if (n=0) or (n=1) then fib := 1 else fib := fib(n1) + fib(n2) 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.
asked
Oct 6, 2014
in
Programming
by
Kathleen
Veteran
(
59.9k
points)

1.5k
views
gate1994
programming
recursion
normal
+11
votes
4
answers
12
GATE199420
A grammar $G$ is in ChomskyNormal Form (CNF) if all its productions are of the form $A \to BC$ or $A \to a$, where $A,B$ and $C$, are nonterminals 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
by
Kathleen
Veteran
(
59.9k
points)

1.1k
views
gate1994
compilerdesign
grammar
normal
+15
votes
3
answers
13
GATE199419
(a) Given a set: $S = \left\{x \mid \text{ there is an xblock 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.
asked
Oct 6, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.9k
points)

1.3k
views
gate1994
theoryofcomputation
identifyclasslanguage
normal
+14
votes
2
answers
14
GATE199418
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
by
Kathleen
Veteran
(
59.9k
points)

621
views
gate1994
compilerdesign
normal
assembler
truefalse
+9
votes
3
answers
15
GATE199417
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
by
Kathleen
Veteran
(
59.9k
points)

569
views
gate1994
compilerdesign
normal
assembler
+3
votes
0
answers
16
GATE199416
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
by
Kathleen
Veteran
(
59.9k
points)

220
views
gate1994
settheory&algebra
ring
normal
outofsyllabusnow
+13
votes
2
answers
17
GATE199415
Use the patterns given to prove that $\sum\limits_{i=0}^{n1} (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
by
Kathleen
Veteran
(
59.9k
points)

467
views
gate1994
permutationsandcombinations
proof
summation
descriptive
+19
votes
6
answers
18
GATE199414
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
by
Kathleen
Veteran
(
59.9k
points)

2.5k
views
gate1994
databases
btree
normal
+12
votes
2
answers
19
GATE199413
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.
asked
Oct 6, 2014
in
Databases
by
Kathleen
Veteran
(
59.9k
points)

798
views
gate1994
databases
relationalalgebra
sql
normal
+12
votes
3
answers
20
GATE199412
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.
asked
Oct 6, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.9k
points)

897
views
gate1994
coandarchitecture
machineinstructions
normal
+12
votes
2
answers
21
GATE199411
Find the contents of the flipflop $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
by
Kathleen
Veteran
(
59.9k
points)

956
views
gate1994
digitallogic
circuitoutput
normal
0
votes
0
answers
22
GATE199410
asked
Oct 6, 2014
in
CO & Architecture
by
Kathleen
Veteran
(
59.9k
points)

146
views
gate1994
coandarchitecture
8085
outofsyllabusnow
+15
votes
5
answers
23
GATE19949
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
by
Kathleen
Veteran
(
59.9k
points)

1.5k
views
gate1994
computernetworks
errordetection
hammingcode
normal
+18
votes
2
answers
24
GATE19948
A rooted tree with $12$ nodes has its nodes numbered $1$ to $12$ in preorder. When the tree is traversed in postorder, 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
by
Kathleen
Veteran
(
59.9k
points)

1.6k
views
gate1994
datastructure
binarytree
normal
+3
votes
1
answer
25
GATE19947
An array $A$ contains $n$ integers in locations $A[0], A[1], \dots A[n1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1\leq K \leq n1$. 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+iK)mod n]:=____; i:=______; end;
asked
Oct 6, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.9k
points)

374
views
gate1994
algorithms
normal
+11
votes
2
answers
26
GATE19946
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
by
Kathleen
Veteran
(
59.9k
points)

626
views
gate1994
algorithms
identifyfunction
normal
+12
votes
1
answer
27
GATE19945
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(n1)$.
asked
Oct 6, 2014
in
DS
by
Kathleen
Veteran
(
59.9k
points)

1.1k
views
gate1994
datastructure
trees
proof
+17
votes
1
answer
28
GATE19944
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
by
Kathleen
Veteran
(
59.9k
points)

648
views
gate1994
digitallogic
normal
booleanexpressions
+14
votes
3
answers
29
GATE19943.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.
asked
Oct 6, 2014
in
Mathematical Logic
by
Kathleen
Veteran
(
59.9k
points)

952
views
gate1994
mathematicallogic
normal
propositionallogic
descriptive
+10
votes
3
answers
30
GATE19943.12
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
by
Kathleen
Veteran
(
59.9k
points)

944
views
gate1994
linearalgebra
matrices
easy
descriptive
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
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has begun
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
Follow @csegate
Recent questions tagged gate1994
Recent Blog Comments
@Anuj Mishra how did you study CLRS?what...
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
49,430
questions
53,616
answers
185,966
comments
70,892
users