Success TrackerSuccess Tracker
Log inSign up

The PYQ practice room

GATE CS 2021 Set 1

All 65 solved GATE CS 2021 Set 1 questions in exam order. Open a question, commit to an answer, and learn from the step-by-step solution. One question at a time.

Attempt before revealInstant answer feedbackExplore questions
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.

Questions

65

Paper marks

100

Question formats

3

MCQ · NAT · MSQ

Revision mode

Self-paced

No timer. Focus on understanding.

Difficulty mixEasy 18Medium 40Hard 7

Explore the questions

65 of 65 questions

General Aptitude (GA)

9
  1. Think it through. Then check your answer.

    Question

    The ratio of boys to girls in a class is 7 to 3.
    Among the options below, an acceptable value for the total number of students in the class is:
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  2. Think it through. Then check your answer.

    Question

    A polygon is convex if, for every pair of points, P and Q belonging to the polygon, the line segment PQ lies completely inside or on the polygon.
    Which one of the following is NOT a convex polygon?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  3. Think it through. Then check your answer.

    Question

    Consider the following sentences:
    (i) Everybody in the class is prepared for the exam.
    (ii) Babu invited Danish to his home because he enjoys playing chess.
    Which of the following is the CORRECT observation about the above two sentences?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  4. Think it through. Then check your answer.

    Question

    A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse order of folding, will look like ______.
    Sequence of folding and punching a circular paper
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  5. Think it through. Then check your answer.

    Question

    ____ is to surgery as writer is to ____
    Which one of the following options maintains a similar logical relation in the above sentence?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  6. Think it through. Then check your answer.

    Question

    We have 2 rectangular sheets of paper, M and N, of dimensions 6 cm x 1 cm each. Sheet M is rolled to form an open cylinder by bringing the short edges of the sheet together. Sheet N is cut into equal square patches and assembled to form the largest possible closed cube. Assuming the ends of the cylinder are closed, the ratio of the volume of the cylinder to that of the cube is __________
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  7. Think it through. Then check your answer.

    Question

    ItemsCost (₹)Profit %Marked Price (₹)
    P5,400---5,860
    Q---2510,000
    Details of prices of two items P and Q are presented in the above table. The ratio of cost of item P to cost of item Q is 3:4. Discount is calculated as the difference between the marked price and the selling price. The profit percentage is calculated as the ratio of the difference between selling price and cost, to the cost(Profit %=Selling price−CostCost×100).(\text{Profit } \% = \frac{\text{Selling price} - \text{Cost}}{\text{Cost}} \times 100).The discount on item Q, as a percentage of its marked price, is ________
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  8. Think it through. Then check your answer.

    Question

    There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag.
    The probability that at least two chocolates are identical is ________
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  9. Think it through. Then check your answer.

    Question

    Given below are two statements 1 and 2, and two conclusions I and II.
    Statement 1: All bacteria are microorganisms.
    Statement 2: All pathogens are microorganisms.
    Conclusion I: Some pathogens are bacteria.
    Conclusion II: All pathogens are not bacteria.
    Based on the above statements and conclusions, which one of the following options is logically CORRECT?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page

Computer Science and Information Technology (CS, Set-1)

