DS UNIT-2 TEST-2

What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.

• O(1) and O(n)

• O(1) and O(1)

• O(n) and O(1)

• O(n) and O(n)

Answer explanation

Finding the 8th element from the beginning of a singly linked list requires traversing the first 8 nodes of the list, which takes O(8) time, or simply O(1) time since it's a constant time operation.

Finding the 8th element from the end of a singly linked list requires traversing the list until we reach the 8th node from the end. One way to do this is to first traverse the list once to determine its length, and then traverse the list again until we reach the node at position n-8. This takes O(n) time for the first traversal, and then O(n-8) time for the second traversal. Therefore, the time complexity of finding the 8th element from the end of a singly linked list is O(n).

Is it possible to create a doubly linked list using only one pointer with every node.

• Not Possible

• Yes, possible by storing XOR of current node and next node

• Yes, possible by storing XOR of addresses of previous and next nodes

• Yes, possible by storing XOR of current node and previous node

Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

• Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b)Update the pointer of node X to the node after the next node. Delete next of X.

• Possible if size of linked list is even

• Possible if size of linked list is odd

• Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.

Answer explanation

struct node *temp = X->next;

X->data = temp->data;

X->next = temp->next;

free(temp);

Which of the following is an application of XOR-linked lists?

• Implementing stacks

• Caching data structures

• Memory-efficient linked list representation

• 
  Implementing queues

Answer explanation

XOR linked lists are a memory-efficient representation of linked lists. They store the XOR combination of the addresses of the previous and next nodes, reducing the memory overhead compared to traditional linked lists.

Consider the following function to traverse a linked list. 

void traverse(struct Node *head)

{

   while (head->next != NULL)

   {

       printf("%d  ", head->data);

       head = head->next;

   }

}

Which of the following is FALSE about above function?

• 
  The function is implemented incorrectly because it changes head

• The function doesn't print the last node when the linked list is not empty

• 
  The function may crash when the linked list is empty

• None of the Above

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(log n)

• O(1)

• O(n)

• O(log2 n)

Answer explanation

To delete a node Q from a singly linked list, we need to modify the next pointer of the node that precedes Q to point to the node that follows Q. However, in a singly linked list, we cannot traverse the list backwards from a given node, so we need to start from the beginning of the list to find the node that precedes Q.

Therefore, the worst-case time complexity of the best known algorithm to delete the node Q from the list is O(n), where n is the length of the list. This is because we may need to traverse the entire list to find the node that precedes Q.

However, if we have a pointer to the node that precedes Q, the deletion operation can be performed in O(1) time complexity, since we can simply modify the next pointer of that node to skip over Q. But, if we do not have a pointer to the node that precedes Q, we need to start from the beginning of the list and traverse the list to find it, which takes O(n) time complexity in the worst case.

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together?

• O(Log²N)

• O(N Log N)

• O(N)

• 
  Θ(N² Log N)

Answer explanation

The time complexity of all these operations put together is O(N log N).

The delete operation takes Θ(N) time because we need to traverse the list to find the record to be deleted.

The insert and find operations take O(log N) time each because the list is sorted and we can use binary search to locate the correct position for the new record or to find an existing record.

The decrease-key operation takes Θ(N) time because we need to traverse the list to find the record on which the operation is to be performed.

Assuming that there are M total operations (M = Θ(N) + O(log N) + O(log N) + Θ(N) = O(N)), the total time complexity of all operations is O(M log N) = O(N log N), because the operations take varying amounts of time but they are all performed on a list of size N.

The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

• singly linked list

• doubly linked list

• circular doubly linked list

• array implementation of lists

Answer explanation

As list concatenation requires traversing at least one list to the end. So singly linked list and doubly linked list requires O(n) time complexity whereas circular doubly linked list required O(1) time.

Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers.

Node remove-duplicates(Node head, int j) {

Node t1, t2; j=0; t1 = head;

if (t1! = NULL) t2 = t1 →next;

else return head;

j = 1;

if(t2 == NULL)

return head;

while t2 != NULL) {

if (t1.val != t2.val) --------------------------→ (S1) {

(j)++; t1 -> next = t2; t1 = t2: ----------→ (S2) }

t2 = t2 →next; }

t1 →next = NULL;

return head; }

Assume the list contains n elements (n≥2) in the following questions. a). How many times is the comparison in statement S1 made? b). What is the minimum and the maximum number of times statements marked S2 get executed? c). What is the significance of the value in the integer pointed to by j when the function completes?

• • (a). n-1 times, since comparison is pairwise for n elements.

  • (b). maximum : n-1 for all distinct elements, minimum: 0 for all same elements.

  • (C). j keeps count of distinct nodes in the list.

• • (a). n times, since comparison is pairwise for n elements.

  • (b). maximum : n-1 for all distinct elements, minimum: 0 for all same elements.

  • (C). j keeps count of distinct nodes in the list.

• • (a). n-1 times, since comparison is pairwise for n elements.

  • (b). maximum : n-1 for all distinct elements, minimum: 1 for all same elements.

  • (C). j keeps count of distinct nodes in the list.

• None of the Above

Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node and lengths of lists are not known. What is worst case time complexity of optimal algorithm to find intersecting node from two intersecting linked lists?

• 
  Θ(n*m), where m, n are lengths of given lists

• Θ(n^2), where m>n and m, n are lengths of given lists

• 
  Θ(m+n), where m, n are lengths of given lists

• Θ(min(n, m)), where m, n are lengths of given lists

Answer explanation

This takes Θ(m+n) time and O(1) space in worst case, where M and N are the total length of the linked lists.

1. Traverse the two linked list to find m and n.

2. Get back to the heads, then traverse |m − n| nodes on the longer list.

3. Now walk in lock step and compare the nodes until you found the common ones.