CS/IT Gate Yearwise 



Computer Science Gate 2019 Questions



Ques 1Aptitude

In a college, there are three student clubs, Sixty students are only in the Drama club, 80 students are only in the Dance club, 30 students are only in Maths club, 40 students are in both Drama and Dance clubs, 12 students are in both Dance and Maths clubs, 7 students are in both Drama and Maths clubs, and 2 students are in all clubs. If 75% of the students in the college are not in any of these clubs, then the total number of students in the college is _____________.

a) 1000
b) 975
c) 900
d) 225


c is the correct answer.




Ques 2Aptitude

“A recent High Court judgement has sought to dispel the idea of begging as a disease – which leads to its stigmatization and criminalization – and to regard it as a symptom. The underlying disease is the failure of the state to protect citizens who fall through the social security net.” Which one of the following statements can be inferred from the given passage?

a) Beggars are created because of the lack of social welfare schemes
b) Begging is an offence that has to be dealt with firmly
c) Begging has to be banned because it adversely affects the welfare of the state
d) Beggars are lazy people who beg because they are unwilling to work


b is the correct answer.




Ques 3Aptitude

Ten friends planned to share equally the cost of buying a gifts for their teacher. When two of them decided not to contribute, each of the other friends had to pay Rs. 150 more. The cost of the gift was Rs. _________ .

a) 666
b) 3000
c) 6000
d) 12000


c is the correct answer.




Ques 4Aptitude

Two cars at the same time from the same location and go in the same direction. The speed of the first car is 50 km/h and the speed of the second car is 60 km/h. The number of hours it takes for the distance between the two cars to be 20 km is _________.

a) 1
b) 2
c) 3
d) 6


b is the correct answer.




Ques 5Aptitude

The police arrested four criminals – P, Q, R and S. The criminals knew each other. They made the following statements:

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?

a) P
b) R
c) S
d) Q


b is the correct answer.




Ques 6Aptitude

A court is to a judge as _________ is to a teacher

a) a student
b) a punishment
c) a syllabus
d) a school


d is the correct answer.




Ques 7Aptitude

The search engine’s business model ________ around the fulcrum of trust.

a) revolves
b) plays
c) sinks
d) bursts


English Grammar is the correct answer.




Ques 8Aptitude

The expenditure on the project __________ as follows: equipment Rs.20 lakhs, salaries Rs.12 lakhs, and contingency Rs.3 lakhs.

a) break down
b) break
c) breaks down
d) breaks


c is the correct answer.




Ques 9Automata

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function, i.e. id(j) = j,∀ j. Let ° denote composition on functions. For a string x = x1 x2 ... xn ∈ Σn, n ≥ 0, let π(x) = x1°x2° ... °xn. Consider the language L = {x ∈ Σ* ⏐ π(x) = id}. The minimum number of states in any DFA accepting L is _________ .


120 is the correct answer.




Ques 10Automata

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?

a) S1 and S2
b) S3 and S4
c) S1 and S4
d) S2 and S3


b is the correct answer.




Ques 11Automata

Which one of the following languages over ∑ = {a, b} is NOT context-free?

a) {wwR ⏐ w ∈ {a, b}*}
b) {wwR ⏐ w ∈ {a, b}*}
c) {wanwRbn ⏐ w ∈ {a, b}*, n≥ 0}
d) {anbii⏐ i ∈ {n, 3n, 5n}, n≥ 0}


c is the correct answer.




Ques 12Automata

For Σ = {a, b}, let us consider the regular language

L = {x ∣ x = a2+ 3k or x = b10 + 12k, k ≥ 0}


Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

a) 3
b) 5
c) 9
d) 24


Regular Language is the correct answer.




Ques 13C

Consider the following C program:

#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 above C program is __________


10 is the correct answer.




Ques 14C

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;
        printf("%f ", sum);
    };
    return 0;
}

The number of times variable sum will be printed When the above program is executed is _________ .


a is the correct answer.




Ques 15C

Consider the following C program:

#include<stdio.h>
int main(){
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 5}, *ip = arr + 4;
    printf("%dn", ip[1]);
   return 0;
}


The number that will be displayed on execution of the program is _________ .


a is the correct answer.




Ques 16C

Consider the following C program:

#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 ", x);
    return 0;
}


The value printed by program is __________


a is the correct answer.




Ques 17C

Consider the following C program:

#include<stdio.h>
int r(){
    int static num=7;
    return num--;
}
int main() {
    for(r();r();r()) {
    printf("%d ",r());
};
    return 0;
}
Which one of the following values will be displayed on execution of the programs?

a) 41
b) 52
c) 63
d) 630


b is the correct answer.




Ques 18C

Consider the following C program:

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?

a) It will print the binary representation of n in the reverse order and terminate.
b) It will print the binary representation of n but will not terminate.
c) It will not print anything and will not terminate.
d) It will print the binary representation of n and terminate.


c is the correct answer.




Ques 19COA

Consider Z = X →Y where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:

a) n bits
b) n-1 bits
c) n+1 bits
d) n+2 bits


c is the correct answer.




Ques 20COA

A certain processor uses a fully associative cache of size 16 kB, The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?

a) 24 bits and 0 bits
b) 28 bits and 4 bits
c) 24 bits and 4 bits
d) 28 bits and 0 bits


d is the correct answer.




Ques 21Compiler

Which one of the following kinds of derivation is used by LR parsers?

a) Leftmost
b) Leftmost in reverse
c) Rightmost
d) Rightmost in reverse


d is the correct answer.




Ques 22Compiler