56
  1. Think it through. Then check your answer.

    Question

    Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity: poverty and income inequality.
    Which one of the following statements summarizes the passage?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  2. Think it through. Then check your answer.

    Question

    Suppose that L1L_1 is a regular language and L2L_2 is a context-free language. Which one of the following languages is NOT necessarily context-free?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  3. Think it through. Then check your answer.

    Question

    Let PP be an array containing nn integers. Let tt be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of nn elements. Which one of the following choices is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  4. Think it through. Then check your answer.

    Question

    Consider the following three functions.f1=10nf2=nlog⁡nf3=nnf_1 = 10^n \quad f_2 = n^{\log n} \quad f_3 = n^{\sqrt{n}}Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  5. Think it through. Then check your answer.

    Question

    Consider the following statements.
    S1S_1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
    S2S_2: The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
    Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  6. Think it through. Then check your answer.

    Question

    Consider the following statements.
    S1S_1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
    S2S_2: For any context-free grammar, there is a parser that takes at most O(n3)O(n^3) time to parse a string of length nn.
    Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  7. Think it through. Then check your answer.

    Question

    Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  8. Think it through. Then check your answer.

    Question

    Let pp and qq be two propositions. Consider the following two formulae in propositional logic.S1:(¬p∧(p∨q))→qS_1: (\neg p \wedge (p \vee q)) \to qS2:q→(¬p∧(p∨q))S_2: q \to (\neg p \wedge (p \vee q))Which one of the following choices is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  9. Think it through. Then check your answer.

    Question

    Consider the following two statements.
    S1S_1: Destination MAC address of an ARP reply is a broadcast address.
    S2S_2: Destination MAC address of an ARP request is a broadcast address.
    Which one of the following choices is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  10. Think it through. Then check your answer.

    Question

    Consider the following array.
    2332456972738997
    Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  11. Think it through. Then check your answer.

    Question

    A binary search tree TT contains nn distinct elements. What is the time complexity of picking an element in TT that is smaller than the maximum element in TT?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  12. Think it through. Then check your answer.

    Question

    In the context of operating systems, which of the following statements is/are correct with respect to paging?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  13. Think it through. Then check your answer.

    Question

    Let ⟨M⟩\langle M \rangle denote an encoding of an automaton MM. Suppose that Σ={0,1}\Sigma = \{0, 1\}. Which of the following languages is/are NOT recursive?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  14. Think it through. Then check your answer.

    Question

    Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery.
    Which of the following statements is/are correct?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  15. Think it through. Then check your answer.

    Question

    Which of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  16. Think it through. Then check your answer.

    Question

    Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory foo.
    Which of the following operations will necessarily require a full scan of foo for successful completion?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  17. Think it through. Then check your answer.

    Question

    In an undirected connected planar graph GG, there are eight vertices and five faces. The number of edges in GG is _______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  18. Think it through. Then check your answer.

    Question

    Consider the following undirected graph with edge weights as shown:
    An undirected graph with 6 vertices arranged in a 2x3 grid. The edges have weights 0.1 and 0.9.
    The number of minimum-weight spanning trees of the graph is _______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  19. Think it through. Then check your answer.

    Question

    The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter 22. For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to 22 decimal places) is ___________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  20. Think it through. Then check your answer.

    Question

    There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that:
    • The fastest computer gets the toughest job and the slowest computer gets the easiest job.
    • Every computer gets at least one job.

    The number of ways in which this can be done is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  21. Think it through. Then check your answer.

    Question

    Consider the following expression.lim⁡x→−32x+22−4x+3\lim_{x \to -3} \frac{\sqrt{2x + 22} - 4}{x + 3}The value of the above expression (rounded to 2 decimal places) is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  22. Think it through. Then check your answer.

    Question

    Consider the following sequence of operations on an empty stack.
    push(54); push(52); pop(); push(55); push(62); s = pop();
    Consider the following sequence of operations on an empty queue.
    enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
    The value of s + q is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  23. Think it through. Then check your answer.

    Question

    Consider a computer system with a byte-addressable primary memory of size 2322^{32} bytes. Assume the computer system has a direct-mapped cache of size 32 KB (1 KB=2101 \text{ KB} = 2^{10} bytes), and each cache block is of size 64 bytes.
    The size of the tag field is __________ bits.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  24. Think it through. Then check your answer.

    Question

    A relation r(A,B)r(A, B) in a relational database has 1200 tuples. The attribute AA has integer values ranging from 6 to 20, and the attribute BB has integer values ranging from 1 to 20. Assume that the attributes AA and BB are independently distributed.
    The estimated number of tuples in the output of σ(A>10)∨(B=18)(r)\sigma_{(A>10) \lor (B=18)}(r) is ___________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  25. Think it through. Then check your answer.

    Question

    Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127.S:1E:10000001F:11110000000000000000000S : 1 \quad E : 10000001 \quad F : 11110000000000000000000Here S,ES, E and FF denote the sign, exponent and fraction components of the floating point representation.
    The decimal value corresponding to the above representation (rounded to 2 decimal places) is ___________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  26. Think it through. Then check your answer.

    Question

    Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is ________ milliseconds.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  27. Think it through. Then check your answer.

    Question

    Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:
    P -> D* E*
