A program stores five book codes in the list books. The algorithm uses a linear search to find a target code. List positions start at 0. The target is "Dune...
Question 1 Report
A program stores five book codes in the list books. The algorithm uses a linear search to find a target code. List positions start at 0. The target is "Dune".
01 found ← FALSE 02 position ← 0 03 REPEAT 04 IF books[position] = target THEN 05 [A] 06 ELSE 07 [B] 08 ENDIF 09 UNTIL found = TRUE OR position = 5 10 IF found = TRUE THEN 11 DISPLAY position 12 ELSE 13 DISPLAY "Not found" 14 ENDIF
The data in books is: Atlas, Cedar, Dune, Ember, Frost.
| position checked | book code | comparison result | new position |
|---|---|---|---|
| 0 | Atlas | FALSE | 1 |
| 1 | Cedar | FALSE | 2 |
| 2 | Dune | [C] | [D] |
(a) State the type of search used. [1]
(b) Complete cells [C] and [D] in the trace table. [2]
(c) Complete pseudocode lines [A] and [B]. [2]
(d) Give the two line numbers that set found to TRUE and then display the position. [2]
(e) Explain why the condition on line 09 includes both found = TRUE and position = 5. [3]
(f) Identify the target’s position and the number of comparisons made when the target is found. [2]
(g) If the target code is "Solar", state the final values of found and position, and the message displayed. [3]
Answer Details
(a) This is a linear search [1], because items are checked in order from position 0 onward.
(b) At position 2, books[2] is Dune, so the comparison is TRUE and the new position remains 2 [2]. It is not increased after a match.
(c) Line [A] is found ← TRUE; line [B] is position ← position + 1 [2]. A mismatch advances to the next item.
(d) The relevant line numbers are 05, which sets found to true, and 11, which displays the position [2].
(e) found = TRUE stops the search immediately once a match is located. position = 5 stops it after the five valid positions, 0 to 4, have been checked. This prevents trying to access position 5, which is outside the list [3].
(f) Dune is at position 2, found after 3 comparisons [2].
(g) For Solar, no item matches. The final values are found = FALSE and position = 5, so Not found is displayed [3].
Download The App On Google Playstore
Everything you need to excel in your exams
