Linear search - Cambridge IGCSE Computer Science (Paper 2) Exam Questions

Practise 30 exam-style questions on Linear search for Cambridge IGCSE Computer Science (Paper 2). Write your answer as you would in the exam and get it marked in seconds against the mark scheme, point by point, with an AI tutor on hand if you get stuck.

30 questions
1–6 marks each
Instant marking
No sign-up needed

20 questions, marked as you go

Sample questions with model answers

Here are 4 of the questions in this topic, each with a model answer, an explanation of why it earns the marks and the mark scheme an examiner would use.

Question 1

1 mark

This pseudocode searches the array Names[1:25].

Index ← 0
Found ← FALSE
REPEAT
    Index ← Index + 1
    IF Names[Index] = SearchName
      THEN
        Found ← TRUE
    ENDIF
UNTIL Found OR Index = 25

SearchName is not stored in the array. State the value of Index when the loop ends.

Model answer

Explanation

Index is increased at the start of each pass, before the comparison, so on the last pass it becomes 25, Names[25] is checked, and then the condition Index = 25 ends the loop. It never reaches 26, unlike searches that increase the index after the comparison.

Mark scheme

1 mark
25
Do not accept 26

Question 2

2 marks

The array Surnames[1:8] holds "Patel", "Jones", "Smith", "Khan", "Brown", "Lee", "Smith", "Evans", in that order.

INPUT SearchName
Index ← 1
Found ← FALSE
WHILE Found = FALSE AND Index <= 8 DO
    IF Surnames[Index] = SearchName
      THEN
        Found ← TRUE
      ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found = TRUE
  THEN
    OUTPUT "Found at position ", Index
  ELSE
    OUTPUT "Not found"
ENDIF

The input is Smith. State the output and explain why position 7 is not output.

Model answer

Output: Found at position 3
When Smith is found at position 3, Found becomes TRUE, so the WHILE condition is false and the loop stops. Element 7 is never compared, so its position is not output.

Explanation

This linear search stops at the first match because Found is part of the loop condition. To report every position of a repeated value, the algorithm would have to keep searching to the end of the array, for example with a FOR loop that outputs each match.

Mark scheme

1 mark
Found at position 3
1 mark
The loop stops as soon as Found is set to TRUE at position 3, so element 7 is never checked / the search stops at the first match

Question 3

3 marks

The table shows the contents of the array Players[1:7].

INPUT Name
Name ← LCASE(Name)
Index ← 0
Found ← FALSE
REPEAT
    Index ← Index + 1
    IF LCASE(Players[Index]) = Name
      THEN
        Found ← TRUE
    ENDIF
UNTIL Found OR Index = 7
IF Found
  THEN
    OUTPUT Players[Index], " is in the squad"
  ELSE
    OUTPUT Name, " is not in the squad"
ENDIF

The algorithm is run three times. Give the output when the input is CARTER, when it is evans and when it is Hughes.

Array: Players. Table with columns "Index", "Players". Index: 1; Players: Ahmed | Index: 2; Players: Brooks | Index: 3; Players: Carter | Index: 4; Players: Doyle | Index: 5; Players: Evans | Index: 6; Players: Finch | Index: 7; Players: Grant.

Model answer

CARTER: Carter is in the squad
evans: Evans is in the squad
Hughes: hughes is not in the squad

Explanation

Both the input and each element are converted to lower case before comparing, so the search ignores case. When a match is found the element is output exactly as stored in the array; when no match is found the input is output, but by then it has been converted to lower case.

Mark scheme

1 mark
CARTER: Carter is in the squad
1 mark
evans: Evans is in the squad
Capital E, because the stored element is output
1 mark
Hughes: hughes is not in the squad
Lower case h, because Name was changed to lower case

Question 4

5 marks

Two one-dimensional arrays store a cafe's menu. ItemCodes[1:60] holds the code of each item and ItemPrices[1:60] holds its price, so the price of ItemCodes[n] is stored in ItemPrices[n].

Write pseudocode that inputs an item code, uses a linear search to find it, and outputs the price of the item. If the code is not found, output "Code not recognised".

Model answer

INPUT Code
Index ← 1
Found ← FALSE
WHILE NOT Found AND Index <= 60 DO
    IF ItemCodes[Index] = Code
      THEN
        Found ← TRUE
      ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found
  THEN
    OUTPUT "Price: ", ItemPrices[Index]
  ELSE
    OUTPUT "Code not recognised"
ENDIF

Explanation

Parallel arrays share the same index, so once the linear search has found the code at position Index, the price is simply ItemPrices[Index]. Only ItemCodes is searched; searching the prices would make no sense. Keep Index pointing at the match by increasing it only when there is no match.

Mark scheme

1 mark
MP1 inputs the item code
max 5
1 mark
MP2 initialises an index to 1 and a flag to FALSE (or equivalent) before the loop
1 mark
MP3 loop that stops when the code is found or after element 60 has been checked
1 mark
MP4 compares ItemCodes[Index] with the input code inside the loop
1 mark
MP5 increments the index when there is no match
1 mark
MP6 outputs ItemPrices[Index], using the same index as the matching code
1 mark
MP7 outputs "Code not recognised" once, after the loop, if the code was not found

Ready to try the rest? Every answer you write is marked against the mark scheme, so you can see exactly where the marks are.

AI Tutor Hints first, answers after you try

Hi! Stuck? Ask me for a hint and I’ll help you work it out. Once you’ve checked your answer I can explain exactly where the marks are.