Static and dynamic data structures: arrays and lists – IB Computer Science exam questions with mark scheme

1Core4 marks

Arrays in Java are static data structures, whereas a Python list or a Java ArrayList is dynamic.

(a) Define the term static data structure. [1]

(b) Compare dynamic and static data structures in terms of memory allocation, resizing and memory use. [3]

(a) A data structure whose size (number of elements / memory allocated) is fixed when it is created / declared and cannot change while the program runs; accept 'size fixed at compile time'(1)
(b) Memory allocation: a static structure's memory is allocated once, in advance (often as one contiguous block), whereas a dynamic structure's memory is allocated and released while the program runs (at run time) as elements are added or removed(1)
(b) Resizing: a dynamic structure can grow or shrink during execution, whereas a static structure cannot change size(1)
(b) Memory use: a static structure may waste memory when not full (or overflow when full), whereas a dynamic structure uses only (about) the memory it needs; accept: a dynamic structure may need extra memory for overhead such as references / spare capacity(1)
Answer: (a) Size fixed when created. (b) Allocation: dynamic at run time vs static once in advance; resizing: dynamic can grow/shrink, static cannot; memory use: static may waste unused space, dynamic uses about what it needs (with some overhead).
Examiner tip: 'Static' does not mean the values cannot change: the contents of an array can be updated, it is the size that is fixed.

2Core3 marks

Consider the following Python code.

scores = [12, 7, 19, 4]
scores.append(10)
scores.insert(1, 15)
scores.remove(19)
last = scores.pop()
print(scores)
print(len(scores), last)

State the exact output of this code. [3]

