Data Structure
Q201.
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?Q202.
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?Q203.
The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node {int value; struct node *next;); void rearrange (struct node *list) { struct node *p, *q; int temp; if (!list || !list -> next) return; p = list; q = list -> next; while (q) { temp = p -> value; p -> value = q -> value; q -> value = temp; p = q -> next; q = p ? p -> next : 0; } }Q205.
Suppose there are \left \lceil log n \right \rceil sorted lists of \left \lfloor n/log n \right \rfloor elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)Q206.
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node { int value; struct node *next; }; Void rearrange(struct node *list) { struct node *p, * q; int temp; if(!list|| !list-> next) return; p=list; q=list->next; while(q) { temp = p->value; p->value = q->value; q->value = temp; p = q->next; q = p?p->next:0; } }Q207.
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 x from the list ?Q208.
Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest?Q209.
Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL) || ((P->data <= p->next->data) && f(p->next))); } For a given linked list p, the function f returns 1 if and only ifQ210.
In the worst case, the number of comparisons needed to search a single linked list of length n for a given element is