Flashcards · 7517 · Topic 2

Fundamentals of data structures flashcards

39 cards on Topic 2, subtopics 4.2.1.1 to 4.2.8. 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 39 cards

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

4.2.1.1 Data structures

What is a data structure?: A way of organising, storing and accessing data so that it can be used efficiently for a given task.
What is the difference between a static and a dynamic data structure?: Static: fixed size, set when it is created (e.g. an array). Dynamic: grows and shrinks as the program runs, using memory from the heap (e.g. a linked list).
What are the advantages and drawbacks of static and dynamic structures?: Static: no pointers needed and memory is known in advance, but space may be wasted or run out. Dynamic: uses only the memory needed, but pointers take space and memory can run out at run time.

4.2.1.2 Single- and multi-dimensional arrays (or equivalent)

What does a 1-D array represent, and what does a 2-D array represent?: A 1-D array is useful for a vector (a single ordered list, one index). A 2-D array is useful for a matrix (rows and columns, two indices).
What is an n-dimensional array?: A set of elements of the same data type, indexed by a tuple of n integers (one index per dimension).
What is the difference between an array’s dimensionality and its size?: Dimensionality: how many indices locate one element. Size: how many elements it holds in total. A 7 × 3 array is 2-D and holds 21 elements.

4.2.1.3 Fields, records and files

What are a field, a record and a file?: Field: one item of data about something (e.g. Surname). Record: a set of related fields about one item. File: a collection of records stored in secondary storage.
What is the difference between a text file and a binary file?: A text file stores data as characters and can be read in a text editor. A binary file stores data in the same binary form as in memory (e.g. records of integers and reals) and is not human-readable.
What are the steps to read data from a file in a program?: Open the file for reading, read records in a loop until the end of file is reached, then close the file.

4.2.1.4 Abstract data types/data structures

What is an abstract data type?: A data type defined by the values it holds and the operations on it, without saying how it is implemented.
Name the abstract data types in the AQA A-level specification.: Queue, stack, graph, tree, hash table, dictionary and vector.
Why is the idea of an abstract data type useful?: Programs can use the operations (e.g. push and pop) without depending on the implementation, so the implementation can change without changing the code that uses it.

4.2.2 Queues

How does a queue work?: First in, first out (FIFO): items are added at the rear (enqueue) and removed from the front (dequeue).
What is the difference between a linear and a circular queue?: Linear: front and rear pointers only move forward, so freed space at the start of the array is not reused. Circular: the rear wraps round to the start of the array when it reaches the end, reusing space.
What is a priority queue?: A queue in which each item has a priority; items with higher priority are removed first, and items of equal priority leave in FIFO order.
What should enqueue and dequeue check first?: Enqueue: test whether the queue is full. Dequeue: test whether the queue is empty.

4.2.3 Stacks

How does a stack work?: Last in, first out (LIFO): items are pushed onto and popped off the top, tracked by a top-of-stack pointer.
What do the push, pop and peek operations do?: Push adds an item to the top. Pop removes and returns the top item. Peek returns the top item without removing it.
What are stack overflow and stack underflow?: Overflow: pushing onto a stack that is already full. Underflow: popping from an empty stack.
Give three uses of a stack.: Storing return addresses and local variables for subroutine calls, evaluating Reverse Polish expressions, and undo operations.

4.2.4 Graphs

What are a graph, a weighted graph and a directed graph?: Graph: vertices (nodes) joined by edges (arcs). Weighted: each edge has a value such as distance. Directed: edges go one way only.
What is an adjacency matrix?: A 2-D array where the entry in row i, column j shows whether there is an edge from vertex i to vertex j (or its weight).
What is an adjacency list?: For each vertex, a list of the vertices it is joined to (with weights if weighted).
When is an adjacency matrix better than an adjacency list?: A matrix suits a dense graph with many edges and gives quick edge look-up. A list suits a sparse graph, as it stores only the edges that exist and uses less memory.

4.2.5 Trees

What is a tree?: A connected, undirected graph with no cycles.
What is a rooted tree?: A tree with one vertex chosen as the root; every edge leads away from the root, giving parent–child relationships.
What is a binary tree?: A rooted tree in which each node has at most two children.
What is a binary search tree used for?: Storing items in order so they can be searched quickly: every left descendant is smaller than a node and every right descendant larger.

4.2.6 Hash tables

What is a hash table?: A data structure in which a hashing algorithm calculates the storage position of each item from its key, so items can be found almost immediately.
What is a collision in a hash table?: When two different keys hash to the same position.
How can collisions be handled?: Rehashing (e.g. store the item in the next free position, open addressing) or chaining (each position holds a list of the items that hash to it).
What makes a good hashing algorithm?: It is quick to calculate, spreads keys evenly over the table, and produces few collisions.

4.2.7 Dictionaries

What is a dictionary data structure?: A collection of key–value pairs in which each value is looked up by its unique key.
Give a use of a dictionary.: Dictionary-based compression, such as counting or storing words and their codes; or storing settings by name.
What are the main operations on a dictionary?: Add a key–value pair, retrieve the value for a key, and delete a pair.

4.2.8 Vectors

How can a vector be represented?: As a list of numbers, as a function, or as a geometric point (arrow) in space. A vector over ℝ with n components is written as ℝⁿ.
What is the result of adding two vectors and scaling a vector?: Addition gives a translation: add the components, e.g. [1, 2] + [3, 4] = [4, 6]. Scalar multiplication gives a scaling: 2 × [1, 2] = [2, 4].
How is the dot product of two vectors calculated?: Multiply matching components and add: [1, 2] · [3, 4] = 1 × 3 + 2 × 4 = 11.
What can the dot product be used for?: Finding the angle between two vectors, and calculating a parity bit (the dot product of the bits with a vector of 1s, over modulo 2).