GATE CS 2015 Set 1 Q.52 (CS Q.42): Data Types, Operators and Control Flow

Consider the following C program segment.

while (first <= last)
{
    if (array[middle] < search)
        first = middle + 1;
    else if (array[middle] == search)
        found = TRUE;
    else last = middle - 1;
    middle = (first + last) / 2;
}
if (first > last) notPresent = TRUE;

The cyclomatic complexity of the program segment is _____.

Your answer

Official answer and solution

Official answer: 5
From: Official GATE 2015 answer key

Solution

Calculate McCabe cyclomatic complexity using the predicate formula V(G) = P + 1.

McCabe's cyclomatic complexity $V(G)$ for a structured program is given by:

V(G) = P + 1

where $P$ is the number of predicate (decision) nodes in the control flow graph.

Identifying all predicate conditions in the code:

Predicate 1: while (first <= last) (loop condition, 2 branch outcomes: enter loop or exit loop)
Predicate 2: if (array[middle] < search) (binary branch)
Predicate 3: else if (array[middle] == search) (binary branch)
Predicate 4: if (first > last) (condition following the while loop)

Total predicate nodes $P = 4$ .

Therefore, the cyclomatic complexity is:

V(G) = 4 + 1 = 5.

Final answer

Common trap

Overlooking the conditional check if (first > last) after the loop body.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 1
Question: 52 of 65, printed as CS Q.42
Section: Computer Science and Information Technology

This question is from a part of the syllabus that is no longer in GATE CS. It is kept because it was in the paper.

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source