How to think about data structures

Ideas

Question 1

Which statement best describes what a data structure is?

A.A container that makes every operation fastB.A method for sorting data before you search itC.A way of storing data that uses the least possible memoryD.An arrangement of data that makes some operations cheap at the cost of others

Question 2

An operation takes 3n + 50 steps on n items. What is its growth described as?

A.O(50), because the constant dominates for small nB.O(3n + 50), because that is the exact countC.O(n), because only the fastest-growing term mattersD.O(n squared), because there are two terms

Reading a cost claim

Question 3

Adding to a list is usually one step, but occasionally copies everything. Averaged over a long run it is constant. What is that called?

A.Worst caseB.Amortised costC.Best caseD.Average case

Question 4

You are writing audio code where every single operation must finish before the next sample is due. Which cost matters most?

A.Best case, because the hardware is fastB.Average case, because most operations are typicalC.Worst case, because one slow operation drops the sampleD.Amortised, because it describes the long run

4 questions left to answer.