GATE CSE
I. The smallest element in a max-heap is always at a leaf node
II. The second largest element in a max-heap is always a child of the root node
III. A max-heap can be constructed from a binary search tree in Θ(n) time
IV. A binary search tree can be constructed from a max-heap in Θ(n) time
Which of the above statements are TRUE?
There are n unsorted arrays : A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, …, An is :
Answer : ________.
S' → S
S → 〈L〉 | id
L → L,S | S
Let I0 = CLOSURE ({[S' → ●S]}). The number of items in the set GOTO (I0 , 〈 ) is: _____.
S → Aa
A → BD
B → b | ε
D → d | ε
Let a, b, d, and $ be indexed as follows:

Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210)
Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let $X_1, X_2, X_3, X_4, X_5$, and $X_6$ be the placeholders for the nonterminals $\mathrm{D}, \mathrm{T}, \mathrm{L}$ or $\mathrm{L}_1$ in the following table :
Production rule | Semantic action |
---|---|
D → T L | X1.type = X2.type |
T → int | T.type = int |
T → float | T.type = float |
L → L1, id |
X3.type = X4.type addType(id.entry, X5.type) |
L → id | addType(id.entry, X6.type) |
Which one of the following are the appropriate choices for $X_1, X_2, X_3$ and $X_4$ ?
Consider three machines M, N, and P with IP addresses 100.10.5.2, 100.10.5.5, and 100.10.5.6 respectively. The subnet mask is set to 255.255 .255 .252 for all the three machines. Which one of the following is true?
Suppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?


How many tuples will be returned by the following relational algebra query?


The primary key of the Student table is Roll_no. For the Performance table, the columns Roll_no. and Subject_code together from the primary key. Consider the SQL query given below:
SELECT S.Student_name, sum (P.Marks)
FROM Student S, Performance P
WHERE P.Marks > 84
GROUP BY S.Student_name;
The number of rows returned by the above SQL query is _________.
F = {QR → S, R → P, S → Q}
hold on a relation schema X = (PQRS). X is not in BCNF. Suppose X is decomposed into two schemas Y and Z, where Y = (PR) and Z = (QRS).
Consider the two statements given below.
I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is dependency preserving and lossless
Which of the above statements is/are correct?
I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas Write Rule can generate view serializable schedules that are not conflict serializable.
Which of the above statements is/are TRUE?
f = Σ(0, 2, 5, 7, 8, 10, 13, 15)?
Assume that all the inputs and their complements are available.
f1 = Σ(0, 2, 5, 8, 14),
f2 = Σ(2, 3, 6, 8, 14, 15),
f3 = Σ(2, 7, 11, 14)
For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as :

I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?
I. |A| = n2n–1
II. |A| = $$\sum\limits_{k = 1}^n {k\left( {\matrix{ n \cr k \cr } } \right)} $$
Which of the above statements is/are TRUE?
∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))]
Here 'a|b' denotes that 'a divides b', where a and b are integers.
Consider the following sets:
S1. {1, 2, 3, ..., 100}
S2. Set of all positive integers
S3. Set of all integers
Which of the above sets satisfy φ?
R1: ∀a,b ∈ G, aR1b if and only if ∃g ∈ G such that a = g-1bg
R2: ∀a,b ∈ G, aR2b if and only if a = b-1
Which of the above is/are equivalence relation/relations?
Let G be any connected, weighted, undirected graph.
I. G has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.
Which of the above two statements is/are TRUE?
Consider the following matrix :
$$ R=\left[\begin{array}{cccc} 1 & 2 & 4 & 8 \\ 1 & 3 & 9 & 27 \\ 1 & 4 & 16 & 64 \\ 1 & 5 & 25 & 125 \end{array}\right] $$
The absolute value of the product of Eigen values of $R$ is ___________.
#include < unistd.h >
int main ()
{
int i ;
for (i=0; i<10; i++)
if (i%2 == 0) fork ( ) ;
return 0 ;
}
The total number of child processes created is _____.
Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is _____.

#include < stdio.h >
int jumble (int x, int y) {
x = 2 * x + y ;
return x ;
}
int main ( ) {
int x=2, y=5 ;
y = jumble (y, x) ;
x = jumble (y, x) ;
printf ("%d \n", x) ;
return 0 ;
}
The value printed by the program is ______.
#include < stdio.h >
int main()
{
int a[] = {2, 4, 6, 8, 10} ;
int i, sum = 0, *b = a + 4 ;
for (i = 0; i < 5; i++)
sum = sum + (*b - i) - *(b - i) ;
printf ("%d\n", sum) ;
return 0 ;
}
The output of the above C program is _________.
#include < stdio.h >
int main () {
int arr [] = {1,2,3,4,5,6,7,8,9,0,1,2,5}, *ip = arr+4;
printf ("%d\n", ip[1]);
return 0;
}
The number that will be displayed on execution of the program is _______.
Consider the following C function.
void convert(int n){
if(n < 0)
printf("%d",n);
else {
convert(n/2);
printf("%d",n%2);
}
}
Which one of the following will happen when the function convert is called with any positive integer n as argument?
Consider the following C program :
#include<stdio.h>
int r()
{
static int num=7;
return num--;
}
int main()
{
for(r();r();r())
printf("%od ",r());
return 0;
}
Which one of the following values will be displayed on execution of the programs?
Consider the following C program :
#include <stdio.h>
int main(){
float sum = 0.0, j = 1.0, i = 2.0;
while (i/j > 0.0625){
j = j + j;
sum = sum + i/j;
printf("%f\n", sum);
}
return 0;
}
The number of times the variable sum will be printed, when the above program is executed, is _________.
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free?
Consider the following sets :
S1. Set of all recursively enumerable languages over the alphabet $\{0,1\}$
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet $\{0,1\}$
S4. Set of all non-regular languages over the alphabet $\{0,1\}$
Which of the above sets are uncountable?
General Aptitude
P says "Q committed the crime."
Q says "S committed the crime."
R says "I did not do it."
S says "What Q said about me is false."
Assume only one of the arrested four committed the crime and only one of the statements made above is true. Who committed the crime?
Which of the following statements can be inferred from the given passage?
Request by X: Due to pollen allergy, I want to avoid a wing next to the garden.
Request by Y: I want to live as far from the washrooms as possible, since I am very sensitive to smell.
Request by Z: I believe in Vaastu and so want to stay in the South-west wing.
The shaded rooms are already occupied. WR is washroom.
