1. 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?
(a) O(n)
(b) O(log2 n)
(c) O(logn)
(d) O(1)
Answer
To delete an intermediate node, the next pointer of Q should be copied to previous node’s next pointer. For this to happen, previous node address should be known. So a traversal of linked list should be done which has time complexity of O (n).
2. 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;
}
}
(a) 1, 2, 3, 4, 5, 6, 7
(b) 2, 1, 4, 3, 6, 5, 7
(c) 1, 3, 2, 5, 4, 7, 6
(d) 2, 3, 4, 5, 6, 7, 1
Answer
Initially p points to first node and q points to second node. Now value of both the nodes get interchanged by code of swapping using third variable. After swapping
p = q -> next
q points to third node now.
q = p -> next
and q points to fourth node.
In this data of two nodes get interchanged and now it points to next two nodes.
3. In a circular linked list
(a) Components are all linked together in some sequential manner.
(b) There is no beginning and no end.
(c) Components are arranged hierarchically.
(d) Forward and backward traversal within the list is permitted.
Answer
In a circular linked list, the last node contains the address of first node, looping in itself. So there is no end and no beginning.
some pointer is
(a) 0 (1)
(b) 0 (log n)
(c) 0 (n)
(d) 0 (n 1og n)
Answer
If the element after which node needs to be inserted is pointed by some pointer, then traversal of complete list is not required. Thus insertion in that case is O (1) .
5. A linear collection of data elements where the linear node is given by means of pointer is
called
(a) Linked list
(b) node list
(c) Primitive list
(d) None of these
Answer
6. Which of the following operations is performed more efficiently by doubly linked list than by singly linked list?
(a) Deleting a node whose location is given
(b) Searching of an unsorted list for a given item
(c) Inverting the list after the node with given location
(d) Traversing a list to process each node
Answer
For deleting the node in singly linked list, a traversal is needed till previous node of the node to be deleted which is not required in case of doubly linked list.
7. The time required to delete a node x from a doubly linked list having n nodes is
(a) O (n)
(b) O (log n)
(c) O (1)
(d) O (n log n)
Answer
To delete a node x (a pointer) , no traversal is required. Thus o (1) is required.
8. Time required finding any element of the linked list is.
(a) O (n2)
(b) O (1)
(c) O (n)
(d) None of these
Answer
O (n)Traversal of linked list of all n items is required to search element in the worst case. Thus O (n) is the time complexity.
9. Pointer is pointing to the first element of the Node then time required to insert Element to second position is
(a) O(n2)
(b) O (sqrt(n))
(c) O(n)
(d) O(1)
Answer
Since insertion is O (1) and no traversal is required to reach the second node. Thus it is done in O (1).
(a) Singly linked list
(b) Doubly linked list
(c) Circular linked list
(d) Multiply linked list
Answer
This is the definition of Circular linked list.