GATE CSE

T(1) = 1
T(n) = 2T(n - 1)+n, $$n \ge 2$$
Evaluates to
int recursive(int n){
if(n == 1){
return (1);
}
return (recursive(n - 1) + recursive(n - 1));
}
counter = 0;
for(i = 1; i <= n; i++){
if(A[i]==1){
counter++;
}else{
f(counter); counter = 0;
}
}
The complexity of this program fragment is(Assume m > 1, $$ \in > 0$$)
x = m;
y = 1;
while(x - y > ε){
x = (x + y) / 2;
y = m/x;
}
print(x);
Consider the grammar with the following translation rules and E as the start symbol.
$$\eqalign{ & E \to {E_1}\# T\,\,\left\{ {E.value = {E_1}.value*T.value} \right\} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,|T\,\,\,\,\,\,\,\,\,\,\,\,\left\{ {E.value = T.value} \right\} \cr & T \to {T_1}\& F\,\,\,\left\{ {T.value = {T_1}.value*F.value} \right\} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,|\,F\,\,\,\,\,\,\,\,\,\,\,\left\{ {T.value = F.value} \right\} \cr & F \to num\,\,\,\,\,\,\,\left\{ {F.value = num.value} \right\} \cr} $$Compute E.value for the root of the parse tree for the expression:
2 # 3 & 5 # 6
& 4.
Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r, s, t are terminals.
$$\eqalign{ & 1.\,P \to QR \cr & 2.\,P \to QsR \cr & 3.\,P \to \varepsilon \cr & 4.\,P \to QtRr \cr} $$Group –1
P. Data link layerQ. Network layer
R. Transport layer
Group – 2
1. Ensures reliable transport of data over a physical point-to-point link2. Encodes/decodes data for physical transimission
3. Allows end-to-end communication between two processes
4. Routes data from one network node to the next
Consider three IP networks A, B and C. Host HA in networks A sends messages each containing 180 bytes of application data to a host HC in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate network B. the maximum packet size, including 20 byte IP header, in each network is:
A : 1000 bytesB : 100 bytes
C : 1000 bytes
The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).

Consider three IP networks A, B and C. Host HA in networks A sends messages each containing 180 bytes of application data to a host HC in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate network B. the maximum packet size, including 20 byte IP header, in each network is:
A : 1000 bytesB : 100 bytes
C : 1000 bytes
The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).

Assuming that the packets are correctly delivered, how many bytes, including headers, are delivered to the IP layer at the destination for one application message, in the best case? Consider only data packets.

On which interface will the router forward packets addressed to destinations 128.75.43.16 and 192.12.17.10 respectively?

Let the clock cycles required for various operations be as follows:
Register to/from memory transfer:
$$3$$ clock cycles
ADD with both operands in register:
$$1$$ clock cycle
Instruction fetch and decode:
$$2$$ clock cycles per word
The total number of clock cycle required to execute the program is

Consider that the memory is byte addressable with word size $$32$$ bits, and the program has been loaded starting from memory location $$1000$$ (decimal). If an interrupt occurs while the $$CPU$$ has been halted after executing the HALT instruction, the return address (in decimal) saved in the stack will be
$$1.$$ Absolute addressing
$$2.$$ Based addressing
$$3.$$ Relative addressing
$$4.$$ Indirect addressing
How many bits are there in the $$X$$ and $$Y$$ fields, and what is the size of the control memory in number of words?
$$\eqalign{ & \left( {113. + - 111.} \right) + 7.51 \cr & 113. + \left( { - 111. + 7.51} \right) \cr} $$
i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 has to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder
struct CellNode{
struct CellNode *leftChild;
int element;
struct CellNode *rightChild;
};
int Dosomething (struct CellNode *ptr) {
int value = 0;
if (ptr ! = NULL)
{ if (ptr - > leftChild ! = NULL)
value = 1 + DoSomething (ptr - > leftChild);
if (ptr - > rightChild ! = NULL)
value = max(value,1 + DoSomething (ptr - > rightChild));
}
return (value);
}
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

Table: Student
Roll_no | Name | Dept_id |
---|---|---|
1 | ABC | 1 |
2 | DEF | 1 |
3 | GHI | 2 |
4 | JKL | 3 |
Table: Department
Dept_id | Dept_name |
---|---|
1 | A |
2 | B |
3 | C |
Roll_no is the primary key of the Student table, Dept_id is the primary key of the
Department table and Studetn.Dept_id is a foreign key from
Department. Dept_id.
(i) update Student set Dept_id = Null where Roll_no =1
(ii) update Department set Dept_id = Null where Dept_id =1
Insert into department values (1, ‘Mathematics’)
Insert into department values (2, ‘Physics’)
Insert into student values (1, ‘Navin’,1)
Insert into student values (2, ‘Mukesh’,2)
Insert into student values (3, ‘Gita’,1)
How many rows and columns will be retrieved by the following SQL statement?
Select * from student, department;
The employee information in a company is stored in the relation
Employee (name, sex, salary, deptName)Consider the following SQL query
Select deptName
From Employee
Where sex = ‘M’
Group by deptName
Having avg(salary) >
(Select avg (salary) From Employee);
It returns the names of the department in whichStudents (rollno, name, address)
Enroll(rollno,courseno, coursename)
Where the primary keys are shown underlined. The number of tuples in the student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where '*' denotes natural join?Name, courseNo $$\,\, \to \,\,$$ grade
RollNo, courseNo $$\,\, \to \,\,$$ grade
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,$$ Name $$\,\, \to \,\,$$ rollNo
$$\,\,\,\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,$$ RollNo $$\,\, \to \,\,$$ name
The highest normal form of this relation scheme is
The attributes of $$E1$$ are $$A11, A12$$ and $$A13$$ where $$A11$$ is the key attribute. The attributes of $$E2$$ are $$A21, A22$$ and $$A23$$ where $$A21$$ is the key attribute and $$A23$$ is a multi-valued attribute. Relation $$R$$ does not have any attribute. A relational database containing minimum number of tables with each table satisfying the requirements of the third normal form $$(3NF)$$ is designed form the above $$ERD.$$ The minimum number of tables in the database is
To complete the circuit, the input $$X$$ should be
How many students have not taken any of the three courses?

