List of top Questions asked in GATE CS

In the context of schema normalization in relational DBMS, consider a set F of
functional dependencies. The set of all functional dependencies implied by F is
called the closure of F. To compute the closure of F, Armstrong’s Axioms can be
applied. Consider 𝑋, 𝑌, and 𝑍 as sets of attributes over a relational schema. The three
rules of Armstrong’s Axioms are described as follows.
Reflexivity: If 𝑌⊆𝑋 , then 𝑋→𝑌
Augmentation: If 𝑋→𝑌, then 𝑋𝑍→𝑌𝑍 for any Z
Transitivity: If 𝑋→𝑌 and 𝑌→𝑍, then 𝑋→𝑍
The additional rule of Union is defined as follows.
Union: If 𝑋→𝑌 and 𝑋→𝑍, then 𝑋→𝑌𝑍
It can be proved that the additional rule of Union is also implied by the three rules
of Armstrong’s Axioms. Listed below are four combinations of these three rules.
Which one of these combinations is both necessary and sufficient for the proof ?

Consider the canonical 𝐿𝑅(0) parsing of the grammar below using terminals
{𝑎, 𝑏, 𝑐} and non-terminals {𝐴, 𝐵, 𝐶, 𝑆} with 𝑆 as the start symbol.
𝑆→𝐴𝐶𝐵
𝐴→𝑎𝐴 | 𝜖
𝐶→𝑐𝐶 | 𝜖
𝐵→𝑏𝐵 | 𝑏
Which one of the following options gives the number of shift-reduce conflicts that
will occur in the 𝐿𝑅(0) ACTION table?

Consider the following 4-variable Boolean function
𝐹(𝐴, 𝐵, 𝐶, 𝐷) = Σ𝑚(0, 1, 2, 3, 8, 9, 10, 11)
Consider 𝐴 as MSB, 𝐷 as LSB. Which one of the following options represents the
minimal sum of products form for the above function?
Note: + is OR operation, . is AND operation, ′ is NOT operation

Consider an array 𝐴 of integers of size 𝑛. The indices of 𝐴 run from 1 to 𝑛. An
algorithm is to be designed to check whether 𝐴 satisfies the condition given below.
∀𝑖, 𝑗∈{1, … , 𝑛−1} such that 𝑖> 𝑗, (𝐴[𝑖+ 1] −𝐴[𝑖]) > (𝐴[𝑗+ 1] −𝐴[𝑗])
Which one of the following gives the worst case time complexity of the fastest
algorithm that can be designed for the problem?

Let 𝐺 be a weighted directed acyclic graph with 𝑚 edges and 𝑛 vertices. Given 𝐺
and a source vertex 𝑠 in 𝐺, which one of the following options gives the worst case
time complexity of the fastest algorithm to find the lengths of shortest paths from 𝑠
to all vertices that are reachable from 𝑠 in 𝐺?

Consider a complete graph 𝐾𝑛 with 𝑛 vertices (𝑛> 4). Note that multiple spanning
trees can be constructed over 𝐾𝑛. Each of these spanning trees is represented as a
set of edges. The Jaccard coefficient between any two sets is defined as the ratio of
the size of the intersection of the two sets to the size of the union of the two sets.
Which one of the following options gives the lowest possible value for the Jaccard
coefficient between any two spanning trees of 𝐾𝑛 ?

A lexical analyzer uses the following token definitions
 𝑙𝑒𝑡𝑡𝑒𝑟→[𝐴−𝑍𝑎−𝑧]
 𝑑𝑖𝑔𝑖𝑡→[0 −9]
 𝑖𝑑→𝑙𝑒𝑡𝑡𝑒𝑟 (𝑙𝑒𝑡𝑡𝑒𝑟 | 𝑑𝑖𝑔𝑖𝑡)*
 𝑛𝑢𝑚𝑏𝑒𝑟→𝑑𝑖𝑔𝑖𝑡+
 𝑤𝑠→(𝑏𝑙𝑎𝑛𝑘 | 𝑡𝑎𝑏 | 𝑛𝑒𝑤𝑙𝑖𝑛𝑒)+
For the string given below,
𝑥1 23𝑚𝑚 78 𝑦 7𝑧 𝑧𝑧5 14𝐴 8𝐻 𝐴𝑎𝑌𝑐𝐷
the number of tokens (excluding 𝑤𝑠) that will be produced by the lexical analyzer
is __________. (answer in integer)

