Data Structure
Q201.
Consider the C code fragment given below. typedef struct node { int data; node* next ; } node; void join (node* m, node* n) { node* p=n ; while (p->next ! =NULL){ p = p -> next ; } p-> next = m; } Assuming that m and n point to valid NULL- terminated linked lists, invocation of join willQ202.
An algorithm performs (log N)^{1/2} find operations, N insert operations, (log N)^{1/2} delete operations, and (log N)^{1/2} decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?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.
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; } }Q206.
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)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.
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?