Fundamentals of Data Structures

What Fundamentals of Data Structures covers

Arrays, records and files, then the abstract data types — stacks, queues, graphs, trees, hash tables and dictionaries — with the operations and traces each is examined through. Examined on Paper 1.

The 11 subtopics

Each one has its own page.

• Data Structures and Abstract Data TypesRecall questions on what a data structure is, how it differs from an abstract data type and why a particular structure is chosen.Open →
• Static and Dynamic Data StructuresRecall questions on the difference between static and dynamic structures and on the advantages and disadvantages of each.Open →
• Queues and Linear QueuesRecall questions on what a queue is, its typical uses, the front and rear pointers and the working of a linear queue.Open →
• Circular and Priority QueuesRecall questions on adding to, removing from and testing a circular queue, tracing one held in an array, how a priority queue works and is used, and comparing linear and circular queues.Open →
• StacksRecall questions on push, pop and peek, what the top pointer holds, testing for empty and full, and tracing a sequence of operations on an array-based stack.Open →
• GraphsRecall questions on vertices and edges, weighted, directed and undirected graphs, and the trade-off between an adjacency matrix and an adjacency list.Open →
• TreesRecall questions on rooted and binary trees, parent, child and descendant, leaf nodes, and the ordering rule that governs a binary search tree.Open →
• Hash tablesRecall questions on hashing algorithms, working out where a key is stored, why collisions are unavoidable, and how rehashing resolves them.Open →
• DictionariesRecall questions on key-value pairs, how a dictionary differs from an array, why it is usually built on a hash table, and the word-count algorithm.Open →
• Vectors and Their NotationRecall questions on what a vector is, list and set notation for vectors, and the function interpretation.Open →
• Vector Arithmetic and GeometryRecall questions on visualising a vector as an arrow, adding vectors, scalar multiplication and the dot product.Open →

What you need to know

Answer each one before you reveal it.

Take Fundamentals of Data Structures further

The same content, four other ways.

Commonly confused

Pairs that lose marks when they are blurred together.

• Stack vs Queue

  Stack: a last-in-first-out collection accessed at one end. Queue: a first-in-first-out collection entered and left at opposite ends.

• Static structure vs Dynamic structure

  Static structure: a collection whose allocated size stays fixed during execution. Dynamic structure: a collection whose allocated size can change during execution.

• Text file vs Binary file

  Text file: stored characters interpreted through a character encoding. Binary file: stored bit patterns interpreted through an agreed record format.

Questions from this topic

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.

What is inside Levo

Six ways to work the same material.

Fundamentals of Data Structures revision questions

What does Fundamentals of Data Structures cover in AQA A-Level Computer Science?

11 subtopics: data structures and abstract data types, static and dynamic data structures, queues and linear queues, circular and priority queues, stacks, graphs, trees, hash tables, dictionaries, vectors and their notation and vector arithmetic and geometry. Each one has its own page with questions and model answers.

How is Fundamentals of Data Structures organised?

By the AQA 7517 specification, subtopic by subtopic, so it matches the order you are taught it in.