Skip to content
GATETECH
Official PYQ · 2003Q90Linked ListsMCQ1 mark

GATE CS 2003 Q90 — Linked Lists

Explain with AI

Consider the function ff defined below.

struct item {
        int data;
        struct item * next;
};
int f(struct item *p) {
    return ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));
}

For a given linked list pp, the function ff returns 11 if and only if

Choose one option
View worked solution

Answer: B

Let us analyze the behavior of the recursive function f(p)f(p):

  1. Base Cases:
    • p == NULL: If the list is empty, the function immediately returns 1 (true).
    • p->next == NULL: If the list has exactly one element, the function immediately returns 1 (true).
  2. Recursive Step:

    If the list has two or more elements, the function returns 1 if and only if:

    (p->data <= p->next->data) && f(p->next) is true.

    This condition requires that:

    • The current element's data is less than or equal to the next element's data (p→data≤p→next→datap\to\text{data} \le p\to\text{next}\to\text{data}).
    • The remaining sublist starting from p->next is also recursively verified to satisfy the same condition.

Combining these conditions, the function returns 1 if and only if every element in the list is less than or equal to its succeeding element. This is the definition of a list sorted in non-decreasing order.

Therefore, the correct option is B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Linked Lists questions