GATE CSE
I. (n + k)m = $$\Theta \,({n^m})$$ where k and m are constants
II. 2n+1 = O(2n)
III. 22n = O(22n)
Which of those claims are correct?
$$$A[j,k] = \left\{ {\matrix{ {1\,if\,(j,\,k)} \cr {1\,otherwise} \cr } } \right.$$$ Consider the following algorithm.
for i = 1 to n
for j = 1 to n
for k = 1 to n
A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); Consider the grammar shown below
$$\eqalign{ & S \to iEtSS'\,|\,\,a \cr & S' \to eS\,|\,\,\varepsilon \cr & E \to b \cr} $$In the predictive parse table, $$M$$, of this grammar, the entries $$M\left[ {S',e} \right]$$ and $$M\left[ {S',\phi } \right]$$ respectively are
Consider the translation scheme shown below
$$\eqalign{ & S \to TR \cr & R \to + T\left\{ {pr{\mathop{\rm int}} (' + ');} \right\}\,R\,|\,\varepsilon \cr & T \to num\,\left\{ {pr{\mathop{\rm int}} (num.val);} \right\} \cr} $$Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will print
Consider the syntax directed definition shown below.
Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X : = Y + Z', the 3-address code sequence generated by this definition is
Consider the grammar shown below.
$$\eqalign{ & S \to CC \cr & C \to cC\,|\,d \cr} $$This grammar is
$$1.\,\,\,\,\,$$ The $$j+1$$ instruction uses the result of the $$j$$-$$th$$ instruction as an operand
$$2.\,\,\,\,\,$$ The execution of a conditional jump instruction
$$3.\,\,\,\,\,$$ The $$j$$-$$th$$ and $$j+1$$ instruction require the $$ALU$$ at the same time
Which of the above can cause a hazard?
Let $$s, e,$$ and $$m$$ be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is
$$\left\{ {\matrix{ {{{\left( { - 1} \right)}^s}\left( {1 + m \times {2^{ - 9}}} \right){2^{e - 31}},} & {if\,the\,{\mathop{\rm exponent}\nolimits} \, \ne \,111111} \cr {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,0} & {otherwise\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,} \cr } } \right.$$
What is the maximum difference between two successive real numbers representable in this system?
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e
What are depth first traversals of the above graph?struct item {
int data;
struct item * next;
};
int f(struct item *p) {
return ((p == NULL) || (p ->next == NULL) ||
((p->data <= p -> next -> data) &&
f(p-> next)));
}
Which of the following statements is correct?
Select distinct a1, a2, ..., an
From r1, r2, ..., rm
Where P; Students: (Roll_number, Name, Date_of_birth)
Courses: (Course number, Course_name, Instructor)
Grades: (Roll_number, Course_number, Grade)
Select distinct Name
From Students, Courses, Grades
Where Students.Roll_number = Grades.Roll_number
and Courses.Instructor = 'Korth'
and Courses.Course_number = Grades.Course_number
and Grades.grade = 'A';$$\eqalign{ & \,\,\,\,Date\,\,of\,\,Birth\,\, \to \,\,Age \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Age\,\, \to \,\,Eligibility \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Name\,\, \to \,\,Roll\_number \cr & \,\,\,\,\,Roll\_number\,\, \to \,\,Name \cr & Course\_number\, \to \,\,Course\_name \cr & Course\_number\, \to Instructor \cr & (Roll\_Number,\,Course\_number)\,\, \to \,\,Grade \cr} $$
The relation (Roll_number, Name, Date_of_Birth, Age) is
If the operands are in $$2's$$ complement representation, which of the following operations can be performed by suitably setting the control lines $$K$$ and $${C_0}$$ only ( + and - denote addition and subtraction respectively)?
Let $${z_k},\,{n_k}$$ denote the number of $$0’s$$ and $$1’s$$ respectively in initial $$k$$ bits of the input
$$\left({{z_k} + {n_k} = k} \right).$$ The circuit outputs $$00$$ until one of the following conditions holds.
$$ * \,\,\,\,\,$$ $${z_k} = {n_k} + 2.\,\,\,$$ In this case, the output at the $$k$$-th and all subsequent clock ticks is $$10.$$
$$ * \,\,\,\,\,$$ $${n_k} = {z_k} + 2.\,\,\,$$ In this case, the output at the $$k$$-th and all subsequent clock ticks is $$01.$$
What is the minimum number of states required in the state transition graph of the above circuit?
The non-inverting buffers have delays $${\delta _1} = 2$$ $$ns$$ and $${\delta _2} = 4$$ $$ns$$ as shown in the figure. Both $$XOR$$ gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level $$0$$ at time$$0.$$ If the following waveform is applied at input $$A$$, how many transition(s) (change of logic levels) occurs(s) at $$B$$ during the interval from $$0$$ to $$10$$ $$ns?$$
Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of $$\alpha $$, does this system of equations have infinitely many solutions?
i) Each is sorted in ascending order.
ii) $$B$$ has $$5$$ and $$C$$ has $$3$$ elements, and
iii) The result of merging $$B$$ $$C$$ gives $$A$$?
Which of the following statements related to this rule is FALSE?
Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address $$0 \times 00000000,$$ two contiguous data pages starting at virtual address $$0 \times 00400000,$$ and a stack page starting at virtual address $$0 \times FFFFF000.$$ The amount of memory required for storing the page tables of this process is
Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest $$0.5$$ ns)
Process P:
while(1){
W:
Print '0';
Print '0';
X:
}
Process Q:
while(1){
Y:
Print '1';
Print '1';
Z:
}
Which of the following will ensure that the output string never contains a substring of the form 01n0 or 10n1 where n is odd?
Process P:
while(1){
W:
Print '0';
Print '0';
X:
}
Process Q:
while(1){
Y:
Print '1';
Print '1';
Z:
}
Which of the following will always lead to an output starting with 001100110011
#include < stdio.h >
#define print(x) printf("%d ", x)
int x;
void Q(int z) {
z += x; print(z);
}
void P(int *y) {
int x = *y+2;
Q(x); *y = x-1;
print(x);
}
main(void) {
x = 5;
P(&x);
print(x);
}global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {
P(i + j);
}global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {
P(i + j);
}Class P {
void f(int i) {
print(i);
}
}
Class Q subclass of P {
void f(int i) {
print(2*i);
}
}Px = new Q();
Qy = new Q();
Pz = new Q();
x.f(1); ((P)y).f(1); z.f(1);
Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be
int * A[10], B[10][10];
Of the following expressionsI. A[2]
II. A[2] [3]
III. B[1]
IV. B[2] [3]
Which will not give compile-time errors if used as left hand sides of assignment statements in a C program?
float f,(float x, int y) {
float p, s; int i;
for (s=1,p=1,i=1; i < y; i++) {
p *= x/i;
s+=p;
}
return s;
}$${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \right\}$$
$${L_1} = \left\{ { < M,w,1 > \left| M \right.} \right.$$ does not halts on $$\left. w \right\}$$
Here $$ < M,\,w,\,i > $$ is a triplet, whose first component, $$M$$ is an encoding of a Turing Machine, second component, $$w$$, is a string, and third component, $$t,$$ is a bit.
Let $$L = {L_0} \cup {L_1}.$$ Which of the following is true?
The table is interpreted as illustrated below. The entry $$\left( {{q_1},1,\,R} \right)$$ in row $${{q_0}}$$ and column $$1$$ signifies that if $$M$$ is in state $${{q_0}}$$ and reads $$1$$ on the current tape square, then it writes $$1$$ on the same tape square, moves its tape head one position to the right and transitions to state $${{q_1}}$$.
Which of the following statements is true about $$M?$$
$$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,\,\,Otherwise} \cr } } \right.$$
Which of the following statement is true?
Let $$S$$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $$1$$. The number of strings in $$S$$ that are accepted by $$M$$ is
Let the language accepted by $$M$$ be $$L.$$ Let $${L_1}$$ be the language accepted by the $$NFA$$, $${M_1}$$ obtained by changing the accepting state of $$M$$ to a non accepting state and by changing the non accepting state of $$M$$ to accepting states. Which of the following statements is true?