GATE CSE 2003 | Question: 90

Question

Consider the function $f$ 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 $p$, the function $f$ returns $1$ if and only if

• A. the list is empty or has exactly one element

• B. the elements in the list are sorted in non-decreasing order of data value

• C. the elements in the list are sorted in non-increasing order of data value

• D. not all elements in the list have the same data value

Comments

If someone has confusion how function return terminating value

return(0 || 1 || (......) );

the ..... part will not execute as here || operator used and when it gets 1 it will not check or execute right part.

---

If and only if means ==> necessary and sufficient condition. 

But the list is empty or has exactly one element is not necessary and sufficient condition to return 1 for the function f.

Because a non empty list, a list containing more than one element (which is non-decreasing order in data value) will also return 1. 

So option A is not true. 

---

Thanks a lot

Answer 1

Here if and only if word is important . Option A will be wrong because even if the linked list is not empty the function will still return 1 . So the whole idea of  S: A$\Leftrightarrow$B  fails as  S can still be made true even after B is false .

Answer 2

Non decreasing element list can include empty and single element list as they are in itself a non decreasing list.