GATE 2021 CS-Set-2

Question 1
Listening to music during exercise improves exercise performance and reduces discomfort. Scientists researched whether listening to music while studying can help students learn better and the results were inconclusive. Students who needed external stimulation for studying fared worse while students who did not need any external stimulation benefited from music. Which one of the following statements is the CORRECT inference of the above passage?
A
Listening to music has no effect on learning and a positive effect on physical exercise.
B
Listening to music has a clear positive effect on physical exercise. Music has a positive effect on learning only in some students.
C
Listening to music has a clear positive effect both on physical exercise and on learning.
D
Listening to music has a clear positive effect on learning in all students. Music has a positive effect only in some students who exercise.
       Aptitude       Verbal
Question 1 Explanation: 

From the first statement “Listening to music during exercise improves exercise performance and reduces discomfort. “ It is clear that listening to music has a positive effect on physical exercise.

From the statement “Scientists researched whether listening to music while studying can help students learn better and the results were inconclusive. “   it is clear that only on some students music has a positive effect.

Question 2

A transparent square sheet shown above is folded along the dotted line. The folded sheet will look like _______.
A
B
C
D
       Aptitude       Non-Verbal
Question 2 Explanation: 
Fold the sheet along the dotted line and join the shapes, we get option 2.
Question 3
Gauri said that she can play the keyboard _______ her sister.
A
as worse as
B
as well as
C
as better as
D
as nicest as
       Aptitude       Verbal
Question 3 Explanation: 
‘worse’, ‘better’ are comparative words which need the word ‘than’ for comparison. Out of the remaining two options ‘as well as’ is the correct answer.
Question 4
Pen : Write :: Knife : _______ Which one of the following options maintains a similar logical relation in the above?
A
Vegetables
B
Sharp
C
Blunt
D
Cut
       Aptitude       Verbal
Question 4 Explanation: 
A pen is used to write. Similarly, a knife is used to cut.
Question 5
The number of students in three classes is in the ratio 3:13:6. If 18 students are added to each class, the ratio changes to 15:35:21. The total number of students in all the three classes in the beginning was:
A
66
B
22
C
88
D
110
       Aptitude       Numerical
Question 5 Explanation: 

Given Initial ratio : 3:13:6

Total number of students initially = 3x+13x+6x = 22x

From the given question, we can write 3x+18 = 15y -----I

                                   13x+18 = 35y-----II

                                   6x+18 = 21y------III

 

                      I - II => -10X = -20Y

                                    X=2Y------IV

 

                      Put IV in III => 6(2y) + 18 = 21y

                                       12y + 18 = 21y

                                       9y = 18

                                        y = 2 -----V

                      Substitute V in I => 3x + 18 = 30

                                           3x = 12

                                           x = 4

   Number of initial students = 22x = 22(4) = 88

Question 6

  The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year 3 was ₹ 1, which was half the cost/unit in Year 2. The cost/unit in Year 3 was one-third of the cost/unit in Year 1. Taxes were paid on the selling price at 10%, 13% and 15% respectively for the three years. Net profit is calculated as the difference between the selling price and the sum of cost and taxes paid in that year.
The ratio of the selling price in Year 2 to the selling price in Year 3 is ______.
A
1:1
B
3:4
C
1:2
D
4:3
       Aptitude       Numerical
Question 6 Explanation: 

 According to the given data:

                        Year     Cost/unit   Number of units     Cost Price

                            1           ₹ 3                    100                     300

                            2           ₹ 2                     200                    400

                            3           ₹ 1                     300                    300

 Cost Price = Cost/unit x Number of units

