Lesson 4.3.1.1

4.3.1.1 Breadth-first and depth-first search Quiz: AQA Computer Science, Unit 3

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 4.3.1.1, Breadth-first and depth-first search: 20 multiple choice questions for the AQA Computer Science (7517), Unit 3: Fundamentals of algorithms, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. Which search algorithm finds the shortest path in an unweighted graph?

    • Bubble sort
    • Breadth-first search
    • Binary search
    • Depth-first search, which explores each branch fully before backtracking

  2. Which data structure does breadth-first search typically use to hold nodes waiting to be explored?

    • A stack
    • A heap only
    • A queue
    • A binary search tree

  3. Which data structure does depth-first search typically use to hold nodes waiting to be explored?

    • A hash table
    • A queue
    • A binary heap that keeps the largest value at the top of the structure
    • A stack, either explicit or through recursion

  4. Which application of depth-first search is named in the specification?

    • Finding the shortest route on a weighted map
    • Sorting a list of numbers
    • Compressing an image
    • Navigating a maze

  5. Which statement about breadth-first search on an unweighted graph is correct?

    • It requires weights on every edge
    • It only works on trees
    • It explores nodes level by level, so the first time a node is reached uses the fewest edges from the start
    • It always finds the path with the most edges

  6. Which search goes as deep as possible along one path before backtracking?

    • Binary search
    • Linear search
    • Depth-first search
    • Breadth-first search

  7. In breadth-first search, which node is removed from the queue next?

    • The node with the largest label
    • A randomly chosen node
    • The most recently added node
    • The node that was added earliest

  8. Graph edges: A-B, A-C, B-D, C-D, D-E. Starting at A and taking neighbours in alphabetical order, what is the breadth-first visit order?

    • A, B, D, C, E
    • A, B, C, E, D
    • A, E, D, C, B
    • A, B, C, D, E

  9. Using the same graph (A-B, A-C, B-D, C-D, D-E), starting at A and taking neighbours alphabetically, what is the depth-first visit order?

    • A, C, B, D, E
    • A, B, E, D, C
    • A, B, C, D, E
    • A, B, D, C, E

  10. In the same graph, what is the shortest number of edges from A to E?

    • 1
    • 4
    • 3
    • 2

  11. Why is depth-first search a natural choice for finding any exit from a maze?

    • It explores all corridors at the same distance first
    • It requires the maze to be a weighted graph
    • It always gives the shortest exit route
    • It follows one route to a dead end, then backtracks

  12. Breadth-first search first reaches node T at level 3 from start S. Can a path from S to T with fewer edges exist?

    • No, but only if the graph is a tree
    • Yes, whenever the graph contains cycles
    • Yes, because breadth-first search skips over some of the edges that link nodes
    • No, the first discovery of T gives its shortest edge distance from S

  13. Breadth-first search starts at S. S has neighbours X and Y, and X has neighbour Z. After S and then X are processed, which nodes are in the queue?

    • X and Y
    • S, X, Y and Z
    • Y and Z
    • Z only

  14. A depth-first search uses an explicit stack. S has neighbours X then Y pushed in that order. Which node is popped next?

    • X
    • Z
    • Y
    • S

  15. A connected graph has 10 nodes. How many nodes does a breadth-first search from any start node visit?

    • 11
    • 10
    • 9
    • It depends on the start node and can be fewer than 10

  16. Why must a graph search record which nodes have been visited?

    • To sort the nodes into order
    • To avoid revisiting nodes endlessly when a cycle exists
    • To convert the graph into a tree
    • To count the number of edges

  17. What is the time complexity of breadth-first or depth-first search on a graph with V vertices and E edges, using adjacency lists?

    • O(V^2)
    • O(E log V) always
    • O(V + E)
    • O(2^V)

  18. Which statement about depth-first search is correct?

    • It always finds the shortest path between two nodes
    • It requires a queue rather than a stack
    • It cannot be used on directed graphs
    • Its visit order depends on the order neighbours are explored, and it does not guarantee shortest paths in unweighted graphs

  19. A graph of 6 nodes has two connected components, one of size 4 and one of size 2. How many nodes does a search started in the size-4 component visit?

    • It depends on the edge weights
    • 2
    • 6
    • 4

  20. Which graph algorithm should be used for shortest paths when edges have different positive weights?

    • Binary tree search, because it orders the weights
    • Dijkstra's algorithm, because breadth-first search counts edges, not weights
    • Depth-first search, because it respects weights
    • Breadth-first search, because it always gives the least total weight and uses queues

All AQA Computer Science quizzes