Data Structures Prelimes

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)

Which of the following problems can be solved using 2 pointers on linked list?

• Detecting cycle in a Linked List

• Finding intersection of two linked lists

• Finding middle of a linked lists

• None of the above

Rotating a linked list by some places clockwise will take a time complexity of?

• O(n)

• O(1)

• O(log n)

• O(n log n)