DS Training

  What does the following function do for a given Linked List with first node as head?

 

void fun1(struct node* head)

{

  if(head == NULL)

    return;

 

  fun1(head->next);

  printf("%d  ", head->data);

}

•     Prints all nodes of linked lists

• Prints all nodes of linked list in reverse order

•      Prints alternate nodes of Linked List

•   Prints alternate nodes in reverse order

1.      Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next.

 

void fun(struct node **head_ref)

{

    struct node *temp = NULL;

    struct node current = head_ref;

 

    while (current !=  NULL)

    {

        temp = current->prev;

        current->prev = current->next;

        current->next = temp;

        current = current->prev;

    }

 

    if(temp != NULL )

        *head_ref = temp->prev;

}

Assume that reference of head of following doubly linked list is passed to above function 1 <--> 2 <--> 3 <--> 4 <--> 5 <-->6. What should be the modified linked list after the function call?

•    2 <--> 1 <--> 4 <--> 3 <--> 6 <-->5

•     5 <--> 4 <--> 3 <--> 2 <--> 1 <-->6.

•     6 <--> 5 <--> 4 <--> 3 <--> 2 <--> 1.

•      6 <--> 5 <--> 4 <--> 3 <--> 1 <--> 2

Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

•   Insertion Sort

•      Quick Sort

• Heap Sort

• Merge Sort

What is the output of following function in which start is pointing to the first node of the following linked list 1->2->3->4->5->6 ?

void fun(struct node* start)

{

  if(start == NULL)

    return;

  printf("%d  ", start->data);

  

  if(start->next != NULL )

    fun(start->next->next);

  printf("%d  ", start->data);

}

•    1 4 6 6 4 1

•    1 3 5 1 3 5

•     1 2 3 5

•      1 3 5 5 3 1

     In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is (GATE CS 2002)

 

•   log(2*n)

•     n/2

•    log(2*n) -1

•     n

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? (GATE CS 2004)

• union

• membership

• cardinality

• union, intersection

What is the optimal time complexity to count the number of nodes in a linked list?

• O(n)

• O(1)

• O(log n)

• O(n log n)

Which of the following algorithms is not feasible to implement in a linked list?

•   Insertion Sort

• Quick Sort

•     Heap Sort

•    Binary Search

What is the time complexity to insert an element to the front of a LinkedList(head pointer given)?

• O(n)

• O(1)

• O(log n)

• O(n log n)
  
  

What is the time complexity of a program to reverse a linked list?         

• O(n)

• O(1)

• O(log n)

• O(n log n)