The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.3k views

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

asked in DS by Veteran (59.5k points)
edited by | 2.3k views
+3
I still dont understand why is a not correct it is an or condition if (p==NULL||(p->next==NULL)||((p->data<=p->next->data)&&f(p->next))) all 4 coditions are in or even if one is true  it can return 1 plz explain
0

$A$ if and only if $B$ means both $A\rightarrow B$ as well as $B\rightarrow A$ hold.

So is the function returning 1 only when the list is empty or has exactly one element? NO

because it also returns 1 for  ((p->data <= p ->next -> data) && f(p->next)) which is nothing but C ! So C is the most appropriate choice.

0
C means it sat that its a decreasing order list....is it possible??
0
Some one please give better answer

2 Answers

+25 votes
Best answer

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.

answered by Boss (14.2k points)
edited by
0
why not A as it also satisfies ?
+8
Due to if and only if
+3
olrite, got it
+14 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.)
answered by Boss (22.7k points)
0
The cause "if and only if" makes both option (a) and (b) wrong. How to handle this ?
0
@arjun sir

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,000 questions
45,497 answers
131,580 comments
48,634 users