Register

GO Classes DA Test Series | Data Structures and Algorithms | Topic Wise Test 1 | Question: 9

• edited by
439 views
4 4 votes

Consider a mutual pair of recursive functions g() and h().

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def g(l):
    if l is None or l.next is None:
        return 1
    if l.value < l.next.value:
        return h(l.next)
    else:
        return 0

def h(l):
    if l is None or l.next is None:
        return 1
    if l.value > l.next.value:
        return g(l.next)
    else:
        return 0

Let head be a pointer to a singly linked list having at least $3$ nodes.

When will the expression (g(head) || h(head)) return $1$ or $0?$

  1. g(head) || h(head) is $1$ if the linked list is in ascending order.
  2. g(head) || h(head) is $1$ if the linked list is in descending order.
  3. g(head) || h(head) is $1$ for every unsorted linked list.
  4. g(head) || h(head) is $1$ for the linked list $1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 0\rightarrow 6$

2 Answers

3 3 votes

$g(l)$ : It checks whether two nodes are in ascending order, then it calls $h(l)$ else it will return 0.

$h(l)$ : It checks whether two nodes are in descending order, then it calls $g(l)$ else it will return 0.


 

it will return 0 for sorted array.

If it is unsorted array it will return 0. ( Note : LL has at least 3 nodes. )


 

Option D : As per order of evaluation $g(l)$ will be called first.

Recursively, It will check $l$ and $l \rightarrow n$, ascending in $g(l)$ then descending in $h(l)$

i.e. $g(h) 1 < 3, $h(l)$: 3 > 2$ and so on.


 

So, main call $g(l)$ will return 1 when $l \rightarrow n$ is null.

1 1 vote

g(head) ∥ h(head) returns 1 if and only if the linked list is a strictly alternating zig-zag sequence (also called strictly alternating up–down or down–up).

That means:

  • either
    l₁ < l₂ > l₃ < l₄ > l₅ < … (starts with <, handled by g)

  • or
    l₁ > l₂ < l₃ > l₄ < l₅ > … (starts with >, handled by h)

Any break in alternation → both g and h return 0

A. “1 if linked list is in ascending order.” → False

Purely increasing like 1 → 2 → 3 → 4 fails because h(l.next) immediately fails.

B. “1 if linked list is in descending order.” → False

Purely decreasing also fails.

C. “1 for every unsorted linked list.” → False

Only some unsorted lists qualify (alternating ones), not all.

D. “1 for the list 1 → 3 → 2 → 4 → 0 → 6.” → True

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DA Test S...Next → · GO Classes DA Test S...
← Previous in category · GO Classes DA Test S...Next in category → · GO Classes DA Test S...
Position:
Show:

Related questions

3 3 votes
1 1 answer
600
600 views
GO Classes asked Sep 15, 2024
600 views
GO Classes DA Test Series | Data Structures and Algorithms | Topic Wise Test 1 | Question: 8
The following code is intended to remove a node p from a doubly linked list. Assume that we know that p is in the list, so the list is not empty.class Node: def __init__(...
8 8 votes
1 1 answer
572
572 views
GO Classes asked Sep 15, 2024
572 views
GO Classes DA Test Series | Data Structures and Algorithms | Topic Wise Test 1 | Question: 11
Consider the following function Merge() that takes the head of two linked lists.class Node: def __init__(self, value): self.value = value self.next = None def Merge(head1...
7 7 votes
2 2 answers
801
801 views
GO Classes asked Sep 15, 2024
801 views
GO Classes DA Test Series | Data Structures and Algorithms | Topic Wise Test 1 | Question: 12
Consider the following program. printlist() is a function that takes the head of a linked list and prints all nodes values separated by comma. Node can be assumed to be d...
3 3 votes
1 1 answer
362
362 views
GO Classes asked Sep 15, 2024
362 views
GO Classes DA Test Series | Data Structures and Algorithms | Topic Wise Test 1 | Question: 6
class Node: def __init__(self, data, next=None): self.data = data self.next = next def print_nodes(ptr): if ptr: print(ptr.data, end=' ') while ptr.next: ptr = ptr.next p...