Net Profit = Selling Price - (Cost Price + (Tax%  x selling price )

Year 2:

   296 = SP - (400 + (13/100) x SP)

   =>296 = 0.87SP - 400

   => 0.87SP = 696

    => SP = ₹ 800

Year 3: 

      210 = SP - (300 + (15/100) x SP)

     => 210 = 0.85SP - 300

    =>  0.85SP = 510

    => SP = ₹ 600

The ratio of selling price in Year 2 to the selling price in year 3 = 800:600 

                                                                                           = 4:3

Question 7

A jigsaw puzzle has 2 pieces. One of the pieces is shown above. Which one of the given options for the missing piece when assembled will form a rectangle? The piece can be moved, rotated or flipped to assemble with the above piece.
A
B
C
D
       Aptitude       Non-Verbal
Question 7 Explanation: 
Rotate 90 degrees to the left and flip the piece in Option 2.
Question 8
A
2
B
4
C
8
D
6
       Aptitude       Numerical
Question 8 Explanation: 

Expand the given equation:

x2+1/4 - x -x2 -9/4 +3x = x+2

   => -2 + 2x = x + 2

                    X = 4

Question 9
If θ is the angle, in degrees, between the longest diagonal of the cube and any one of the edges of the cube, then, cos θ =
A
B
C
D
       Aptitude       Numerical
Question 9 Explanation: 
Question 10
Six students P, Q, R, S, T and U, with distinct heights, compare their heights and make the following observations.
Observation I: S is taller than R.
Observation II: Q is the shortest of all.
Observation III: U is taller than only one student.
Observation IV: T is taller than S but is not the tallest.
The number of students that are taller than R is the same as the number of students shorter than _______.
A
S
B
P
C
T
D
R
       Aptitude       Verbal
Question 10 Explanation: 
The order will be PTSRUQ
Number of students taller than R = Number of students shorter than S = 3
Question 11
Consider the three-way handshake mechanism followed during TCP connection established between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers chosen by P and Q respectively. Suppose P sends a TCP connection request message to Q with a TCP segment having SYN bit = 1, SEQ number = X, and ACK bit = 0. Suppose Q accepts the connection request. Which one of the following choices represents the information present in the TCP segment header that is sent by Q to P?
A
SYN bit = 1, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 0
B
SYN bit = 0, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 1
C
SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X+1, FIN bit = 0
D
SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X, FIN bit = 0
       Computer-Networks       Sliding-Window-Protocol
Question 11 Explanation: 

 

Q will send the SYN bit = 1 to the connection establishment.

Q Seq number will be Y different from X

ACK bit = 1 because sending the ACK

ACK number = X+1 (Next seq number id)

FIN bit = 0 (Because establishing the connection) 

Question 12
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∊ is divisible by three.
A
(0+1 (01*0)*1)*
B
(0+11+10(1+00)*01)*
C
(0*(1(01*0)*1)*)*
D
(0+11+11(1+00)*00)*
       Theory-of-Computation       Regular-Expression
Question 12 Explanation: 

Transition table

 

 

0

1

->*q0

q0

q1

q1

q2

q0

q2

q1

q2

 

DFA of divisible by 3

The regular expression will be

Three paths to reach to final state from initial state

Path 1: self loop of 0 on q0

Path 2: q0->q1->q0  hence 11

Path 3: q0->q1->q2->q1->q0 hence 10(1+00)*01

So finally the regular expression will be

(0+11+10(1+00)*01)*



Other regular expression is (if we consider two paths)

Path 1: Path 1: self loop of 0 on q0

Path 2: q0->q1->q2*->q1->q0 

Hence regular expression

(0+1 (01*0)*1)*

 

Another regular expression is (if we consider only one path and remaining part is present inside this path as cycles)

q0->q1->q2->q1->q0

Another regular expression is

(0*(1(01*0)*1)*)*

 

So A,B, C are correct.

Option D generates string 11100 which is not accepted by FA hence wrong.

Question 13
 For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR= 10110. Which of the following languages is/are context-free?
A
L={w x wR xR | w, x ∈ {0,1}* }
B
L={w wR x xR | w, x ∈ {0,1}* }
C
L={w x xR wR | w, x ∈ {0,1}* }
D
L={w x wR | w, x ∈ {0,1}* }
       Theory-of-Computation       Context-Free-Language
Question 13 Explanation: 

Option A: L={w x wR  xR  | w, x ∈ {0,1}* }

This is not CFL as if we push “w” then “x” then we cannot match wR with “w” as top of stack contains x.

 

Option B: L={w wR x xR  | w, x ∈ {0,1}* }

This is CFL. We non deterministically guess the middle of the string. So we push “w” then match with wR  and again push x and match with xR  

 

Option C: L={w x  xR wR   | w, x ∈ {0,1}* } 

This is also CFL. We non deterministically guess the middle of the string. So we push “w” then push x and then  match with xR  and again match with wR 

 

Option D: L={w x  wR   | w, x ∈ {0,1}* }

This is a regular language (hence CFL). In this language every string start and end with same symbol (as x can expand).



Question 14
For a statement S in a program, in the context of liveness analysis, the following sets are defined: USE(S) : the set of variables used in S IN(S)     : the set of variables that are live at the entry of S OUT(S)  : the set of variables that are live at the exit of S Consider a basic block that consists of two statements, S1followed by S2. Which one of the following statements is correct?
A
OUT(S1) =IN(S2) U OUT(S2)
B
OUT(S1) =IN(S1) U USE(S1)
C
OUT(S1) =USE(S1) U IN(S2)
D
OUT(S1) =IN(S2)
       Compiler-Design       liveness-analysis
Question 14 Explanation: 
As we know the formula for In and OUT are
Question 15
A data consisting of 1,50,000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is sorted on the primary key RollNo. The size of a record pointer for this disk is 7 bytes. Each student-record has a candidate key attribute called ANum of size 12 bytes. Suppose an index file with records consisting of two fields, ANum value and the record pointer to the corresponding student record, is built and stored on the same disk. Assume that the records of data file and index file are not split across disk blocks. The number of blocks in the index file is ______.
A
698
       Database-Management-System       Indexing
Question 15 Explanation: 

Total no. of records = 150000

Block size = 4096 bytes

Key size = 12 bytes

Record pointer size = 7 bytes


Question 16
Consider the following ANSI C program.
#include <stdio.h>
int foo(intx, int y, int q)
{
         if ((x <= 0) && (y <= 0))
              return q;
         if (x <= 0)
              return foo(x, y-q, q);
         if (y <= 0)
              return foo(x-q, y, q);
         return foo(x, y-q, q) + foo(x-q, y, q);
}
int main()
{
         int r = foo(15, 15, 10);
         printf(“%d”, r);
         return 0;
}
The output of the program upon execution is ______
A
60
       Programming       Recursion
Question 16 Explanation: 

int foo(intx, int y, int q)

{

         if ((x <= 0) && (y <= 0))  //if 1

              return q;

         if (x <= 0)                      //if 2

              return foo(x, y-q, q);

         if (y <= 0)                     //if 3

              return foo(x-q, y, q);

         return foo(x, y-q, q) + foo(x-q, y, q);

}

int main()

{

         int r = foo(15, 15, 10);

         printf(“%d”, r);

         return 0;

}


Question 17
Consider the following directed graph:

Which of the following is/are correct about the graph?
A
For each pair of vertices u and v, there is a directed path from u to v.
B
The graph does not have a strongly connected component.
C
The graph does not have a topological order.
D
A depth-first traversal staring at vertex S classifies three directed edges as back edges.
       Data-Structures       Graphs-and-Tree
Question 17 Explanation: 

Option-1: FALSE: There is no path from  top right corner vertex to any other vertex

Option-2: FALSE: A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. As there is no path from the above vertex then this statement is wrong. 

Option-3: TRUE: This graph does have directed cycles, thus topological order can not be  possible for according to topological definition. 

Question 18
The format of the single-precision floating-point representation of a real number as per the IEEE 754 standard is as follows:   Which one of the following choices is correct with respect to the smallest normalized positive number represented using the standard?
A
exponent = 00000001 and mantissa = 00000000000000000000001
B
exponent = 00000001 and mantissa = 00000000000000000000000
C
exponent = 00000000 and mantissa = 00000000000000000000000
D
exponent = 00000000 and mantissa = 00000000000000000000001
       Digital-Logic-Design       Number-Systems
Question 18 Explanation: 

The smallest biased exponent for the normalized number is E= 1.

The smallest Mantissa M = 000...0

The smallest positive normalized number = 1.M x 2 E-127

= 1.0 x 2 -126 .

= 2 -126

Question 19
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
A
B
C
D
       Algorithms       Time-Complexity
Question 19 Explanation: 

In this question they given three main constraints

  1. The input array is in sorted order
  2. Use recursive binary search
  3. Worst case number of operations

If the array is in sorted order then the worst case time complexity is O(logn)

Ex: 10, 20, 30

The binary search approach is using either recursive or iterative method is

Step-1: element = middle, the element is found and return the index.

Step-2: element > middle, search for the element in the sub-array starting from middle+1 index to n.

Step-3: element < middle, search for element in the sub-array starting from 0 index to middle -1.

Note: The worst case happens when we want to find the smallest/largest farthest node. So, it will not take more than O(logn) time. 

Question 20
Which one of the following circuits implements the Boolean function given below?
A
B
C
D
       Digital-Logic-Design       Combinational-Circuit
Question 20 Explanation: 
Question 21
Let S be the following schedule of operations of three transactions T1, T2 and T3in a relational database system:
  R2(Y), R1(X), R3(Z), R1(Y), W1(X), R2(Z), W2(Y), R3(X), W3(Z)
Consider the statements P and Q below:
P: S is conflict-serializable.
Q: If T3commits before T1finishes, then S is recoverable.
Which one of the following choices is correct? 
A
P is true and Q is false.
B
Both P and Q are false.
C
Both P and Q are true.
D
P is false and Q is true.
       Database-Management-System       Transactions
Question 21 Explanation: 
Question 22
 Consider a set-associative cache of size 2KB (1KB = 210bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used for accessing the cache. If the width of the tag field is 22 bits, the associativity of the cache is ______
A
2
       Computer-Organization       Cache
Question 22 Explanation: 

Cache size = 2KB

Block size = 64 Bytes = 2^6 bytes. So the OFFSET is 6 bits long.

The TAG field is 22 bits. And the physical address is 32 bits.

Since it is given as a set associative cache, the physical address is divided as (TAG, SET, OFFSET).

 

From the given information we can find the SET number = 32 - 22 - 6 = 4 bits.

Using the 4 SET bits, the number of sets possible = 2^4 = 16.

 

Number of blocks in the cache = Cache size / Block size = 2KB /  64 = 2^11/2^6 = 2^5.

 

Number of sets in the cache = Number of blocks in the cache / Number of blocks in each set

 

Number of blocks in each set is also called the associativity.

 

16 = 2^5/associativity

Associativity = 2^5/16 = 2

Question 23
For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:

Which one of the following options is correct about the recurrence T(n)?
A
B
C
D
       Algorithms       Recurrences
Question 23 Explanation: 
Question 24
A
19
       Engineering-Mathematics       Relations-and-Functions
Question 24 Explanation: 
Question 25
Consider the following ANSI C code segment:
z = x + 3 + y -> f1 + y -> f2;
for (i = 0; i < 200; i = i+2)  {
      if (z > i)  {
             p = p + x + 3;
             q = q + y -> f1;
      }  else  {
             p = p + y -> f2;
             q = q + x + 3;
      }
  }    
Assume that the variable y points to a struct (allocated on the head) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common subexpression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y->f1 or y->f2) in the optimized code, respectively, are:
A
303 and 2
B
303 and 102
C
403 and 102
D
203 and 2
       Compiler-Design       Code-Optimization
Question 25 Explanation: 

 In compiler theory, common subexpression elimination is a compiler optimization that searches for instances for identical expressions (i.e, they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.

For example: Consider the following block of code

a=x+y+z;  

r=p+q; 

b=x+y+r; 

The code after common subexpression elimination.

t=x+y;

a=t+z;  

r=p+q; 

b=t+r; 

In the given code

z = x + 3 + y -> f1 + y -> f2;

for (i = 0; i < 200; i = i+2)  {

      if (z > i)  {

             p = p + x + 3;

             q = q + y -> f1;

      }  else  {

             p = p + y -> f2;

             q = q + x + 3;

      }

  }    

 

X+3 is common subexpression, also  y -> f1 & y -> f2  is found in first line itself so they are also like common subexpression.

Hence the code after common subexpression

t1=x+3; t2=y -> f1 ; t3= y -> f2; 

z = t1 + t2 + t3;

for (i = 0; i < 200; i = i+2)  {

      if (z > i)  {

             p = p + t1;

             q = q + t2;

      }  else  {

             p = p + t3;

             q = q + t1;

      }

  }    

Hence two dereference operations (of the form y->f1 or y->f2) in the optimized code.

The number of addition in the optimized code are:

Loop will execute for 100 times and in loop one addition (i+2)

So 100 additions.

Inside loop we have two additions (either in if block or in else block) so 200 additions inside loop

Hence 300 additions in loop (loop body as well as inside)

First 2 lines contains 3 additions

t1=x+3; 

z = t1 + t2 + t3;

Hence total 303 additions.

So 303 and 2 are the answer.

Question 26
 Consider a computer system with DMA support, The DMA module is transferring one 8-bit character in one CPU cycle from a device to memory through cycle stealing at regular intervals. Consider a 2 MHz processor. If 0.5% processor cycles are used for DMA, the data transfer rate of the device is ______ bits per second.
A
80,000
       Computer-Organization       DMA
Question 26 Explanation: 
Question 27
Consider the following ANSI C program
#include<stdio.h>
int main() {
    int arr[4][5];
    int i, j;
    for (i=0; i<4; i++){
        for (j=0; j<5; j++){
              arr[i][j] = 10*i + j;
            }
          }
          printf (“%d”, *(arr[1] + 9));
          return 0;
}
What is the output of the above program?
A
14
B
30
C
24
D
20
       Programming       Pointers
Question 27 Explanation: 
arr[4][5]
Question 28
Consider the following ANSI C function:
int SomeFunction (int x, int y)
{
    if ((x == 1) || (y == 1)) return 1;
    if (x == y) return x;
    if (x > y) return SomeFunction (x-y, y);
    if (y > x) return SomeFunction (x, y-x);
}
The value returned by SomeFunction (15, 255) is _______.
A
15
       Programming       Recursion
Question 28 Explanation: 
Question 29
 For two n-dimensional real vectors P and Q, the operation s(P, Q) is defined as follows:
A
10
B
11
C
9
D
100
       Engineering-Mathematics       Vectors
Question 29 Explanation: 

s(P,Q) is the sum of dot products of vectors P and Q in each dimension.  The 0 dot product indicates that the vectors must be orthogonal to each other. 
In a n-dimensional space, we have n axes  orthogonal to each other.  It is given that for every pair the dot product must be 0, then at most n vectors each mentioning each dimension can be considered.  Thus for 10 dimensional space’s set of vectors ℒ , 10 mutually orthogonal vectors can be present. 

Question 30
Consider the following statements S1 and S2 about the relational data model: S1: A relation scheme can have at most one foreign key. S2: A foreign key in a relation schema R cannot be used to refer to tuples of R. Which one of the following choices is correct?  
A
S1 is false and S2 is true.
B
Both S1 and S2 are false.
C
Both S1 and S2 are true.
D
S1 is true and S2 is false.
       Database-Management-System       Keys
Question 30 Explanation: 
  • A database table may have more than one foreign key, and each foreign key can have a different parent table. Hence, the statement I is incorrect.
  • A foreign key is a set of attributes in a table that refers to the primary key of another table or to the primary key of the same table (self-referential table). Hence, the statement II is also incorrect.
Question 31
A bag has r red balls and b black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and the ball is placed back into the bag along with another ball of the same colour. Note that the number of balls in the bag will increase by one, after the trial. A sequence of four such trials is conducted. Which one of the following choices gives the probability of drawing a red ball in the fourth trial?
A
B
C
D
       Engineering-Mathematics       Probability-and-statistics
Question 31 Explanation: 
  • There are 8 ways to get ‘red’ in the fourth attempt of drawing 

    i.e., _ _ _ R these three gaps can be filled with B/R in 222=8 ways

    The probability for case (1),


Question 32
  • Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the following choices is correct.?
A
Only S2is true.
B
Both S1and S2are true.
C
Only S1is true.
D
Neither S1nor S2is true.
       Theory-of-Computation       Regular-Language
Question 32 Explanation: 
  • S1 is true. We can solve this intuitively.

    Suppose L=(a+b)*  i.e, sigma* 

    We know that this is a regular language and any language is subset of this language.

     

    As we know so many undecidable languages (not recursive languages) exist, hence S1 is true.

    Take another example:

     

    L=a* which is regular and infinite.

    Take its subset L1=an | n> 0 and n is a set such that it cannot be generated by any algorithm

     

    I.e, n is a set of natural numbers which does not have any algorithm which can generate this

     

    So  L1 is a undecidable language.

     

    L2 is true as every finite language is regular.

Question 33
 In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?
A
Three address code
B
Abstract Syntax Tree (AST)
C
Symbol table
D
Control Flow Graph (CFG)
       Compiler-Design       Intermediate-code-generator
Question 33 Explanation: 
  • An intermediate representation is a representation of a program “between” the source and target languages. A good IR is one that is fairly independent of the source and target languages, so that it maximizes its ability to be used in a retargetable compiler.

    Types of intermediate representation:

    1. Structured (Tree such as abstract syntax tree or Graph such as CFG, single static assignment)
    2.  tuple-based, generally three-address code (quadruples)

     

    Symbol table is not an intermediate representation of a source program. Symbol table is created in the first phase (lexical analysis phase and subsequently updated in later phases) and it stores the information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc.

     

    Abstract syntax tree and three address code are well known representations of intermediate code.

    CFG i.e., control flow graph is also a representation of intermediate code which represents the flow of control of the program. In CFG we break sequences of three address codes into basic blocks hence CFG is also a representation of intermediate code as it contains three address codes along with control flow representation with help of blocks and edges (arrows).

Question 34
If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(s) the unsigned integer on a little endian computer?
A
0x4243
B
0x6665
C
0x0001
D
0x0100
       Digital-Logic-Design       Number-Systems
Question 34 Explanation: 

It is given that the unsigned integer is 2-bytes long. It needs 4 hexadecimal digits.

We know the big-endian and little-endian computers differ in how the data is stored in memory.

 

In little endian machines, the last byte of binary representation of the multibyte data-type is stored first. On the other hand, in big endian machines, the first byte of binary representation of the multibyte data-type is stored first.

 

In the hexadecimal representation of the 2-byte number on the little endian machine, the first two hexadecimal digits are for one byte and the last two hexadecimal digits are for the second byte. On the big endian machine it is the other way round. 

 

It is given that the value in little endian representation is 255 more than the value in the big endian machine.

 

From the given options 

A). In little endian = 0x4243 in binary (0100 0010 0100 0011) which has decimal value = 16963

On big endian = 0x4342 in binary (0100 0011 0100 0010) which has decimal value = 17218 

Here the big endian value is higher than the little endian value. So this is not the correct option.

 

B). In little endian 0x6665 in binary (0110 0110 0110 0101) which has the decimal value = 26213

