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)
PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 2
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.
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.
then the constants R and S are, respectively
Contiguous allocations suffer from external fragmentation. But linked and indexed allocation schemes free from external fragmentation. Hence, option D is correct.
