IB Questionbank

User interface language: English | Español

Date	May 2022	Marks available	5	Reference code	22M.1.SL.TZ0.14
Level	SL	Paper	1	Time zone	no time zone
Command term	Evaluate	Question number	14	Adapted from	N/A

Question

The array DATA_ARR[] is a one-dimensional array of 12 integers.

Algorithm 1 represents a method of searching the array DATA_ARR[] to see if it contains a specific value.

Algorithm 1

input TO_FIND
LIMIT = 11
LOC = FALSE
ITERATE = 0
loop while not LOC and ITERATE <= LIMIT
    if DATA_ARR[ITERATE] = TO_FIND then
        LOC = TRUE
    end if
    ITERATE = ITERATE + 1
end loop
if LOC then
    output TO_FIND, "is in the array"
else
    output TO_FIND, "is NOT in the array"
end if

Algorithm 2 represents an alternative method of searching the array DATA_ARR[] to see if it contains a specific value.

Algorithm 2

input TO_FIND
LOC = FALSE
LOW_LIM = 0
UP_LIM = 11
loop while LOW_LIM <= UP_LIM and LOC = FALSE
    MID_VAL = (LOW_LIM + UP_LIM) div 2
        if DATA_ARR[MID_VAL] = TO_FIND then
            LOC = TRUE
        else
            if TO_FIND < DATA_ARR[MID_VAL] then
                UP_LIM = MID_VAL - 1
            else
                LOW_LIM = MID_VAL + 1
            end if
        end if
end loop
if LOC = TRUE then
    output TO_FIND, "is in the array"
else
    output TO_FIND, "is NOT in the array"
end if

Copy and complete the trace table for Algorithm 1 using TO_FIND = 39.

The first value of the first row has been done for you.

[4]

State the constant used in Algorithm 1.

[1]

Copy and complete the trace table for Algorithm 2 using TO_FIND = 50.

The first two values of the first row have been done for you.

[4]

Outline why MID_VAL could not be a constant.

[1]

Evaluate the use of a sequential search and a binary search including the advantages and disadvantages of each.

[5]

Markscheme

Award [4 max].
Award [1] for TO_FIND and LOC columns;
Award [1] for ITERATE column;
Award [1] for DATA_ARR[ITERATE] column;
Award [1] for the correct output;

Award [1 max].
LIMIT

Award [4 max].
Award [1] for LOW_LIM column;
Award [1] for UP_LIM column;
Award [1] for MID_VAL and DATA_ARR[MID_VAL] columns;
Award [1] for TO_FIND, LOC and Output columns;

Award [1 max].
The value (of MID_VAL) changes during the operation of the algorithm;

Award [5 max].

Award [3 max] for sequential search
The algorithm searches through every element in the array starting at the beginning and working through one after the other;
…until the required item is found;
This method is potentially slow if the data set is large and the required element is towards the end of the list;
The data does not need to be in any particular order;

Award [3 max] for binary search
The data must be sorted before it is stored;
After comparing the data set with the target data, half of the data can be discounted using a simple condition;
…enabling the target to be more quickly located;

Note to examiners: Big O notation is not on the syllabus so answers with reference to this are not expected, however, if this type of answer is seen, please allow, for example:

Sequential: main disadvantage is O(N) so inefficient;
advantage is that it works with an unsorted array;
Binary search: main advantage is that it’s efficient as it’s O(log n);
disadvantage is that the array must be sorted (and so must be sortable – not all data has a defined sort order);
Binary search cannot be performed on a linked list but a sequential search can;

Examiners report

Candidates generally constructed the correct trace table for this question; however, marks were often lost by not providing the correct quantity of iterations for the trace, or by making errors in how the output would actually appear if the program ran.

The vast majority of candidates correctly identified LIMIT as the constant in the algorithm.

Candidates generally performed less well on the trace for the second algorithm (binary search), with similar errors to the trace carried out in part (a). Also, as this algorithm required more processing, additional errors included incorrect calculations of the variables, leading to incorrect values being displayed in the trace table.

The vast majority of candidates gave an appropriate reason why the variable MID_VAL could not be a constant in the given algorithm.

Virtually all candidates were able to evaluate the use of a sequential and a binary search, with many of these candidates achieving high or full marks. One point that was often missing form candidates’ responses, however, which is fundamental to the topic, was the need for the data to be sorted/ordered for a binary search to work.

Syllabus sections

Topic 4: Computational thinking, problem-solving and programming » 4.2 Connecting computational thinking and program design

Show 59 related questions

18M.1.SL.TZ0.12a:

The collection DATA contains the following data:

2, 4, 1, −2, −4, 1, 0

Consider the following pseudocode:

COUNTER = 0
SUM = 0
DATA.resetNext()
loop for X from 0 to 6
  if DATA.getNext() > 0
    ARRAY[X] = DATA.getNext()
    COUNTER = COUNTER + 1
    SUM = SUM + ARRAY[X]
  end if
end loop
output SUM/COUNTER

Trace the pseudocode using the table below:

18N.1.SL.TZ0.7:

Construct a trace table for the following algorithm

A = 3
B = 7
loop while B >= A
  A = A + 1
  output(B − A)
  B = B − 1
end loop

19N.1.SL.TZ0.7:

Construct a trace table for the following algorithm.

K = 1
N = 1
M = 2
loop while K < 5
   output(N,M)
   K = K + 1
   N = N + 2
   M = M * 2
end loop

21M.1.SL.TZ0.8:

List the output from the given algorithm for the following input.

2, 6, 8, 9, 12, 15, 18, 20

loop for Count from 0 to 7
    input NUMBER
    if NUMBER div 2 = NUMBER / 2 then
        if NUMBER div 3 = NUMBER / 3 then
        output NUMBER
        end if
    end if
end loop

19N.1.SL.TZ0.10a:

Consider the following algorithm.

N = 372
X = N DIV 100
Y = X + 10 * (N MOD 100 DIV 10)
Z = Y + (N MOD 10) * 100

Determine the values of variables X, Y, and Z after execution of this algorithm. Show your working.

19M.2.SL.TZ0.4b:
Using the rules and initial values above, construct the pseudocode that would enable the area of the sea ice and the sea level rise to be calculated if there was an increase of 0.04 °C in the ocean surface temperature.

Hide related questions

Topic 4: Computational thinking, problem-solving and programming

Question

Markscheme

Examiners report

Syllabus sections

View options