In big endian 0x6566 in binary (0110 0101 0110 0110) which has the decimal value = 25958

The difference = 26213 - 25958 = 255. So this is also the correct option. 

 

C). In little endian 0x0001 in binary (0000 0000 0000 0001) which has the decimal value = 1.

In big endian 0x0100 in binary (0000 0001 0000 0000) has decimal value = 256.

But here also the big endian value is higher than the little endian. So this is not the correct option.

 

D). On the little endian machine for hexadecimal number 0x0100 in binary (0000 0001 0000 0000) which has decimal value = 256. On a big endian machine it is 0x 0001 in binary  (0000 0000 0000 0001) which has decimal value = 1

 

The difference in value of little endian to big endian is 256-1 = 255.

 

Hence 2, 4 are the correct options.

Question 35
 Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is _________.
A
59049
       Engineering-Mathematics       Set-Theory
Question 35 Explanation: 
Question 36
 Let L ⊆ {0, 1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?
A
L U {01}
B
L.L
C
{0,1}*-L
D
L-{01}
       Theory-of-Computation       DFA
Question 36 Explanation: 
Explanation:If L has a DFA with the number of states k then complement of L will also have a DFA with k states. Hence {0,1}* -L i.e, the complement of L will have k states DFA also.
Question 37
Consider a pipelined processor with 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Each stage of the pipeline, except the EX stage, takes one cycle. Assume that the ID stage merely decodes the instruction and the register read is performed in the EX stage. The EX stage takes one cycle for ADD instruction and two cycles for MUL instruction.
Consider the following sequence of 8 instructions:
              ADD, MUL, ADD, MUL, ADD, MUL, ADD, MUL
Assume that every MUL instruction is data-dependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data- dependent on the MUL instruction just before it. The Speedup is defined as follows:
Assume that every MUL instruction is data-dependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data-dependent on the MUL instruction just before it. The Speedup is defined as follows:

The Speedup achieved in executing the given instruction sequence on the pipelined processor (rounded to 2 decimal places) is ________.
A
1.875
       Computer-Organization       Pipelining
Question 37 Explanation: 

Question 38
Consider the following deterministic finite automaton (DFA).

The number of strings of length 8 accepted by the above automaton is __________.
A
256
       Theory-of-Computation       DFA
Question 38 Explanation: 
State q3 and q4 are equivalent so they can be merged and states q1 and q2 are also equivalent so they can also be merged hence the min DFA will be

So the DFA accepts all strings of length greater than equal to 3.

 

For 8 length strings we have 8 positions

 

_ _ _ _ _ _ _ _

 

For each position there are two possibilities 0 or 1.

So for 8 positions we have 28 possibilities = 256

Question 39
Consider a Boolean function f(w, x, y, z) such that
               f(w, 0, 0, z) = 1
               f(1, x, 1, z) = x + z
               f(w, 1, y, z) = wz + y
The number of literals in the minimal sum-of-products expression of f is __________.
A
6
       Digital-Logic-Design       Boolean-Function
Question 39 Explanation: 

f(w,0,0,z)= 1 If x=y=0, then the sum of the corresponding minterms be 1. 

The minterms with literals x’ and y’ are wx’y’z(9), w’x’y’z(1), wx’y’z’(8), w’x’y’z’(0) . 

If x=y=0, then we get wz+w’z+wz’+w’z’ = 1. 

f(1,x,1,z)= x+z. 

The minterms with variables w and y in true form and x or z or both in true form. 

The corresponding minterms are wx’yz(11), wxyz’(14), wxyz(15) 

If w=1 and y=1, then we get x’z+xz’+xz= x+z. 

f(w,1,y,z)= wz+y

The corresponding minterms are w’xyz’(6), w’xyz(7), wxyz’(14), wxyz(15), wxy’z(13).

If x=1, then we get w’yz’ + w’yz+ wyz’ + wyz+ wy’z = y + wz

So, the function f(w,x,y,z)= Σ(0,1,6,7, 8,9, 11, 13, 14, 15,).

Therefore, the k-map will be:

Therefore, the minimal expression will be: X’Y’ + WZ + XY 

Thus, the number of literals will be 6.

Question 40
Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock (L). The following scheme is used to own a resource instance:
function OWNRESOURCE(Resource R)
      Acquire lock L  //  a global lock
      if R is available then
               Acquire R
               Release lock L
        else
                if R is owned by another process P then
                      Terminate P, after releasing all resources owned by P
                      Acquire R
                      Restart P
                      Release lock L
                 end if 
         end if
  end function
Which of the following choice(s) about the above scheme is/are correct?
A
The scheme ensures that deadlocks will not occur.
B
The scheme may lead to live-lock.
C
The scheme violates the mutual exclusive property.
D
The scheme may lead to starvation.
       Operating-Systems       Deadlock
Question 40 Explanation: 

(1) True, 

The scheme ensures deadlock free operation, as there is no hold-and-wait condition possible. 

 

(2) True, 

The scheme may lead to priority inversion problems, and hence livelock is possible. 

 

(3) False, 

Mutual exclusion is satisfied as only one process can acquire and release locks at a time.  

 

(4) True,

The scheme may lead to starvation. For example, the priority process can get scheduled repeatedly and keeps on killing the lower priority processes. Hence, a low priority process may strave.

Question 41
. Suppose that P is a 45matrix such that every solution of the equation Px=0 is a scalar multiple of [2  5  4  3  1]T. The rank of P is _________.
A
4
       Engineering-Mathematics       Linear-Algebra
Question 41 Explanation: 
If the rank of a homogeneous system is less than the number of variables in the system, then the system has infinitely many solutions. r
Question 42
In an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted.
  • If the first question is answered wrong, the student gets zero marks.
  • If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question.  
  • If both the questions are answered correctly, the student gets the sum of the marks of the two questions.
The following table shows the probability of correctly answering a question and the marks of the question respectively.
question Probability of answering correctly marks
QuesA QuesB 0.8 0.5 10 20
Assuming that the student always wants to maximize her expected marks in the examination, in which order should she attempt the questions and what is the expected marks for that order (assume that the questions are independent)?
A
First QuesB and then QuesA. Expected marks 22.
B
First QuesA and then QuesB. Expected marks 16.
C
First QuesA and then QuesB. Expected marks 14.
D
First QuesB and then QuesA. Expected marks 14.
       Engineering-Mathematics       Probability-and-statistics
Question 42 Explanation: 

There are two ways to get marks.
1. Answering first question correctly, and second one wrongly
2. Answering first question and second question correctly.

There are two ways to answer the question paper. First A or First B.
In total we get 4 ways of answering the paper to get marks. 

Note: Answering each question is independent, thus P(x intersection y) = P(x)*P(y)|
P(Answering A correctly) =0.8, P( Answering A wrongly) = 1-0.8=0.2
P(Answering B correctly) =0.5, P( Answering B wrongly) = 1-0.5=0.5



 

Probability of Getting marks 

Marks 

First A correctly, B wrongly

P(A correctly)*P(B wrongly)
= 0.8*0.5 = 0.4

10+0 = 10

First A correctly B correctly

P(A correctly)*P(B Correctly)
= 0.8*0.5 = 0.4

10+20 = 30

First B correctly, A wrongly

P(B correctly)*P(A wrongly)
= 0.5*0.2 = 0.1

20+0=20

First B correctly then A correctly

P(B correctly)*P(A Correctly)
=0.5*0.8 = 0.4

20+10=30

 

Expectation formula
                                   

                                         E(X)=∑X*P(X)

 

   Expectation for the order:A followed by B = 0.4*10 +0.4*30 = 16
Expectation for the order B followed by A = 0.1*20 + 0.4*30 = 14

 

As the target is to get maximum marks, the order A followed by B is the correct option

Question 43
The relation scheme given below is used to store information about the employees of a company, where empId is the key and deptId indicates the department to which the employee is assigned. Each employee is assigned to exactly one department.
              emp(empId, name, gender, salary, deptId)
Consider the following SQL query:
              select deptId, count (*)
              from emp
              where gender = “female” and salary > (select avg(salary) from emp)
              group by deptId;
The above query gives, for each department in the company, the number of female employees whose salary is greater than the average salary of
A
employees in the department
B
female employees in the company
C
employees in the company
D
female employees in the department
       Database-Management-System       Nested-Query
Question 43 Explanation: 

The given SQL query is:

Select deptId, count(*)

from emp

where gender = “female” and 

group by deptId

  • The inner query will return the average salary of the emp table.
  • Hence, the given query will return the deptId wise count of female employees whose salary is greater than the average salary of the emp table.
Question 44
Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial X3+X+1. Suppose the message m4m3m2m1m0=11000 is to be transmitted. Check bits c2c1c0are appended at the end of the message by the transmitter using the above CRC scheme. The transmitted bit string is denoted by m4m3m2m1m0c2c1c0. The value of the checkbit sequence c2c1c0is
A
111
B
100
C
101
D
110
       Computer-Networks       CRC
Question 44 Explanation: 
Question 45
Consider the following augmented grammar with {#, @, <, >, a, B, c} as the set of terminals.
S’ ⟶ S
S ⟶ S#cS
S ⟶ SS
S ⟶ S@
S ⟶ < S >
S ⟶ a
S ⟶ b
S ⟶ c  
Let I0=CLOSURE({S' ⟶.S}). The number of items in the set GOTO(GOTO(I0, <), <) is ____________.
A
8
       Compiler-Design       Parsers
Question 45 Explanation: 
Question 46
Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements.
S1:Read misses in a write through L1 cache do not result in writebacks of dirty lines to the L2.
S2:Write allocate policy must be used in conjunction with write through caches and no-write allocate policy is used with write back caches.
A
S1is true and S2is false
B
S1is false and S2is false
C
S1is true and S2is true
D
S1is false and S2is true
       Computer-Organization       Cache
Question 46 Explanation: 

S1: In a write through cache the writing happens to both the L1 and L2 caches simultaneously.  It is also given as the inclusive hierarchy. Here L1 is a subset of L2. So when there is a cache read miss in L1 we try to fetch the content from L2. If the block containing that missed word is dirty in the L1 cache,  since it is a write through cache the same content would have also been written to the L2 cache also earlier itself. So there is no need to write back the dirty lines again to the L2 cache on a cache miss. Hence S1 is true.

 

S2:  Generally no-write allocate is used with write through cache and write allocate is used with write back cache. Hence S2 is false.

Question 47
Consider the following multi-threaded code segment (in a mix of C and pseudocode), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2:
int x=0;    // global
Lock L1;    // global
main()  {
     create a thread to execute foo();     // Thread T1 
     create a thread to execute foo();     // Thread T2
     wait for the two threads to finish execution;
     print (x); }
     foo() {
        int y=0;
        Acquire L1;
        x = x + 1;
        y = y + 1;
        Release L1;
        print (y);}  
Which of the following statement(s) is/are correct?
A
At least one of P1 and P2 will print the value of x as 4.
B
Both T1 and t2, in both the processes, will print the value of y as 1.
C
Both P1 and P2 will print the value of x as2.
D
At least one of the threads will print the value of y as 2.
       Operating-Systems       Threads
Question 47 Explanation: 
  1. True,

Execution order : P1->T1->T2; P2->T1->T2; P1-print(x),P2-print(x) | output is 4,4

 

  1. True, 

y=y+1 can be treated as a critical section, and it is well synchronized by Acquire L1 and release L1. 

  1. False, need not be true always. 
  2. False,

Threads maintain their own copy of stack,and local variables (y) are stored on the stack. 



Question 48
Choose the correct choice(s) regarding the following propositional logic assertion S:
A
S is a contradiction.
B
The anecdote of S is logically equivalent to the consequent of S.
C
S is a tautology.
D
S is neither a tautology nor a contradiction.
       Engineering-Mathematics       Propositional-Logic
Question 48 Explanation: 
Question 49
Let L1be a regular language and L2be a context-free language. Which of the following languages is/are context free
A
B
C
D
       Theory-of-Computation       Context-Free-Language
Question 49 Explanation: 
Question 50
 Suppose the following functional dependencies hold on a relation U with attributes P, Q, R, S, and T:
                  P⟶ QR
                  RS⟶ T 
Which of the following functional dependencies can be inferred from the above functional dependencies?
A
PS ⟶ Q
B
PS ⟶ T
C
R ⟶ T
D
P ⟶ R
       Database-Management-System       Functional-Dependency
Question 50 Explanation: 
Question 51
Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weighted edge in G which is present in every minimum spanning tree of G.
S2:If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which of the following options is correct?
A
S1is false and S2is true.
B
S1is true and S2is false.
C
Both S1 and S2are false.
D
Both S1 and S2are true.
       Algorithms       Minimum-Spanning-Tree
Question 51 Explanation: 

Statement-1: FALSE: The given statement is not valid for all the cases because they are not mentioned, edge weights are in distinct or duplicate. So, we can take any random edge weights for the given statement. 

Example:


Statement-2: TRUE: Using the kruskal’s (or) prim's algorithm we get a unique MST when there is a unique edge weight. 

Example:


Based on the above graph, we get the MST is
Question 52
Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below.   The objective is to find the shortest-cost path from the router R to routers P and Q. Assume that R does not initially know the shortest routes to P and Q. Assume that R has three neighbouring routers denoted as X, Y and Z. During one iteration, R measures its distance to its neighbours X, Y and Z as 3, 2 and 5, respectively. Router R gets routing vectors from its neighbours that indicate that the distance to router P from routers X, Y and Z are 7, 6 and 5, respectively. The routing vector also indicates that the distanceto router Q from routers X, Y and Z are 4, 6 and 8, respectively. Which of the following statement(s) is/are correct with respect to the new routing table of R, after updation during this iteration
A
The next hop router for a packet from R to P is Y.
B
The distance from R to Q will be stored as 7.
C
The next hop router for a packet from R to Q is Z.
D
The distance from R to P will be stored as 10.
       Computer-Networks       Routing
Question 52 Explanation: 

Given R gets the distance vector (3,2,5)

After the one iteration distance vector from X to P, Y to P,  and Z to P is (7, 6, 5) respectively

The distance vector from R to P via X Y Z is (3+7, 2+6, 5+5) =(10, 8, 10)

So Take minimum distance from R to P which is 8 via Y

After the iteration distance vector from X to Q, Y to Q, Z to Q is ( 4, 6, 8) respectively

The distance vector from R to Q via X Y Z is (3+4, 2+6, 5+8) = (7, 8 13)

So Take minimum distance from R to Q  which is 7 via X.



Question 53
Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below.

The page size is 4KB (1KB = 210bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2GB (1GB = 230bytes) virtual memory which is mapped to 2GB of physical memory. The minimum amount of memory required for the page table of P across all levels is ________ KB.
A
8.01
       Operating-Systems       Paging
Question 53 Explanation: 

A system can support upto 2^39 bytes of Virtual address space. Three level paging is used with Level 1 (9 bits), Level 2 (9 bits) and Level 3 (9 bits) and page offset of 12 bits. 

Page table entry is 8 bytes at every level. Therefore, 

 

Level 3 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)

Level 2 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame)

Level 1 page table size : 2^9 * 8bytes = 2^12 bytes. (Fits in one frame).

 

However, the process P has a virtual address space of 2^31 bytes. Thus, it is clear that the last level page table does not occupy the frame completely. Let x be the number of bits indexed in the last level. 

Therefore, we can  have (2^x) * (2^9) * (2^9)* (2^12) = 2^31 => x =1. Thus, the minimum size of page table for process P would be,

Page table size at level-1 + Page table size at level-2 + Page table size at level-3 = 

2^1 * 8bytes +  2^9 * 8bytes +  2^9 * 8bytes = (1026)*8 bytes = 8.01 KB 



Question 54
Which of the following statement(s) is/are correct in the context of CPU scheduling?
A
Implementing preemptive scheduling needed hardware support.
B
Turnaround time includes waiting time
C
Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori.
D
The goal is to only maximize CPU utilization and minimize throughput.
       Operating-Systems       CPU-Scheduling
Question 54 Explanation: 
  1. True. Preemptive scheduling needs hardware support such as a timer
  2. True. Turnaround time = Burst time + Waiting time 
  3. True, RR assigns qunatume to each process equally. Hence, it is not required to know burst size apriori
  4. False. Maximize CPU utilization and throughput, and minimize waiting time etc. 
Question 55
 In a directed acyclic graph with a source vertex s, the quality-score of s directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all the vertices in the graph shown above is _________.
A
929
       Algorithms       Minimum-Spanning-Tree
Question 56
Consider a network using the pure ALOHA medium access control protocol, where each frame is of length 1,000 bits. The channel transmission rate is 1 Mbps (= 106bits per second). The aggregate number of transmissions across all the nodes (including new frame transmissions and retransmitted frames due to collisions) is modelled as a Poisson process with a rate of 1,000 frames per second. Throughput is defined as the average number of frames successfully transmitted per second. The throughput of the network (rounded to the nearest integer) is _________. 
A
135
       Computer-Networks       Sliding-Window-Protocol
Question 56 Explanation: 

1 frames takes = Tt = L / B.w. => 1000 / 10^6 = 1 millisec

1000 frame Tt = 1000 x 1 millisec = 1 sec

In 1 sec, 1000 frames sends, which is 1 millisec per frame.

So, G = 1

 

Efficiency of Pure Aloha (η) = G x e-2G

where G = Number of requests per time slot willing to transmit.

e = Mathematical constant approximately equal to 2.718

So, η = 1 x 2.718(-2 x 1) = 0.1353

Therefore, In 1 sec1000 frames = 0.1353 x 1000 = 135.3(closest integer) =>135

 

Throughput =>  135

Question 57
Consider a complete binary tree with 7 nodes, Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of |A - B| is _______.
A
1
       Data-Structures       BFS-and-DFS
Question 57 Explanation: 
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

A={0,1,2} → BFS

The BFS traverse through level by level. 

DFS:

B={0,1,3} 

B={0,1,4}

B={0,2,6}

B={0,2,5}

The DFS starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

|A-B| = 1

Note: The cardinality of set A-B is 1. 

Question 58
Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1’s by a 0. Consider the following example.
              Input sequence:       00100011000011100
              Output sequence:    00000001000001100
A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.
What are the Boolean expressions corresponding to t and y in terms of s and b?
A
B
C
D
       Theory-of-Computation       Moore-and-Mealy-Machine
Question 58 Explanation: 
Question 59
If x and y are two decimal digits and (0.1101)2=(0.8xy5)10, the decimal value of x+yis _______.
A
3
       Digital-Logic-Design       Number-Systems
Question 59 Explanation: 
0.1101) 2 = 1/2 + 1/4 + 1/16= 0.5+0.25+ 0.0625 = (0.8125) 10 . x=1 and y=2 x+y= 1+2=3
Question 60
Consider the following ANSI C program:
#include<stdio.h>
#include<stdlib.h>
Struct Node{
           int value;
           struct Node *next;};
int main() {
           struct Node *boxE, *head, *boxN; int index = 0;
           boxE = head = (struct Node *) malloc(sizeof(struct Node));
           head->value = index;
           for (index = 1; index <= 3; index++) {
                    boxN = (struct Node *) malloc(sizeof(struct Node));
                    boxE->next = boxN;
                    boxN->value = index;
                    boxE = boxN; }
           for (index = 0; index <= 3; index++) {
                    printf(“Value at index %d is %d\n”, index, head->value);
                    head = head->next;
                    printf(“Value at index %d is %d\n”, index+1, head->value); } }                
  Which one of the statements below is correct about the program?
A
Upon execution, the program creates a linked-list of five nodes.
B
It dereferences an uninitialized pointer that may result in a run-time error.
C
Upon execution, the program goes into an infinite loop.
D
It has a missing return which will be reported as an error by the compiler.
       Data-Structures       Linked-List
Question 60 Explanation: 

One node is created with value 0.

Loop i runs from 1 to 3. Hence total 4 nodes will be created.

0     →   1     → 2     → 3 → NULL

When index =3, head =3

Head = Head → Next

Head → Value from printf will generate an error.

Question 61
Consider the following ANSI C program:
int main()  {
      Integer x;
      return 0;
}
Which one of the following phases in a seven-phase C compiler will throw an error?
A
Syntax analyzer
B
Lexical analyzer
C
Semantic analyzer
D
Machine dependent optimizer
       Compiler-Design       Phases-of-Compilers
Question 61 Explanation: 
Integer will be considered as a variable and hence it will be treated as an undeclared identifier and so it is a semantic error.
Question 62
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties:
  1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
  2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.
Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?
A
21
B
30
C
23
D
25
       Computer-Networks       Hamming-Distance
Question 62 Explanation: 

Input String : abbccddeee

The character frequencies are

Character

a

b

c

d

e

Frequency

1

2

2

2

3

Binary Code

?

?

?

?

?


Question 63
A
There exists a bijection from S1to S2.
B
There does not exist a bijection from S1to S2.
C
There exists a surjection from S1to S2.
D
There does not exist an injunction from S1to S2.
       Engineering-Mathematics       Linear-Algebra
Question 63 Explanation: 

The number of functions from a set A to set B is |B|^|A|.

S2: |B|= 3, |A|= n^2-1 +1 = n^2.
we have number of functions 3^(n^2).

S1: there are n*n positions in a matrix of size nxn. Each can be filled with either 0 or 1 or 2 i,e, in 3^(n^2)

 

As there are equal number of elements on both sides, S1->S2 can be one one , onto as well bijection



Question 64
 Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?
A
B
C
D
       Algorithms       Time-Complexity
Question 64 Explanation: 

The heap is nothing but a complete binary tree and uses linear search to find the elements. 

In min heap, the parent key is less than or equal to (≤) the child keys. The maximum values should present in the farthest leaf node for the worst case time complexity. 

To traverse all the elements in a heap will take O(n) time for the worst case because it uses the linear search to find the element. 

Question 65
 For a given biased coin, the probability that the outcome of a toss is a head is 0.4. This coin is tossed 1,000 times. Let X denote the random variable whose value is the number of times that head appeared in these 1,000 tosses. The standard deviation of X (rounded to 2 decimal places) is _______.
A
15.49
       Engineering-Mathematics       Probability-and-statistics
Question 65 Explanation: 
There are 65 questions to complete.