Line 1 begins [12, 15 ... (15 inserted at index 1, so before 7)(1)
Line 1 is exactly [12, 15, 7, 4] (19 removed by value, 10 removed by pop)(1)
Line 2 is 4 10; allow follow-through for len and last from an incorrect list(1)
Answer: [12, 15, 7, 4]
4 10
Examiner tip: remove(19) removes the value 19, not the item at index 19; pop() with no argument removes and returns the last item.

3Standard6 marks

A multi-storey car park records which bays are occupied in a 2D Python list park. Each inner list is one level; park[level][bay] is 1 if the bay is occupied and 0 if it is free. The contents are shown in the diagram.

(a) State the value of park[1][3]. [1]

(b) State the value of park[2][0]. [1]

(c) Construct a Python function count_free(park) that uses nested loops to return the total number of free bays in the car park. Your function must work for any number of levels and any number of bays per level. [4]

(a) 0(1)
(b) 1(1)
(c) Function header with parameter, and a counter initialised to 0 (before the loops)(1)
(c) Outer loop over every level (e.g. for level in park / for r in range(len(park)))(1)
(c) Inner loop over every bay in that level, with a test for == 0 that increments the counter; must index the correct element, e.g. park[r][b] or bay == 0(1)
(c) Returns the counter after both loops have finished (not inside a loop); do not award if the bounds are hard-coded as 3 and 5(1)

Answer: (a) 0 (b) 1 (c) e.g.

def count_free(park):
    free = 0
    for level in park:
        for bay in level:
            if bay == 0:
                free = free + 1
    return free

For the data shown it returns 6.

Examiner tip: Hard-coding range(3) and range(5) loses the mark for general bounds; use len(park) and len(park[r]) or iterate over the lists directly.

Stuck on Static and dynamic data structures: arrays and lists?

Get it sorted in a free 30-minute session

We work through your weakest questions on this topic on Zoom. I reply the same day.

Free 30-min session on this topic Send me 5 questions a day

4Standard5 marks

Consider the following Java code.

ArrayList<String> playlist = new ArrayList<>();
playlist.add("Rain");
playlist.add("Echo");
playlist.add("Drift");
playlist.add(1, "Bloom");
playlist.remove(2);
playlist.set(0, "Flare");
System.out.println(playlist.get(1));
System.out.println(playlist.size());

(a) State the output of this code. [2]

(b) A programmer instead declares String[] tracks = new String[3]; and later executes tracks[3] = "Bloom";

Explain why this statement fails, whereas the call playlist.add("Bloom") succeeds even though playlist already holds three elements. [3]

(a) Bloom (first line)(1)
(a) 3 (second line)(1)
(b) The array has a fixed size of 3, so its valid indices are 0 to 2 only(1)
(b) Index 3 is out of bounds, so an ArrayIndexOutOfBoundsException is thrown / run-time error; accept 'there is no element 3'(1)
(b) An ArrayList is dynamic: add() increases its size automatically (allocating more memory as needed), so a new element can be appended at the end; accept: the ArrayList copies its contents into a larger internal array when it is full; do not award this mark for a point about the array alone (e.g. 'an array's size cannot change'), which is credited in the first (b) mark(1)
Answer: (a) Bloom then 3. (b) The array has length 3 so indices are 0–2; tracks[3] is out of bounds (ArrayIndexOutOfBoundsException) because an array cannot grow, whereas an ArrayList resizes itself when add() is called.
Examiner tip: remove(2) removes by index in an ArrayList<String> when given an int; track the list after each line rather than guessing.

5Standard4 marks

A weather station program stores temperature readings in a static 2D array of integers with 200 rows and 150 columns. Each integer occupies 4 bytes.

(a) Calculate the memory, in bytes, reserved for this array. [2]

(b) On a typical day only 30% of the array's elements contain readings. Calculate the number of bytes reserved for elements that are not used. [1]

(a) 200 × 150 (= 30 000 elements) × 4 seen(1)
(a) 120 000 (bytes); accept 120 kB / 117.2 KiB only if 120 000 bytes is also shown(1)
(b) 84 000 (bytes) (0.7 × 120 000); allow follow-through from (a)(1)
(c) A dynamic structure grows as readings arrive, so memory is only allocated for readings that exist / no memory is wasted on unused elements; ignore 'it is faster'(1)
Answer: (a) 120 000 bytes (b) 84 000 bytes (c) memory is allocated only as readings are added, avoiding the 84 000 wasted bytes.
Examiner tip: A static array reserves memory for every element when it is created, whether or not the element is ever used.

6Hard5 marks

The following Python code is intended to remove every even number from the list nums.

nums = [3, 8, 8, 5, 6, 10]
i = 0
while i < len(nums):
    if nums[i] % 2 == 0:
        nums.pop(i)
    i = i + 1
print(nums)

(a) State the output of this code. [1]

(b) Explain why the code does not work as intended. [2]

(a) [3, 8, 5, 10](1)
(b) When an element is removed, every later element shifts one position to the left (down one index)(1)
(b) i is still incremented, so the element that moved into position i is never checked / is skipped (e.g. the second 8 and the 10)(1)
(c) Only increment i when no element was removed (put i = i + 1 in an else branch); accept: traverse the list backwards from the last index(1)
(c) So that the element shifted into position i is tested on the next iteration / every element is checked; accept as alternative for both marks: build a new list containing only the odd values (e.g. new = [n for n in nums if n % 2 != 0]) so the list being traversed is not changed(1)
Answer: (a) [3, 8, 5, 10] (b) pop shifts later items left but i still advances, so the item that moved into index i is skipped. (c) e.g. put i = i + 1 in an else, giving [3, 5].
Examiner tip: Changing the length of a list while traversing it by index is a classic bug: always ask what happens to the indices of the remaining elements.

7Hard6 marks

Two Python lists, a and b, each contain integers in ascending order. For example, a = [4, 9, 15, 22] and b = [1, 9, 30].

Construct a Python function merge(a, b) that returns a new list containing every element of both lists in ascending order. For the example it would return [1, 4, 9, 9, 15, 22, 30].

You must not use any built-in sorting function, and either list may be empty. [6]

Creates an empty result list and two index variables (or equivalent pointers) set to 0(1)
Loop that continues while both indices are within their lists (i < len(a) and j < len(b))(1)
Compares a[i] with b[j] and appends the smaller value to the result(1)
Increments only the index of the list whose element was appended(1)
After the loop, appends all remaining elements of whichever list is not finished (e.g. result.extend(a[i:]) and result.extend(b[j:]) or two further loops); this also handles an empty list(1)
Returns the result list; do not award if a or b is modified/sorted with sort()/sorted(); duplicates (e.g. both 9s) must both be kept(1)

Answer: e.g.

def merge(a, b):
    result = []
    i = 0
    j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i = i + 1
        else:
            result.append(b[j])
            j = j + 1
    while i < len(a):
        result.append(a[i])
        i = i + 1
    while j < len(b):
        result.append(b[j])
        j = j + 1
    return result

Examiner tip: Most lost marks come from forgetting the leftover elements once one list runs out, so test your code with one list empty.

8Hard4 marks

A developer must choose a data structure for each of the following situations.

Situation A: storing the 64 squares of a chessboard in a board-game program.

Situation B: storing the items a customer adds to and removes from an online shopping basket.

For each situation, identify whether a static or a dynamic data structure is more appropriate and justify your choice. [4]

A: static (e.g. a fixed 8 × 8 2D array)(1)
A justification: the number of squares never changes (always 64), so the size is known in advance and no memory is wasted; accept: fast direct access by index (row, column) with no resizing overhead(1)
B: dynamic (e.g. Python list / Java ArrayList)(1)
B justification: the number of items is unknown and changes while the program runs, so the structure must grow and shrink / avoids reserving memory for a maximum basket size or running out of space; no mark for the choice without a justification linked to the context(1)
Answer: A: static, as the size is fixed at 64. B: dynamic, as items are added and removed so the size changes and is not known in advance.
Examiner tip: Each justification must refer to the scenario (a fixed 64 squares; an unpredictable number of basket items), not just repeat a generic definition.

9Stretch6 marks

A shop chain stores the number of units sold in a Java 2D array sales. Each row is a branch and each column is a month, so sales[branch][month] holds one value. The data is shown in the diagram.

(a) Calculate the total units sold in month 1 across all branches. [1]

(b) Construct the Java method below so that it returns the index of the month with the highest total sales across all branches. Assume every row has the same number of columns and that there are no ties. [5]

public static int bestMonth(int[][] sales) {
    // to be completed
}

(a) 57 (9 + 17 + 11 + 20)(1)
(b) Outer loop over the columns/months, using sales[0].length (not hard-coded 3)(1)
(b) Running total reset to 0 for each month (inside the outer loop)(1)
(b) Inner loop over the rows/branches (sales.length) adding sales[r][c] to the total; indices must be in the order [row][column](1)
(b) Compares the month total with the best total so far and, if greater, updates both the best total and the best index; best total must be initialised sensibly (e.g. -1, 0 or the total of month 0)(1)
(b) Returns the index (not the total) after all months have been processed; accept equivalent code storing totals in a 1D array then finding the index of the maximum(1)

Answer: (a) 57 (b) e.g.

public static int bestMonth(int[][] sales) {
    int best = 0;
    int bestTotal = -1;
    for (int c = 0; c < sales[0].length; c++) {
        int total = 0;
        for (int r = 0; r < sales.length; r++) {
            total = total + sales[r][c];
        }
        if (total > bestTotal) {
            bestTotal = total;
            best = c;
        }
    }
    return best;
}

For the data shown it returns 1.

Examiner tip: Summing a column means the column index stays fixed in the outer loop while the row index changes in the inner loop; swapping them sums branches instead of months.

10Stretch6 marks

A sensor program uses a fixed-size list readings of capacity 8 to simulate a static array. The variable count holds how many positions are in use, and the used positions are kept in ascending order. The diagram shows the current state.

def insert_sorted(readings, count, value):
    pos = count - 1
    while pos >= 0 and readings[pos] > value:
        readings[pos + 1] = readings[pos]
        pos = pos - 1
    readings[pos + 1] = value
    return count + 1

(a) The call count = insert_sorted(readings, count, 10) is made. State the contents of positions [0] to [5] of readings afterwards, and the number of elements that were shifted. [2]

(b) A further call count = insert_sorted(readings, count, 1) is then made. State how many elements are shifted. [1]

(c) The function does not check whether the array is full. Explain what would happen if it were called when count is 8, and state the check that should be added. [2]

(d) With reference to your answers to (a) and (b), outline why inserting into the front of an array is slower than appending to the end. [1]

(a) 3, 8, 10, 12, 17, 25(1)
(a) 3 elements shifted (25, 17 and 12)(1)
(b) 6 (all elements in use are shifted)(1)
(c) readings[pos + 1] would be index 8, which is outside the array (capacity 8, indices 0–7), causing an index out of range error / IndexError; accept 'overflow'(1)
(c) Check before shifting: if count == len(readings) (or count >= 8) then do not insert / report that the array is full(1)
(d) Inserting at the front requires every existing element to be moved one place (n shifts, linear time / O(n)), whereas appending at the end needs no shifts (constant time / O(1))(1)
Answer: (a) 3, 8, 10, 12, 17, 25; 3 shifts (b) 6 shifts (c) writing to index 8 is out of bounds (IndexError); add a check that count < 8 before inserting (d) front insertion moves all n elements, the end needs none.
Examiner tip: Count shifts by checking which elements are greater than the new value; every one of them moves exactly one place to the right.

Stuck on this topic?

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.

Free 30-minute session