AQA A Level · Computer Science 7517

Graph-traversal: Practice Questions

5 multiple-choice questions marked as you go, and 5 written questions with worked solutions. All on Graph-traversal.

10 questions25 marksFree, no account

Question 1

1 mark

In the context of graph-traversal, which algorithm is best suited for finding the shortest path between two nodes in an unweighted graph?

Question 2

1 mark

In an unweighted graph, a student needs to find the shortest path between two nodes. Which graph-traversal algorithm should they use, and which primary data structure is used to manage the nodes that are discovered but not yet visited to ensure this shortest path property is maintained?

Question 3

1 mark

Consider a directed graph where a Depth-First Search (DFS) is implemented. During the traversal, an edge is encountered that points from the current node to an ancestor currently in the recursion stack. What property of the graph does this specific edge identify?

Question 4

1 mark

In the context of graph-traversal, which algorithm is typically used to find the shortest path between two nodes in an unweighted graph?

Question 5

1 mark

A developer is using graph-traversal to solve a puzzle. The search space is modeled as a tree where the target node is known to be very close to the root, but the tree itself is infinitely deep. Which algorithm is guaranteed to find the target, and why?

Question 6

2 marks

In an undirected, unweighted graph, which specific traversal algorithm is most suitable for finding the shortest path between two given vertices?

Write your answer out first, then check it against the worked solution.

Question 7

3 marks

A depth-first search (DFS) is applied to a graph. Describe a specific real-world scenario mentioned in the syllabus where this traversal method is commonly used.

Write your answer out first, then check it against the worked solution.

Question 8

5 marks

During a Breadth-first search on an unweighted graph, a queue is used to manage vertices. Explain the relationship between the distance from the start node and the order in which vertices are added to this queue.

Write your answer out first, then check it against the worked solution.

Question 9

4 marks

A graph contains 5 nodes (A, B, C, D, E) and the following undirected edges: (A,B), (A,C), (B,D), (C,E).

(a) Trace a Breadth-First Search (BFS) starting at node A. Assume nodes are visited in alphabetical order where a choice exists.
(b) Identify a typical application for a Breadth-First Search in an unweighted graph.

Write your answer out first, then check it against the worked solution.

Question 10

6 marks

A Depth-First Search (DFS) and Breadth-First Search (BFS) are used to explore a graph representing a set of connected islands.

(a) Describe the specific application for BFS in an unweighted graph and why it is more suitable than DFS for this purpose.

(b) Explain the role of stack frames in a recursive implementation of DFS.

(c) Compare the space complexity of BFS and DFS when traversing a graph that is very 'wide' (high branching factor) but has a shallow depth.

Write your answer out first, then check it against the worked solution.

* The content provided by thinka is generated by AI and may not always be accurate or up-to-date. Please use it as a supplementary resource and verify with official materials.

You've seen the model answer. Now get yours marked.

This page can show you how a good answer looks. It cannot tell you what your answer was missing. thinka marks your written work against the real mark scheme in about 15 seconds.

Get My Answers Marked Back to the notes

Want more questions like these? Get a fresh set on this topic, graded as you go.