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

It returns $1$ if and only if the linked list is sorted in non-decreasing order- (B) option.

It returns $1$ if the list is empty or has just $1$ element also, but if and only if makes (A) option false.

Comments

sir can you please elaborate on if and ony if . Actually i am unable to find the impact of if and only if in the question .

---

If and only if is important for this ques..

Option (A)- Fails because if f() returns 1 then it can be because of list is empty or having one element or data is non decreasing order(not mentioned in one)

Option (B)- Is True because non decreasing element list can include empty and single element list as they are in itself a non decreasing list.

---

@ ankitrazzagmail.com

If and only if makes option A incorrect, but it also makes option B incorrect.

 

NO i can’t make B incorrect because A is included in B.

    return ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));

here due to f(p→ next ) it do recursive call again and again and finally reaches the value where               p->next == NULL.

Hope this helps!

I think actual answer is : the list is empty OR has exactly one element OR the elements in the list are sorted in non-decreasing order of data value.
 

And yes this is also the answer if it is given in the options but it is not isn’t it... 

Answer 2

How to approach this:-

Emphasize on Word "if and only if"

Read all options carefully ..eliminate the wrong ones.

A. May Correct but due to if and only if Check remaining options.

C. False . Example:->5,5,4 it wont return 1.(still optionA may correct).

D. False. Example:->> 8,2,10 it wont return 1(still option A may correct).

B.Example:->>  1,1,2  it returns 1

So here Option A becomes wrong Now So option  B is correct.

(Check another large list also 1,2,2,3,3 still returns1 So finally Option B is Ans.)

Comments

The cause "if and only if" makes both option (a) and (b) wrong. How to handle this ?

---

@arjun sir

please expalin 4 the option through example .I m not getting this

Answer 3

#include <stdio.h>
#include <stdlib.h>
struct item {
    int data;
    struct item * next;
};
void print(struct item *lhead)
{
    while(lhead!=NULL)
    {
        printf("%d ",lhead->data);
        lhead = lhead->next;
    }
}
int f(struct item *p) {
    return ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));
}
int main(void) {
    // your code goes here
    int t,i=0;
    //printf("Number of testcases:");
    scanf("%d",&t);
    while(t--)
    {
        struct item *head = NULL;
        int n;//number of nodes
        //Number of nodes 
        scanf("%d",&n);
        int d;//data;
        struct item *temp;
        while(n--)
        {
            scanf("%d",&d);
            temp = malloc(sizeof(struct item));
            temp->data = d;
            temp->next = head;
            head = temp;
        }
        
        printf("\nThe elements are for case %d:\n",++i);
        print(head);
        printf("\nReturn value for case %d:",i);
        printf("%d",f(head));
    }
    printf("\n");
    return 0;
}

Output is:

    

From above we can clearly see A is not sufficient, we can get 1 when we have elements in non-decreasing order

whereas in option B we get return value 1, as well as option A, is also contained in Option B

Hence B is a more appropriate answer than A

Answer 4

This question is only observation based.

the condition given is 

 ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));

here in the second line of code we are given that p-> data <= p-> next ->data . It means that the data stored in the address of p pointer  must be smaller or equal to the data in the next node i.e p->next->data. Eg- 2->2-.3->4 which is in non decreasing order and also more valid than option A. So,this condition is only satisfied by option B.

Comments

Also non-decreasing order allows null or single node are also valid