Consider the C code fragment given below.

typedef struct node   {
    int data;
    node* next;
}   node;

void join(node* m, node* n)   {
    node*  p = n;
    while(p→next  !=NULL)    {
       p = p→next; 
    }
    p→next=m;
}

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: Θ(N) delete,O(logN) insert, O(logN) find, and Θ(N) decrease-key. What is the time complexity of all these operations put together?

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node 
{
  int value;
  struct node *next;
}Node;
  
Node *move_to_front(Node *head) 
{
  Node *p, *q;
  if ((head == NULL: || (head->next == NULL)) 
    return head;
  q = NULL; p = head;
  while (p-> next !=NULL) 
  {
    q = p;
    p = p->next;
  }
  _______________________________
  return head;
}

Choose the correct alternative to replace the blank line.

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

struct node {
  int value;
  struct node *next;
};
void rearrange(struct node *list) {
  struct node *p, * q;
  int temp;
  if ((!list) || !list->next)return;
  p = list; q = list->next;
  while(q) {
     temp = p->value;p->value = q->value;
     q->value = temp;p = q->next;
     q = p?p->next:0;
  }
}

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

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

Let p be a pointer as shown in the figure in a single linked list.

What do the following assignment statements achieve?

q: = p → next
p → next:= q → next
q → next:=(q → next) → next
(p → next) → next:= q

(b) Compute the postfix equivalent of the following Infix expression

  3 * log(x+1) - a/2  

The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

Linked lists are not suitable data structures of which one of the following problems?

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Consider a singly linked list having n nodes. The data items d₁, d₂, ...d_n are stored in these n nodes. Let X be a pointer to the j-th node (1≤j≤n) in which d_j is stored. A new data item d stored in node with address Y is t be inserted. Give an algorithm to insert d into the list to obtain a list having items d₁, d₂, ..., d_j-1, d_j, ..., d_n in the order without using the header.