DS - Linked List - S1

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)