D -> int ID {record that ID.lexeme is of type int}
D -> bool ID {record that ID.lexeme is of type bool}
E -> E1 + E2 {check that E1.type = E2.type = int; set E.type := int}
E -> !E1 {check that E1.type = bool; set E.type := bool}
E -> ID {set E.type := int}
    With respect to the above grammar, which one of the following choices is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  28. Think it through. Then check your answer.

    Question

    The following relation records the age of 500 employees of a company, where empNoempNo (indicating the employee number) is the key:empAge(empNo,age)empAge(empNo, age)Consider the following relational algebra expression:ΠempNo(empAge⋈(age>age1)ρempNo1,age1(empAge))\Pi_{empNo}(empAge \bowtie_{(age > age1)} \rho_{empNo1, age1} (empAge))What does the above expression generate?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  29. Think it through. Then check your answer.

    Question

    Consider a 3-bit counter, designed using T flip-flops, as shown below:
    Assuming the initial state of the counter given by PQR as 000, what are the next three states?
    Circuit diagram of a 3-bit counter with three T flip-flops labeled Tp, Tq, Tr. The clock pulse is connected to Tp. The output P of Tp clocks Tq. The output Q' of Tq clocks Tr. All T inputs appear to be connected to logic 1.

    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  30. Think it through. Then check your answer.

    Question

    Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is d8d7d6d5c8d4d3d2c4d1c2c1d_8d_7d_6d_5c_8d_4d_3d_2c_4d_1c_2c_1, where the data bits and the check bits are given in the following tables:
    Data bits
    d8d_8d7d_7d6d_6d5d_5d4d_4d3d_3d2d_2d1d_1
    110xx0101
    Check bits
    c8c_8c4c_4c2c_2c1c_1
    yy010
    Which one of the following choices gives the correct values of xx and yy?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  31. Think it through. Then check your answer.

    Question

    Consider the following recurrence relation.T(n)={T(n/2)+T(2n/5)+7nif n>01if n=0T(n) = \begin{cases} T(n/2) + T(2n/5) + 7n & \text{if } n > 0 \\ 1 & \text{if } n = 0 \end{cases}Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  32. Think it through. Then check your answer.

    Question

    Consider the following context-free grammar where the set of terminals is {a,b,c,d,f}\{a, b, c, d, f\}.S→daT∣RfS \rightarrow d a T \mid R fT→aS∣baT∣ϵT \rightarrow a S \mid b a T \mid \epsilonR→caTR∣ϵR \rightarrow c a T R \mid \epsilonThe following is a partially-filled LL(1) parsing table.
    aabbccddff$\$
    S(1)S→daTS \rightarrow d a T(2)
    TT→aST \rightarrow a ST→baTT \rightarrow b a T(3)T→ϵT \rightarrow \epsilon(4)
    RR→caTRR \rightarrow c a T RR→ϵR \rightarrow \epsilon
    Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  33. Think it through. Then check your answer.

    Question

    Let ri(z)r_i(z) and wi(z)w_i(z) denote read and write operations respectively on a data item zz by a transaction TiT_i. Consider the following two schedules.S1:r1(x)r1(y)r2(x)r2(y)w2(y)w1(x)S_1: r_1(x) r_1(y) r_2(x) r_2(y) w_2(y) w_1(x)S2:r1(x)r2(x)r2(y)w2(y)r1(y)w1(x)S_2: r_1(x) r_2(x) r_2(y) w_2(y) r_1(y) w_1(x)Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  34. Think it through. Then check your answer.

    Question

    Consider the relation R(P, Q, S, T, X, Y, Z, W) with the following functional dependencies.PQ→X;P→YX;Q→Y;Y→ZWPQ \rightarrow X; P \rightarrow YX; Q \rightarrow Y; Y \rightarrow ZWConsider the decomposition of the relation RR into the constituent relations according to the following two decomposition schemes.D1:R=[(P,Q,S,T);(P,T,X);(Q,Y);(Y,Z,W)]D_1: R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)]D2:R=[(P,Q,S);(T,X);(Q,Y);(Y,Z,W)]D_2: R = [(P, Q, S); (T, X); (Q, Y); (Y, Z, W)]Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  35. Think it through. Then check your answer.

    Question

    Let GG be a group of order 6, and HH be a subgroup of GG such that 1<∣H∣<61 < |H| < 6. Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  36. Think it through. Then check your answer.

    Question

    Consider the two statements.
    S1S_1: There exist random variables XX and YY such that(E[(X–E(X))(Y−E(Y))])2>Var[X]Var[Y](\text{E}[(X – \text{E}(X)) (Y − \text{E}(Y))])^2 > \text{Var}[X] \text{Var}[Y]S2S_2: For all random variables XX and YY,Cov[X,Y]=E[∣X–E[X]∣∣Y–E[Y]∣]\text{Cov}[X, Y] = \text{E}[|X – \text{E}[X]| |Y – \text{E}[Y]|]Which one of the following choices is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  37. Think it through. Then check your answer.

    Question

    Let G=(V,E)G = (V, E) be an undirected unweighted connected graph. The diameter of GG is defined as:diam(G)=max⁡u,v∈V{the length of shortest path between u and v}\text{diam}(G) = \max_{u,v \in V} \{\text{the length of shortest path between } u \text{ and } v\}Let MM be the adjacency matrix of GG.
    Define graph G2G_2 on the same set of vertices with adjacency matrix NN, whereNij={1if Mij>0 or Pij>0, where P=M20otherwiseN_{ij} = \begin{cases} 1 & \text{if } M_{ij} > 0 \text{ or } P_{ij} > 0, \text{ where } P = M^2 \\ 0 & \text{otherwise} \end{cases}Which one of the following statements is true?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  38. Think it through. Then check your answer.

    Question

    Consider the following ANSI C program.
    #include <stdio.h>
int main()
{
    int i, j, count;
    count = 0;
    i = 0;
    for (j = -3; j <= 3; j++)
    {
        if ((j >= 0) && (i++))
            count = count + j;
    }
    count = count + i;
    printf("%d", count);
    return 0;
}
    Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  39. Think it through. Then check your answer.

    Question

    Consider the following language.L={w∈{0,1}∗∣w ends with the substring 011}L = \{w \in \{0,1\}^* \mid w \text{ ends with the substring } 011\}Which one of the following deterministic finite automata accepts LL?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  40. Think it through. Then check your answer.

    Question

    For a Turing machine MM, ⟨M⟩\langle M \rangle denotes an encoding of MM. Consider the following two languages.L1={⟨M⟩∣M takes more than 2021 steps on all inputs}L_1 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on all inputs}\}L2={⟨M⟩∣M takes more than 2021 steps on some input}L_2 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on some input}\}Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  41. Think it through. Then check your answer.

    Question

    Define RnR_n to be the maximum amount earned by cutting a rod of length nn meters into one or more pieces of integer length and selling them. For i>0i > 0, let p[i]p[i] denote the selling price of a rod whose length is ii meters. Consider the array of prices:p[1]=1,p[2]=5,p[3]=8,p[4]=9,p[5]=10,p[6]=17,p[7]=18p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18Which of the following statements is/are correct about R7R_7?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  42. Think it through. Then check your answer.

    Question

    An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
    Let TT be a DFS tree obtained by doing DFS in a connected undirected graph GG. Which of the following options is/are correct?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  43. Think it through. Then check your answer.

    Question

    Consider the following Boolean expression.F=(X+Y+Z)(X‾+Y)(Y‾+Z)F = (X + Y + Z)(\overline{X} + Y)(\overline{Y} + Z)Which of the following Boolean expressions is/are equivalent to F‾\overline{F} (complement of FF)?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  44. Think it through. Then check your answer.

    Question

    A relation R is said to be circular if aRbaRb and bRcbRc together imply cRacRa. Which of the following options is/are correct?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  45. Think it through. Then check your answer.

    Question

    A TCP server application is programmed to listen on port number PP on host SS. A TCP client is connected to the TCP server over the network. Consider that while the TCP connection was active, the server machine SS crashed and rebooted. Assume that the client does not use the TCP keepalive timer. Which of the following behaviors is/are possible?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  46. Think it through. Then check your answer.

    Question

    Consider two hosts PP and QQ connected through a router RR. The maximum transfer unit (MTU) value of the link between PP and RR is 1500 bytes, and between RR and QQ is 820 bytes. A TCP segment of size 1400 bytes was transferred from PP to QQ through RR, with IP identification value as 0x1234. Assume that the IP header size is 20 bytes. Further, the packet is allowed to be fragmented, i.e., Don't Fragment (DF) flag in the IP header is not set by PP. Which of the following statements is/are correct?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  47. Think it through. Then check your answer.

    Question

    Consider the following pseudocode, where SS is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic.
    1. int counter = 0;
