Data Structures and Abstract Data Types

Overview

Recall questions on what a data structure is, how it differs from an abstract data type and why a particular structure is chosen.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a data structure?

   Model answer

   An organised collection of related data items, stored together in a defined arrangement so that the data can be accessed and manipulated efficiently. The structure defines both how the items are held in memory and the operations that may be performed on them.

2. 2

   What is the difference between an abstract data type and a data structure?

   Model answer

   An abstract data type is a logical description of what data is held and which operations may be performed on it, with no statement of how it is implemented. A data structure is the concrete implementation that actually stores the data in memory. For example, a stack is an abstract data type with push and pop operations; it may be implemented as a data structure using an array plus a top pointer, or using a linked list.

3. 3

   Give four everyday contexts that behave like a data structure you have studied.

   Model answer

   A queue at a supermarket till behaves like a queue (first in, first out). A stack of plates behaves like a stack (last in, first out). A telephone contacts list that finds a number from a name behaves like a dictionary (a value looked up by its key). A road map with towns and roads behaves like a weighted graph.

4. 4

   Why do programmers choose a particular data structure for a problem?

   Model answer

   Because the structure determines how efficiently the operations the program needs most can be carried out. Choosing a structure whose natural operations match the problem gives faster code and simpler logic — for example a queue for jobs waiting for a printer, a stack for undo history, a graph for a road network, a hash table for fast lookup by key.

5. 5

   Describe a one-dimensional array.

   Model answer

   A run of elements that all share one data type, stored under a single identifier and reached by an index. For example an array of ten integers might be indexed 0 to 9, and element 3 is accessed as a[3]. One-dimensional arrays are a natural fit for holding a vector.

6. 6

   What is a two-dimensional array a useful way of representing?

   Model answer

   A matrix — or more generally any table of values with rows and columns, such as a grid, a game board, or an adjacency matrix for a graph. Each element is accessed by two integer indices, one for the row and one for the column.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.