Data Structures Quiz

What is the worst case time complexity of inserting a node in a doubly linked list?

• O(nlogn)

• O(logn)

• O(n)

• O(1)

Consider the following linked list: 2 -> 4 -> 7 -> 9 -> 10 -> 13. Their addresses are 2408, 2560, 1560, 5440, 3240, 3000. Head variable is pointing at 4 (the second node). What will be head -->next-->next-->value. (Node has value and next. value stores the value and next stores the address of the next variable).

• 7

• 9

• 10

• 13

Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list? F->1->2->3->L

• Delete the first element of the list

• Interchange the first two elements of the list

• Delete the last element of the list

• Add an element at the end of the list

Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?

• 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

What is the primary disadvantage of using a hash table (or HashSet) to detect a loop in a linked list?

• It has a higher time complexity.

• It requires additional space proportional to the number of nodes.

• It cannot find the starting node of the loop.

• It only works on sorted linked lists.

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

• log(2*n)

• n/2

• log(2*n) -1

• n

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 list

• Prints all nodes of linked list in reverse order

• Prints alternate nodes of Linked List

• Prints alternate nodes in reverse order

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node Q from the list?

• O(n)

• O(log2 n)

• O(logn)

• O(1)

Consider the problem of reversing a singly linked list. Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

• The best algorithm for the problem takes θ(n) time in the worst case

• The best algorithm for the problem takes θ(nlogn) time in the worst case.

• The best algorithm for the problem takes θ(n2) time in the worst case

• It is not possible to reverse a singly linked list in O(1) space.

What is an advantage of using a circular linked list over a singly linked list?

• Easier implementation of stacks and queues.

• Allows for efficient traversal from the last node back to the head.

• Requires less memory.

• Faster searching for elements.