Fundamentals of Data Structures | AQA A-Level Computer Science (7517)

Fundamentals of Data Structures

136 questions
11 subtopics
Paper 1: the on-screen exam
Paper 1

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.

Sample questions from Fundamentals of Data Structures

Answer each one closed book first, then open the answer.

Data Structures and Abstract Data Types

Define an n-dimensional array.

Show the answer
An n-dimensional array holds elements that all share a single data type, and each element is picked out by a tuple of n integers — one index per dimension. A 2-dimensional array is therefore addressed by pairs such as (3, 5); adding a third dimension means every element needs a triple, and so on for higher n.
Static and Dynamic Data Structures

What is a dynamic data structure?

Show the answer
A data structure that can grow and shrink while the program is running, requesting memory from the heap as new items are added and releasing it as items are removed, so its size is not fixed in advance. A linked list is the usual example.
Queues and Linear Queues

Give four typical uses of a queue.

Show the answer
A print spooler holding documents waiting for a printer; a buffer holding keystrokes or data waiting to be processed; the ready queue of processes waiting for the processor in an operating system; and the queue of vertices still to be visited in a breadth-first search.
Circular and Priority Queues

Describe how an item is added to a circular queue.

Show the answer
First test whether the queue is full; if it is, report overflow. Otherwise set rear = (rear + 1) MOD maxSize, store the new item at that position, and increase the size counter by one. The MOD operation makes the rear pointer wrap round to 0 after the last index.
Stacks

Describe the pop operation.

Show the answer
Pop removes the item at the top of the stack and returns it. First test whether the stack is empty; if it is, report stack underflow and do not remove. Otherwise take the item at the position given by the top pointer, then decrease the top pointer by one so that it points at the item beneath.
Graphs

Describe how an adjacency list represents a graph.

Show the answer
A collection of lists, one for each vertex, in which each list holds only the vertices that the vertex is directly connected to. For a weighted graph each entry stores the neighbour together with the weight of the edge to it. Nothing is stored for pairs of vertices that are not connected.
Trees

Define a binary tree.

Show the answer
A binary tree is a rooted tree in which each node has at most two children. A node may therefore have two children, one child, or none at all, but never three or more.
Hash tables

A hash table has 10 slots, indices 0 to 9, and uses h(k) = k MOD 10. Where are the keys 27, 13 and 82 stored?

Show the answer
27 MOD 10 = 7, so the item with key 27 goes in slot 7. 13 MOD 10 = 3, so key 13 goes in slot 3. 82 MOD 10 = 2, so key 82 goes in slot 2.

The 11 subtopics

One subtopic is one session. Work down the list.

Subtopic	What it covers	Questions
Data Structures and Abstract Data Types	Recall questions on what a data structure is, how it differs from an abstract data type and why a particular structure is chosen.	17
Static and Dynamic Data Structures	Recall questions on the difference between static and dynamic structures and on the advantages and disadvantages of each.	10
Queues and Linear Queues	Recall questions on what a queue is, its typical uses, the front and rear pointers and the working of a linear queue.	8
Circular and Priority Queues	Recall 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.	13
Stacks	Recall 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.	12
Graphs	Recall questions on vertices and edges, weighted, directed and undirected graphs, and the trade-off between an adjacency matrix and an adjacency list.	16
Trees	Recall questions on rooted and binary trees, parent, child and descendant, leaf nodes, and the ordering rule that governs a binary search tree.	13
Hash tables	Recall questions on hashing algorithms, working out where a key is stored, why collisions are unavoidable, and how rehashing resolves them.	12
Dictionaries	Recall 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.	9
Vectors and Their Notation	Recall questions on what a vector is, list and set notation for vectors, and the function interpretation.	10
Vector Arithmetic and Geometry	Recall questions on visualising a vector as an arrow, adding vectors, scalar multiplication and the dot product.	16

Fundamentals of Data Structures is 136 of the 1,516 questions in the guide.Get the guide, £9

How the guide is worked

Answering a question from memory stores it far better than reading the answer again. The guide runs that as a fixed procedure on one subtopic at a time, about twenty minutes a session.

Step 1 · Closed book
Cover the answers. Work through one subtopic and write down what you can. Leave blanks where you have nothing.
Step 2 · Open book
Go back to the top. Read each printed answer and write it out in full, including the ones you had right.
Step 3 · Closed book again
Same questions, same order, from memory. The gap between pass one and pass three is the session result.

Read the full method, the return schedule and the research behind it.