Graphs and How to Store Them · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.
En anglais

Storing maps as matrices or lists

Computing · Algorithms & Data Structures · ages 17-18
Name ______________________   Date ____________

  1. A road allows travel from Depot to Park, but not from Park to Depot. Which edges model its permitted travel?

    • Only Park to Depot
    • Only Depot to Park
    • Both directions at once
    • Neither direction at all

  2. A directed matrix uses columns P, Q, R, S and 1 for an edge. Row R is 1, 0, 0, 1. Which adjacency-list entry matches this row?

    • R: Q, R
    • R: Q, S
    • R: P, S
    • R: P, Q

  3. A directed matrix uses columns U, V, W. Its rows are U: 0, 0, 1; V: 1, 0, 1; W: 0, 0, 0. With 1 meaning an edge, how many edges end at W?

    Answer: ______________

  4. A directed graph has edges E to G, F to G, G to E and G to H. What is G's adjacency-list entry?

    • G: E, F
    • G: E, H
    • G: F, H

  5. A directed graph has 100 nodes and 9900 edges. Compare a full matrix using 1 bit per cell with a list using 32 bits per neighbour ID. Ignore list overhead. Which uses fewer bits?

    • Matrix: 10000 bits
    • List: 316800 bits
    • They use equal space

  6. An undirected graph has no self-loops. Its list is A: B, D; B: A, C; C: B, D; D: A, C. How many edges does it have?

    Answer: ______________

  7. A weighted matrix uses null for no road and a number for a road's distance. A cell containing 0 must mean there is no road.

    Circle one:   True   False

  8. Node indices are known. You often ask whether a directed edge S to T exists. Which operation checks this without scanning neighbour entries?

    • Scan every node's unsorted neighbour list
    • Read row T and column S in the matrix
    • Count all entries in S's neighbour list
    • Read row S and column T in the matrix

  9. A directed graph's adjacency list reads A: B, C; B: C; C: none. How many directed edges does it contain?

    Answer: ______________

  10. A route map shows roads from Ashcombe to Bridgeton (5 km) and from Bridgeton to Cliffwood (8 km). What are 5 and 8?

    • Node names
    • Edge counts
    • Edge weights
LightMySky · lightmysky.comW1-mt_tSO-F1sTuu-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Storing maps as matrices or lists W1-mt_tSO-F1sTuu-s1

  1. Only Depot to Park · The road permits one direction, so use a directed edge from Depot to Park.
  2. R: P, S · The 1s are in columns P and S, so R has outgoing edges to P and S.
  3. 2 · Column W contains 1, 1, 0. The two 1s record U to W and V to W.
  4. G: E, H · G points directly to E and H. F points into G, so F is not an outgoing neighbour of G.
  5. Matrix: 10000 bits · The matrix uses 100 times 100 = 10000 bits. The list's IDs alone use 9900 times 32 = 316800 bits.
  6. 4 · There are 8 neighbour entries. Every undirected edge appears at both endpoints, so 8 divided by 2 gives 4 edges.
  7. False · Under this convention, null means no road. The number 0 is a road weight and does not mean absence.
  8. Read row S and column T in the matrix · Use the source as the row and destination as the column. Cell (S, T) checks the requested edge directly.
  9. 3 · Count each listed destination once: A has 2, B has 1 and C has 0, giving 3 edges.
  10. Edge weights · Numbers attached to edges are weights, here distances.
Worksheet · LightMySky