GATE Solved Paper 2020 - GATE 2020

11. Consider the following statements.
I. Daisy chaining is used to assign priorities in attending interrupts.
II. When a device raises a vectored interrupt, the CPU does polling to identify the source of the interrupt.
III. In polling, the CPU periodically checks the status bits to know if any device needs its attention.
IV. During DMA, both the CPU and DMA controller can be bus masters at the same time.
Which of the above statements is/are TRUE?

  • Option : C
  • Explanation :
    Statement 1: True, Daisy chaining assign non-uniform priorities in attending interrupts.
    Statement 2: False, A vectored interrupt means, CPU knows the source of the interrupt.
    Statement 3: True, polling technique makes CPU to periodically verity states bits and service for need
    Statement 4: False: During DMA also, CPU will have master control over the bus. (OR) IOP (I/O processor) and CPU can be mastered but not at the same time.
    Hence, I and III are true
Cancel reply
Cancel reply

13. What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

  • Option : C
  • Explanation :
    Inserting an element at the beginning of the linked list takes O(1) time. But, If it needs to be sorted, then in the worst case, it takes (log n) time using merge sort. To insert such n elements and make sure it is in sorted order, the worst case time complexity would be O(n log n).
Cancel reply
Cancel reply

14. Consider the functions

  • Option : D
  • Explanation :
    (i) e–x is decreasing

    (ii) f(x) = x2 – sinx
    f′ (x) = 2x – cos x
    Now check f′ (x) at [0, 1]
    f′ (0) = –1
    f′ (1) = 2 – cos 1 = 1.4596
    ∴ f(x) is not increasing everywhere

    f′(x) ≥ 0 for all x.
    ∴ f(x) is an increasing function.
Cancel reply
Cancel reply

15. Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

  • Option : B
  • Explanation :
    Eliminate the options.
    --Option (A) is incorrect, it forces the string to start with 1, we cannot generate strings like 01, 0111, ….
    -- Option (C) is incorrect, it generates string ending with 1, so cannot generate strings like 10, 1110
    -- Option (D), not always generates strings with odd 1’s as it can generate 110.
    -- Options (B), is correct, as it can generate all the string with odd number of 1’s.
Cancel reply
Cancel reply