edited by
17,456 views
55 votes
55 votes

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

  1. the list is empty or has exactly one element

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

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

  4. not all elements in the list have the same data value

edited by

6 Answers

Best answer
41 votes
41 votes

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.

edited by
24 votes
24 votes
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.)
3 votes
3 votes
#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

edited by
1 votes
1 votes

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.

Answer:

Related questions

79 votes
79 votes
10 answers
2
Disha asked Sep 19, 2014
31,690 views
In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time$\Theta (n \log n)$$\Theta (n)$$\Theta(\log n)$$\...
81 votes
81 votes
6 answers
4
Kathleen asked Sep 16, 2014
22,317 views
Let $T(n)$ be the number of different binary search trees on $n$ distinct elements.Then $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, where $x$ is $n-k+1$$n-k$$n-k-1$$n-k-2$