AQA A Level · Computer Science 7517

Optimisation algorithms: Practice Questions

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

10 questions26 marksFree, no account

Question 1

1 mark

A programmer uses Dijkstra's shortest path algorithm to find the quickest route between two nodes in a network. Which of the following best describes how the algorithm handles a vertex once it has been 'visited'?

Question 2

1 mark

A specific graph-traversal algorithm is used to find the shortest path between a starting node and all other nodes in a weighted graph with non-negative edge weights. During the execution, the algorithm maintains a set of unvisited nodes and assigns each a 'tentative distance' value. Which of the following best describes the update step when the algorithm processes an unvisited neighbor \(V\) from the current node \(U\)?

Question 3

1 mark

An algorithm must find the shortest path between two nodes in a weighted graph with only positive edge weights. Which algorithm is most appropriate, and what is the typical graph-traversal strategy it employs?

Question 4

1 mark

Dijkstra's algorithm is used to find the shortest path in a graph. What is a specific requirement for the edge weights in the standard version of this algorithm?

Question 5

1 mark

In the context of optimisation algorithms, why might a heuristic method be used instead of an exact algorithm like Dijkstra's?

Question 6

2 marks

Dijkstra's algorithm is a well-known optimisation algorithm. Describe the specific condition that must be met by the edge weights in a graph for the standard version of Dijkstra's algorithm to successfully find the shortest path.

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

Question 7

3 marks

Explain the significance of Dijkstra's algorithm being categorized as an optimisation algorithm and state the primary goal it achieves when applied to a weighted graph.

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

Question 8

5 marks

A student is tracing Dijkstra's algorithm on a graph with nodes A, B, and C. If the current shortest distance to B is 10 and an edge (A, B) with weight 4 is processed while A has a distance of 3, describe the update step performed by the algorithm.

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

Question 9

5 marks

A researcher is using Dijkstra's algorithm to find the shortest path in a weighted graph representing a local delivery network.

(a) Describe the data structures required to implement Dijkstra's algorithm efficiently.
(b) Explain why Dijkstra's algorithm may fail to find the correct shortest path if the graph contains edges with negative weights.

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

Question 10

6 marks

Dijkstra's shortest path algorithm is a key optimisation algorithm for weighted graphs.

(a) Outline the general steps involved in Dijkstra's algorithm, focusing on how 'tentative distances' are updated.

(b) Explain the importance of using a priority queue (or similar data structure) to manage unvisited nodes to improve time complexity.

(c) Why does Dijkstra's algorithm require all edge weights to be non-negative? Explain what would happen if a negative edge weight were present.

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, marked as you go.