Skip to content
GATETECH
Official PYQ · 1995Q2.9Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 1995 Q2.9 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

A language with string manipulation facilities uses the following operations

head(s): first character of a string
tail(s): all but exclude the first character of a string
concat(s1, s2): s1s2

For the string "acbcacbc" what will be the output of

concat(head(s), head(tail(tail(s))))
Choose one option
View worked solution

Answer: C

Given the string s="acbc"s = \text{"acbc"} and the operations defined as:

  • head(s)\text{head}(s): returns the first character of string ss.
  • tail(s)\text{tail}(s): returns the string ss excluding its first character.
  • concat(s1,s2)\text{concat}(s_1, s_2): concatenates s1s_1 and s2s_2.

We evaluate the expression step-by-step from the inside out:

  1. Evaluate head(s)\text{head}(s): head("acbc")=’a’\text{head}(\text{"acbc"}) = \text{'a'}
  2. Evaluate the inner tail(s)\text{tail}(s): tail("acbc")="cbc"\text{tail}(\text{"acbc"}) = \text{"cbc"}
  3. Evaluate the outer tail\text{tail}: tail(tail(s))=tail("cbc")="bc"\text{tail}(\text{tail}(s)) = \text{tail}(\text{"cbc"}) = \text{"bc"}
  4. Evaluate the head of the resulting tail: head(tail(tail(s)))=head("bc")=’b’\text{head}(\text{tail}(\text{tail}(s))) = \text{head}(\text{"bc"}) = \text{'b'}
  5. Perform the concatenation: concat(head(s),head(tail(tail(s))))=concat(’a’,’b’)="ab"\text{concat}(\text{head}(s), \text{head}(\text{tail}(\text{tail}(s)))) = \text{concat}(\text{'a'}, \text{'b'}) = \text{"ab"}

Thus, the output is abab, which corresponds to Option C.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions