Fig. 1 shows an adjacency list for walking routes between cabins at an outdoor activity centre. Each list begins with a cabin and contains the cabins direct...
Question 1 Report
Fig. 1 shows an adjacency list for walking routes between cabins at an outdoor activity centre. Each list begins with a cabin and contains the cabins directly joined by a marked path. The route-planning program uses this graph structure because not every cabin is connected to every other cabin. A new path is planned from Cedar to Lake, so the manager needs to update the stored data before the map is displayed to visitors.
(a) Explain what the entry Lake in Pine's list means. [1]
(b) When a two-way path between Cedar and Lake opens, explain the updates required. [2]
The diagram shows a stack of undo commands in a tablet drawing program. The player has drawn several shapes, and the program stores each completed command so that the most recent action can be reversed. The top pointer is used by the undo subroutine. The designer chooses a stack rather than a queue because the order of removal must match the way users expect an undo button to work.
(a) Explain the command returned by one undo operation. [1]
(b) When the player chooses Redo after undoing a command, explain why the program may need a second stack. [2]
Answer Details
Adjacency list
(a) Lake appearing in Pine's list means there is a direct path, or edge, between Pine and Lake. [1]
(b) Because the new path is two-way, add Lake to Cedar's adjacency list and add Cedar to Lake's adjacency list. Both directions must be stored. [2]
Undo stack
(a) The top of the stack is the most recent command, so one undo operation returns add label. A stack removes items last in, first out. [1]
(b) An undone command must be retained rather than discarded if Redo is possible. It can be pushed onto a second, redo stack, then popped from that stack and applied again when the player chooses Redo. [2]
Download The App On Google Playstore
Everything you need to excel in your exams
