DS Training QUIZ 1

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

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)