2. Semaphore S = init(5);
3. void parop(void)
4. {
5.     wait(S);
6.     wait(S);
7.     counter++;
8.     signal(S);
9.     signal(S);
10.}
    If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  48. Think it through. Then check your answer.

    Question

    Consider a dynamic hashing approach for 4-bit integer keys:
    1.There is a main hash table of size 4.
    2.The 2 least significant bits of a key is used to index into the main hash table.
    3.Initially, the main hash table entries are empty.
    4.Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
    5.First, the 3rd3^{rd} least significant bit is used to divide the keys into left and right subtrees.
    6.To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th4^{th} least significant bit.
    7.A split is done only if it is needed, i.e., only when there is a collision.
    Consider the following state of the hash table.
    Diagram showing a hash table with indices 00, 01, 10, 11. Index 00 is empty. Index 01 points to a tree structure splitting on 0 and 1, with the 1 branch splitting again. Index 10 points to a tree splitting on 0 and 1. Index 11 points to a single node.

    Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
    Your answer

    Select all that apply, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  49. Think it through. Then check your answer.

    Question

    Consider the following ANSI C function.
    int SimpleFunction(int Y[], int n, int x)
{
    int total = Y[0], loopIndex;
    for (loopIndex = 1; loopIndex <= n - 1; loopIndex++)
        total = x * total + Y[loopIndex];
    return total;
}
    Let ZZ be an array of 10 elements with Z[i]=1Z[i]=1, for all ii such that 0≤i≤90 \leq i \leq 9. The value returned by SimpleFunction(Z,10,2Z, 10, 2) is ________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  50. Think it through. Then check your answer.

    Question

    Consider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following:
    • The time taken for processing the data frame by the receiver is negligible.
    • The time taken for processing the acknowledgement frame by the sender is negligible.
    • The sender has infinite number of frames available for transmission.
    • The size of the data frame is 2,000 bits and the size of the acknowledgement frame is 10 bits.
    • The link data rate in each direction is 1 Mbps (=106= 10^6 bits per second).
    • One way propagation delay of the link is 100 milliseconds.
    The minimum value of the sender's window size in terms of the number of frames, (rounded to the nearest integer) needed to achieve a link utilization of 50% is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  51. Think it through. Then check your answer.

    Question

    Consider the following C code segment:
    a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;
    In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  52. Think it through. Then check your answer.

    Question

    In a pushdown automaton P=(Q,Σ,Γ,δ,q0,F)P = (Q, \Sigma, \Gamma, \delta, q_0, F), a transition of the form,
    where p,q∈Qp, q \in Q, a∈Σ∪{ϵ}a \in \Sigma \cup \{\epsilon\}, and X,Y∈Γ∪{ϵ}X, Y \in \Gamma \cup \{\epsilon\}, represents(q,Y)∈δ(p,a,X).(q, Y) \in \delta(p, a, X).Consider the following pushdown automaton over the input alphabet Σ={a,b}\Sigma = \{a, b\} and stack alphabet Γ={#,A}\Gamma = \{\#, A\}.
    The number of strings of length 100 accepted by the above pushdown automaton is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  53. Think it through. Then check your answer.

    Question

    Consider the following matrix.(0111101111011110)\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}The largest eigenvalue of the above matrix is ___________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  54. Think it through. Then check your answer.

    Question

    A five-stage pipeline has stage delays of 150, 120, 150, 160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds each.
    The total time to execute 100 independent instructions on this pipeline, assuming there are no pipeline stalls, is ___________ nanoseconds.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  55. Think it through. Then check your answer.

    Question

    A sender (S) transmits a signal, which can be one of the two kinds: HH and LL with probabilities 0.1 and 0.9 respectively, to a receiver (R).
    In the graph below, the weight of edge (u,v)(u, v) is the probability of receiving vv when uu is transmitted, where u,v∈{H,L}u, v \in \{H, L\}. For example, the probability that the received signal is LL given the transmitted signal was HH, is 0.7.
    Probabilistic transition graph showing Sender S (H, L) and Receiver R (H, L) with edge weights
    If the received signal is HH, the probability that the transmitted signal was HH (rounded to 2 decimal places) is ___________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  56. Think it through. Then check your answer.

    Question

    Consider the following instruction sequence where registers R1, R2 and R3 are general purpose and MEMORY[X] denotes the content at the memory location X.
    InstructionSemanticsInstruction Size (bytes)
    MOV R1, (5000)R1 ←\leftarrow MEMORY[5000]4
    MOV R2, (R3)R2 ←\leftarrow MEMORY[R3]4
    ADD R2, R1R2 ←\leftarrow R1+R22
    MOV (R3), R2MEMORY[R3] ←\leftarrow R24
    INC R3R3 ←\leftarrow R3+12
    DEC R1R1 ←\leftarrow R1-12
    BNZ 1004Branch if not zero to the given absolute address2
    HALTStop1
    Assume that the content of the memory location 5000 is 10, and the content of the register R3 is 3000. The content of each of the memory locations from 3000 to 3010 is 50. The instruction sequence starts from the memory location 1000. All the numbers are in decimal format. Assume that the memory is byte addressable.
    After the execution of the program, the content of memory location 3010 is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page