GATE Solved Paper 2017-19 - GATE 2017 Shift 2

26. Match the algorithms with their time complexities:

  • Option : C
  • Explanation :
    P. Towers of Hanoi
    ⇒ T(n) = 2T(n-1) + 1 ⇒ θ(2n)
    Q. Binary search
    ⇒ T(n) = T(n/2) + c ⇒ θ(log n)
    R. Heap sort ⇒ θ(nlog n)
    S. Addition of two n × n matrices ⇒ θ(nr)
Cancel reply
Cancel reply

27. Match the following according to input (from the left column) to the complier phase (in the right column) that processes it.

  • Option : C
  • Explanation :
    Lexical Analysis phase processes character stream and generates tokens, e.g. identifier or keywords.
    Tokens are processed by Syntax analysis analyzer.
    Syntax tree is processed by Semantic analyzer.
    Intermediate code such as 3 –address code is used for code generation process.
Cancel reply
Cancel reply

28. Consider the following statements about the routing protocols, Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) in an IPv4 network.
I. RIP uses distance vector routing
II. RIP packets are sent using UDP
III. OSPF packets are sent using TCP
IV. OSPF operation is based on link-state routing
Which of the statements above are CORRECT?

  • Option : C
  • Explanation :
    Statement (1): RIP uses distance vector routing. “CORRECT”
    RIP is one of the oldest DVR protocol which employ the hop count as a routing metric.
    Statement (2): RIP packets are sent using UDP. “CORRECT”
    RIP uses the UDP as its transport protocol, and is assigned the reserved port no 520
    Statement (3): OSPF packets are sent using TCP. “INCORRECT”
    OSPF does not use a transport protocol, such as UDP (or) TCP, but encapsulates its data directly in IP packets.
    Statement (4): OSPF operation is based on link state routing. “CORRECT”
    OSPF is a routing protocol which uses link state routing (LSR) and works within a single autonomous system.
    Hence Option “C” is correct.
Cancel reply
Cancel reply

29. If

Cancel reply
Cancel reply

30. In a file allocation system, which of the following allocation schemes(s) can be used if no external fragmentation is allowed?
I. Contiguous
II. Linked
III. Indexed

  • Option : D
  • Explanation :
    Contiguous allocations suffer from external fragmentation. But linked and indexed allocation schemes free from external fragmentation. Hence, option D is correct.
Cancel reply
Cancel reply