Advanced data structures (A Level) flashcards

Topic 10: Advanced data structures

Directed vs undirected vs weighted graphs

Undirected: edges work both ways. Directed: each edge points one way. Weighted: each edge has a value such as distance, time or cost.

When is an adjacency matrix better than an adjacency list?

Matrix: when the graph is dense, or edges are often added, removed or tested. List: when the graph is sparse (few edges relative to vertices), as it stores only each vertex's neighbours.

What is a tree, and what is a rooted tree?

A tree is a connected, undirected graph with no cycles; it does not need a root. A rooted tree has one vertex designated as the root, giving parent-child relationships.

What is a binary search tree?

A binary tree (each node has at most two children) in which, at every node, smaller values are in the left subtree and larger values in the right subtree.

What makes a good hash function?

It spreads records evenly across the table and is quick to compute. Using key MOD size keeps the result in the range 0 to size − 1.

What is a collision, and how does rehashing deal with it?

A collision is when two keys produce the same hash. Rehashing (the specification's method) stores the second record in the next available position.

Hash table vs array searched by key

A hash table calculates a record's position from its key, so no search is needed and inserting needs no shifting; but it needs spare space and records are not in key order. An array can be kept in order but must be searched.

What is a priority queue?

A queue in which each item has a priority: items are removed in priority order, and items of equal priority leave in arrival order. Used in Dijkstra's algorithm and job scheduling.

What is a dictionary?

A collection of key-value pairs in which each value is accessed by its key, e.g. a look-up table.