Consider the augmented grammar given below:

S′ → S
S → ⏐id
L → L, S⏐S
Let I0= CLOSURE ({[S′ → S]}).

The number of items in the set GOTO (I0, <) is __________.


5 is the correct answer.




Ques 23Computer Network

Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate up link ports. The minimum number of switches needed is ___________.


3 is the correct answer.




Ques 24Computer Network

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?

a) M, N and P all belong to the same subnet
b) Only N and P belong to the same subnet
c) M, N, and P belong to three different subnets
d) Only M and N belong to the same subnet


b is the correct answer.




Ques 25Computer Network

Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?

a) IMAP POP3
b) SMTP POP3
c) SMTP, MIME
d) IMAP SMTP


Computer Network is the correct answer.




Ques 26DAA

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum ∑jk=iA[k]. Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)


a is the correct answer.




Ques 27DAA

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.


a is the correct answer.




Ques 28DAA

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 ________ .

a) Ο(n)
b) Ο(n2)
c) Ο(n log n)
d) Ω(n2log n)


b is the correct answer.




Ques 29Data Structure

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________ .


4.24 to 4.26 is the correct answer.




Ques 30Data Structure

Consider the following statements:

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 is/are TRUE?

a) I, II and III
b) I, III and IV
c) I, II and IV
d) II, III and IV


a is the correct answer.




Ques 31Data Structure

Let G be any connection, 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 G, there is a unique minimum weight edge crossing the cut.


Which of the above two statements is/are TRUE?

a) I only
b) II only
c) Both I and II
d) Neither I nor II


c is the correct answer.




Ques 32Data Structure

Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

a) B+ Tree is a height-balanced tree.
b) Non-leaf nodes have pointers to data records.
c) Key values in each node are kept in sorted order.
d) Key values in each node are kept in sorted order.


b is the correct answer.




Ques 33Data Structure

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

a) n!
b) (n-1)!
c) 1
d) (n-1)!/2


d is the correct answer.




Ques 34DBMS

Consider the following two statements about database transaction schedules:

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?

a) I only
b) II only
c) Both I and II
d) Neither I nor II


serializability is the correct answer.




Ques 35DBMS

Let the set of functional dependencies 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 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 a lossless.


Which of the above statements is/are correct?

a) Both I and II
b) Neither I nor II
c) I only
d) II only


d is the correct answer.




Ques 36Digital Logic

In 16-bit 2’s complement representation, the decimal number −28 is:

a) 1111 1111 0001 1100
b) 0000 0000 1110 0100
c) 1111 1111 1110 0100
d) 1000 0000 1110 0100


c is the correct answer.




Ques 37Digital Logic

What is the minimum number of 2-input NOR gates required to implement 4-variable function expressed in sum-of-minterms from as f = Σ(0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available. Answer ________


3 is the correct answer.




Ques 38Digital Logic

Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is ___________.


a is the correct answer.




Ques 39Discrete Mathematics

Let G be an arbitrary group. Consider the following relations on G:

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?

a) R1 and R2
b) R1 only
c) R2 only
d) Neither R1 nor R2


b is the correct answer.




Ques 40Discrete Mathematics

Consider the first order predicate formula:
∀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 φ ?

a) S1 and S3
b) S2 and S3
c) S1 and S2
d) S1, S2 and S3


b is the correct answer.




Ques 41Discrete Mathematics

Which one of the following is NOT a valid identity?

a) (x⊕y) ⊕z = x⊕(y ⊕ z)
b) (x + y) ⊕z = x ⊕ (y + z)
c) x ⊕ y = x + y, if xy = 0
d) x ⊕ y = (xy + x′y′)′


b is the correct answer.




Ques 42Mathematics

Let X be a square matrix. Consider the following two statements on X.

I. X is invertible
II. Determinant of X is non-zero


Which one of the following is TRUE?

a) I implies II; II does not imply I
b) II implies I; I does not imply II
c) I does not imply II; II does not imply I
d) I and II are equivalent statements


d is the correct answer.




Ques 43Mathematics

Suppose Y is distributed uniformly in the open interval (1, 6). The probability that the polynomial 3x2 + 6xY + 3Y + 6 has only real roots is (rounded off to 1 decimal place) _________.


0.80 is the correct answer.




Ques 44OS

A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60 MHz clock. To service a cache-miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch all the eight words of the block, and finally transmits the words of the requested block at the rate of 1 word per cycle. The maximum bandwidth for the memory system when the program running on the processor issues a series of read operations is _________ × 106 bytes/sec.


160 is the correct answer.




Ques 45OS

The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointer The disk block size is 4 kB and the disk block addresses 32-bits long. The maximum possible file size is (rounded off to 1 decimal place) __________ GB.


4 is the correct answer.




Ques 46OS

The following C program is executed on a Unix / Linux system:
 

#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 process created is __________


a is the correct answer.




Ques 47OS

Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R arecurrently in use. Further, for all i, process i can place a request for at most Yi additional instances of R while holding the Xt instances it already has. Of the n processes, there are exactly two processes p and q such that Yp = Yq = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?

a) Xp + Xq < Min {Yk ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}
b) Xp + Xq < Min {Yk ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}
c) Min (Xp , Xq ) ≤ Max {Yk ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}
d) Min (Xp , Xq ) ≤ Max {Yk ⏐ 1 ≤ k ≤ n, k ≠ p, k ≠ q}


a is the correct answer.




Ques 48OS

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 8k Band 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?

a) 16 x 210
b) 8 x 220
c) 4 x 220
d) 256 x 210


d is the correct answer.