Data Structures - Training: Quiz 1

Which sorting algorithm can be used to sort a random linked list with minimum time complexity?

• Insertion Sort

• Quick Sort

• Heap Sort

• Merge Sort

Suppose each set is represented as a linked list with elements in arbitrary order. Which 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)

Which of the following operations is performed more efficiently by a doubly linked list than by a linear linked list? (ISRO CS 2001)

• Deleting a node whose location is given

• Searching an unsorted list for a given item

• Inserting a node after the node with a given location

• Traversing the list to process each node

Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?

• Delete the last element of the list

• Delete the first element of the list

• Add an element after the last element of the list

• Interchange the first two elements of the list