What is the value of the determinant of $$A$$?
and $${X^2} - X + 1 = 0$$
($${\rm I}$$ is the identity matrix and $$O$$ is the zero matrix), then the inverse of $$X$$ is

- x + 5y = - 1
x - y = 2
x + 3y = 3
$$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$
$$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \right) + n,\,n \ge 2$$
evaluates to
i) An element $$x$$ in $$A$$ is related to an element $$y$$ in $$B$$ (under $${R_1}$$) if $$ x + y $$ is divisible by $$3$$.
ii) An element EExEE in $$B$$ is related to an elements $$y$$ in $$C$$ (under $${R_2}$$) if $$x + y$$ is even but not divisible by $$3$$.
Which is the composite relation $$R1R2$$ from $$A$$ to $$C$$?
The reflexive transitive closure of $$S$$ is
S = { {1, 2}, 1, 2, 3}, {1, 3, 5}, {1, 2, 4},
{1, 2, 3, 4, 5} }
Is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?

(0, 0), (1, 0), (1, 2) and (0, 2). If p is the length of the position vector of the point, the expected value of $${p^2}$$ is
$$P:\left[ {\left( {\neg p \vee q} \right) \wedge \left( {r \to s} \right) \wedge \left( {p \vee r} \right)} \right] \to \left( {\neg s \to q} \right)$$
$$Q:\left[ {\left( {\neg p \wedge q} \right) \wedge \left[ {q \to \left( {p \to r} \right)} \right]} \right] \to \neg r$$
$$R:\left[ {\left[ {\left( {q \wedge r} \right) \to p} \right] \wedge \left( {\neg q \vee p} \right)} \right] \to r$$
$$S:\left[ {p \wedge \left( {p \to r} \right) \wedge \left( {q \vee \neg r} \right)} \right] \to q$$
Which of the above arguments are valid?
Which one of the following is its equivalent?
$$Some\,boys\,in\,the\,class\,are\,taller\,than\,all\,the\,girls$$
Note: taller$$\left( {x,\,y} \right)$$ is true if $$x$$ is taller than $$y$$.
$$1.$$ Absolute addressing
$$2.$$ Based addressing
$$3.$$ Relative addressing
$$4.$$ Indirect addressing
What is the average turnaround time for these processes with the preemptive shortest remaining processing time first $$(SRTF)$$ algorithm?
i) Context switch is faster with kernel- supported threads
ii) For user-level threads, a system call can block the entire process
iii) Kernel-supported threads can be scheduled independently
iv) Use-level threads are transparent to the kernel
Which of the above statements are true?
char p[20];
char *s = "string";
int length = strlen(s);
for(i=0; i < length; i++)
p[i] = s[length-i];
printf("%s",p);
The output of the program is
void swap (int a, int b)
{
int temp;
temp = a;
a = b;
b = temp;
}
In order to exchange the values of two variables x and y.main ( )
{
int x, y, m, n;
scanf("%d %d", &x, &y);
/* Assume x > 0 and y > 0 */
m=x; n=y;
while(m!=n)
{
if(m>n)
m=m-n;
else
n=n-m;
}
printf("%d", n);
}
The program computesint f(int n)
{
static int i = 1;
if(n>=5) return n;
n = n+1;
i++;
return f(n);
}
The value returned by f(1) isGroup 1
P. Functional
Q. Logic
R. Object-oriented
S. Imperative
Group 2
1. Command-based, procedural
2. Imperative, abstract data types
3. Side-effect free, declaretive, expression Evaluation
4. Declaretive, clausal representation, theorem proving
Which one of the following strings is not a number of $$L(M)?$$
$$\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr & A \to bA\,\left| {\,aB} \right. \cr & B \to bB\,\left| {\,aS\,\left| {\,a} \right.} \right. \cr} $$
Let $${N_a}\left( w \right)$$ and $${N_b}\left( w \right)$$ denote the number of $$a's$$ and $$b's$$ in a string $$w$$ respectively. The language
$$L\left( G \right)\,\,\, \subseteq \left\{ {a,b} \right\} + $$ generated by $$G$$ is