Flashcards · 9645 · AS Topic 2

Fundamental data structures (AS Level) flashcards

15 cards on AS Topic 2, subtopics 3.2.1 to 3.2.4. Pick a subtopic or study them all.

Study mode needs JavaScript. Every card is listed below, so you can still cover the answers and test yourself.

All 15 cards

For a quick read-through or printing. Cover the right-hand side to test yourself.

Static vs dynamic data structures: Static: fixed size at creation, giving fast, predictable indexed access, but wasting memory if oversized or failing if undersized. Dynamic: grows and shrinks while the program runs, at the cost of resizing overhead.
Is a Python list static or dynamic?: Dynamic: it grows and shrinks as the program runs. Python has no built-in array type; the array module and numpy provide arrays.
Would you use a static or dynamic structure for a year of daily temperatures, and for game high scores?: Temperatures: static, because the count (365 or 366) is known and fixed. High scores: dynamic, because the count is unknown and growing.
What is a two-dimensional array or list of lists?: A structure indexed by two coordinates, usually row and column, used for tabular or grid data. E.g. seating[2][5] is row index 2, seat index 5. Exam questions use no more than two dimensions.

What is a record?: A data structure holding fields of different data types about one entity, handled as a single item, e.g. a student with a name (string), age (integer) and fees paid (Boolean).
Record vs array: A record groups fields of different types about one entity, accessed by field name. An array holds items of the same type, accessed by index.
How can a record be stored in Python?: Python has no record type, so a class (or data class) with one attribute per field is commonly used, or a dictionary with one key per field. A list of records holds many entities.

What is a queue?: A first in, first out (FIFO) structure: items are added (enqueued) at the rear and removed (dequeued) from the front.
Give three uses of queues: Print spooling, process scheduling, keyboard and data buffers, and breadth-first search.
Linear vs circular queue in a one-dimensional array: In a linear queue the front moves along as items leave, so space at the start is wasted. In a circular queue the rear pointer wraps round to the start, reusing freed space.
Which tests and pointers does an array-based queue need?: Front and rear pointers (and usually a count). Test for empty before dequeuing and for full before enqueuing.

What is a stack?: A last in, first out (LIFO) structure: items are pushed onto and popped off the top.
Push vs pop vs peek: Push adds an item to the top. Pop removes and returns the top item. Peek returns the top item without removing it.
Give three uses of stacks: The call stack for subroutines, undo in an application, evaluating expressions, and depth-first search.
Stack overflow vs stack underflow: Overflow: trying to push onto a full stack. Underflow: trying to pop from an empty stack. Check full before pushing and empty before popping.