Modelling a phone book as a dictionary rather than a list of pairs changes almost nothing about what the program can do, and a great deal about what it costs. Why does the representation matter so much when the information is identical?

C. Because the representation decides which operations are cheap.

The two hold identical information and differ in what the structure makes easy, and since lookup by name is essentially all a phone book does, the choice decides whether the program is fast at the one thing it does. Note dictionaries preserve insertion order and are not sorted, so a sorted listing needs a sort either way. Get the representation wrong and no later optimisation recovers it.