Question 6 of 8: Basis Path Testing of fn_delete_element

Question 6: Basis Path Testing of fn_delete_element (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Appendix B (as printed in the exam) is reproduced below for reference:

Function fn_delete_element (int value, int array_size, int array[])
{
    int i;

    location = array_size + 1;

    for i = 1 to array_size
        if ( array[i] == value )
            location = i;
        end if;
    end for;

    for i = location to array_size
        array[i] = array[i+1];
    end for;

    array_size --;

}

Given. A function that searches array[1..array_size] for value, shifts every element after the last match left by one, and decrements array_size.

Find. The control-flow graph, cyclomatic complexity V(G), and a basis (minimum, independent) set of V(G) test cases.

Approach. Number the function's eight basic blocks/decisions, build the flow graph, compute V(G) two independent ways, and derive one test case per basis path, tracing each by hand to confirm what it actually does — the same discipline Question 3(b)'s driver-based unit testing assumes.

1. Number the nodes and build the edge list. 1 location = array_size+1 → 2 first for-test (i ≤ array_size) → 3 if(array[i]==value) → 4 location = i → 5 merge / loop-1 increment → 6 second for-test (i ≤ array_size) → 7 array[i]=array[i+1] / loop-2 increment → 8 array_size--; return. Edges: {1-2, 2-3(T), 2-6(F), 3-4(T), 3-5(F), 4-5, 5-2, 6-7(T), 6-8(F), 7-6}.
2. Compute V(G) two independent ways. By edges/nodes, $N=8$, $E=10$, so $V(G) = E-N+2 = 10-8+2 = \boxed{4}$. By the predicate-node formula $V(G)=1+\sum(\text{out-degree}(p)-1)$ over the three 2-way decisions (nodes 2, 3, 6): $V(G) = 1+1+1+1 = 4$ — the two methods agree, the standard cross-check before trusting a hand-drawn graph.
3. Derive and trace four independent paths. Path 1 (empty array, degenerate boundary): $1\to2_F\to6_F\to8$ — array_size = 0; the first loop never runs, the second loop never runs, yet array_size-- still fires, leaving array_size = -1. Path 2 (value absent, one-element array): $1\to2_T\to3_F\to5\to2_F\to6_F\to8$ — array=[10], value=99; location stays 2 (never matched), the second loop still never runs (2 > array_size), yet array_size-- still drops it from 1 to 0 — the untouched element 10 is silently orphaned. Path 3 (value found, one-element array): $1\to2_T\to3_T\to4\to5\to2_F\to6_T\to7\to6_F\to8$ — array=[10], value=10; location=1, the second loop's one iteration executes array[1]=array[2], and array[2] does not exist. Path 4 (value found mid-array, second loop runs twice): $1\to2_T\to3_F\to5\to2_T\to3_T\to4\to5\to2_T\to3_F\to5\to2_F\to6_T\to7\to6_T\to7\to6_F\to8$ — array=[5,7,9], value=7; location=2, the second loop runs for $i=2,3$: array[2]=array[3]=9 (a real, correct shift), then array[3]=array[4], and array[4] does not exist either.

Path 4 is the more important of the two off-by-one cases: it shows the illegal array[array_size+1] read is not a fluke of the smallest possible test — it happens on EVERY found case, once per second-loop execution, regardless of array size — while the surviving logical elements [5,9] are still exactly right. A black-box test that only checked the function's returned array (correct here) would never notice this defect; only white-box execution of the actual second loop, one iteration at a time, catches the illegal access itself. Two further defects worth flagging beyond the four traced paths: since neither value-not-found case guards array_size--, the function should almost certainly check location ≤ array_size before decrementing at all (Paths 1–2); and since the first loop never breaks once it matches, if value occurs MORE THAN ONCE in the array, location is silently overwritten to the LAST occurrence rather than the first — a data-dependent defect that no single basis path, by itself, is guaranteed to expose, since it depends on the specific VALUES in the array rather than on which control-flow edges are taken.