9618 · 10.4
Introduction to Abstract Data Types (ADT) flashcards
Revision flashcards for Cambridge 9618 Introduction to Abstract Data Types (ADT) (syllabus 10.4). Flip, recall, then mark a real past-paper question.
Card
What is an Abstract Data Type (ADT)?
A logical description of how data is viewed and the operations that can be performed on it, without regard to how it will be implemented. It's a model or a blueprint.
Card
What is a Data Structure?
A concrete, physical implementation of an ADT. It's the 'how' - for example, using an array or pointers to organise data in memory.
Card
What is the key difference between an ADT and a Data Structure?
An ADT is a theoretical concept (the 'what'), while a data structure is a concrete implementation (the 'how'). E.g., a Queue (ADT) can be implemented using an array (data structure).
Card
What is Encapsulation in the context of ADTs?
The bundling of data with the methods or operations that act on that data. The data is typically kept private and is only accessible via the public interface.
Card
What is Information Hiding?
The principle of concealing the implementation details of an ADT from the user. The user interacts with the ADT through its interface, without needing to know its internal workings.
Card
What is an ADT's 'interface'?
The set of public procedures and functions that a programmer can use to interact with the ADT. For a Stack, this would include `Push()`, `Pop()`, and `isEmpty()`.
Card
Is an array an ADT or a data structure?
An array is a data structure. It's a concrete way of storing a collection of elements in contiguous memory locations. It can be used to *implement* an ADT like a stack or queue.
Card
Name the two main operations for a Stack ADT.
PUSH (add an item to the top) and POP (remove an item from the top).
Card
Name the two main operations for a Queue ADT.
ENQUEUE (add an item to the rear) and DEQUEUE (remove an item from the front).
Card
What is a benefit of using ADTs in a large software project?
It allows the implementation of the data structure to be changed without affecting the rest of the program, as long as the interface remains the same. This improves maintainability.
Card
What does it mean for an ADT to be 'dynamic'?
It means the data structure used to implement it can grow or shrink in size at runtime, like a linked list. This contrasts with a 'static' implementation using a fixed-size array.