The 32-bit IEEE 754 single precision representation of a number is 0xC2710000.
The number in decimal representation is ________. (rounded off to two decimal
places)

If an IP network uses a subnet mask of 255.255.240.0, the maximum number of IP
addresses that can be assigned to network interfaces is __________. (answer in
integer)

Consider an array 𝐴= [10, 7, 8, 19, 41, 35, 25, 31]. Suppose the merge sort
algorithm is executed on array 𝐴 to sort it in increasing order. The merge sort
algorithm will carry out a total of 7 merge operations.
A merge operation on sorted left array 𝐿 and sorted right array 𝑅 is said to be void
if the output of the merge operation is the elements of array 𝐿 followed by the
elements of array 𝑅.
The number of void merge operations among these 7 merge operations
is __________. (answer in integer)

Consider the system of linear equations given below.
𝑎𝑥+ 𝑦= 𝑏
16𝑥+ 𝑎𝑦= 24
Suppose the values of a and b are chosen such that the system of linear equations
produce multiple solutions. Then the product of a and b is __________. (answer in
integer)

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the
hash function ℎ(𝑘) = 𝑘 𝑚𝑜𝑑 9. The collisions are resolved by chaining. After all
the keys are inserted, the length of the longest chain is __________. (answer in
integer)

Which of the following grammars is/are ambiguous?

In a system, numbers are represented using 4-bit two’s complement form. Consider
four numbers 𝑁1 =1011, 𝑁2 =1101, 𝑁3 =1010 and 𝑁4 =1001 in the system.
Which of the following operations will result in arithmetic overflow?

For a real number \(a\), let \[I(a)=\int_{-1}^{1}(3x^2-ax+1)\,dx.\]
Which of the following statements is/are true?

Let 𝑅 be a binary relation on the set {1, 2, … , 10}, where (𝑥, 𝑦) ∈𝑅 if the product
of 𝑥 and 𝑦 is square of an integer. Which of the following properties is/are satisfied
by 𝑅?

Consider the functions \(n^{1/3},\ \log_2 n,\ \log_2(n!),\ 2^{\log_2 n}\), where \(n\) is a positive integer.
Which option lists the functions in increasing asymptotic growth order?
Assume that the logarithm has base 2.

Consider a file of size 4 million bytes being transferred between two hosts
connected via a path consisting of three consecutive links of bandwidth 2 Mbps,
500 kbps, and 1 Mbps, respectively. All processing delays and propagation delays
are negligible. Assume that there is no other background traffic over the path and
no other additional overhead to transfer the file.
Which one of the following is the total time (in seconds) to transfer the file?
Note: \(1\mathrm{M}=10^6\), \(1\mathrm{k}=10^3\)

Consider concurrent execution of two transactions 𝑇1 and 𝑇2 in a DBMS, both of
which access a data object 𝐴. For these two transactions to not conflict on 𝐴, which
one of the following statements must be true?

Consider the following three ANSI-C programs, P1, P2, and P3.
P1
P2
P3
#include <stdio.h>
int a=5;
int main(){
int a=7;
return(0);
}
#include <stdio.h>
int main(){
int a=5;
int a=7;
return(0);
}
#include <stdio.h>
int main(){
int a=5;
float a=7;
return(0);
}
Which one of the following statements is true?

In C runtime environment, which one of the following is stored in heap?

Which one of the following options is not a property of Boolean Algebra?
Note: + is OR operation, . is AND operation, and ′ is NOT operation

The probability density function \(f(x)\) of a real-valued random variable \(X\) is
\[f(x)=\frac{1}{3\sqrt{2\pi}}\exp\!\left(-\frac{x^2}{18}\right),\quad x\in(-\infty,+\infty).\]
Which one of the following statements is correct about the random variable X?

Which one of the following statements is equivalent to the following assertion?
Turing machine 𝑀 decides the language 𝐿⊆{0,1}∗

For two different persons 𝑥 and 𝑦, the predicate 𝑀(𝑥, 𝑦) denotes that x knows y.
Consider the following statement.
There is a person who does not know anyone else, but that person is known by
everyone else.
Which one of the following expressions represents the above statement?