LinkedList
Question 1 
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 NULLterminated linked lists, invocation of join will
append list m to the end of list n for all inputs.  
either cause a null pointer dereference or append list m to the end of list n.  
cause a null pointer dereference for all inputs.  
append list n to the end of list m for all inputs. 
So have to consider both the cases.
⇾ 1. Lists are not null, invocation of JOIN will append list m to the end of list n.
m = 1, 2, 3
n = 4, 5, 6
After join, it becomes 4, 5, 6, 1, 2, 3, NULL.
⇾ 2. If lists are null, if the list n is empty, and itself NULL, then joining & referencing would obviously create a null pointer issue.
Hence, it may either cause a NULL pointer dereference or appends the list m to the end of list n.
Question 2 
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 decreasekey 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(logN) insert, O(logN) ﬁnd, and Θ(N) decreasekey. What is the time complexity of all these operations put together?
O(log^{2} N)  
O(N)  
O(N^{2})  
Θ(N^{2} logN) 
→ Delete needs O(1) time
→ Insert takes O(N) time
→ Find takes O(N) time
→ Decrease by takes O(N) time
Now number of each operation performed is given, so finally total complexity,
→ Delete = O(1) × O(N) = O(N)
→ Find = O(N) × O(log N) = O(N log N)
→ Insert = O(N) × O(log N) = O(N log N)
→ Decrease key = O(N) × O(N) = O(N^{2})
So, overall time complexity is, O(N^{2}).
Question 3 
The following C function takes a simplylinked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
typedef struct node { int value; struct node *next; }Node; Node *move_to_front(Node *head) { Node *p, *q; if ((head == NULL:  (head>next == NULL)) return head; q = NULL; p = head; while (p> next !=NULL) { q = p; p = p>next; } _______________________________ return head; }
Choose the correct alternative to replace the blank line.
q = NULL; p→next = head; head = p;  
q→next = NULL; head = p; p→next = head;  
head = p; p→next = q; q→next = NULL;  
q→next = NULL; p→next = head; head = p; 
The function modifies the list by moving the last element to the front of the list.
Let the list be 1 → 2 → 3 → 4 & the modified list must be 4 → 1 → 2 → 3.
Algorithm:
Traverse the list till last node. Use two pointers. One to store the address of last node & other for the address of second last node.
After completion of loop. Do these.
(i) Make second last as last
(ii) Set next of last as head
(iii) Make last as head
while (p → !=NULL)
{
q = p;
p = p → next;
}
― p is travelling till the end of list and assigning q to whatever p had visited & p takes next new node, so travels through the entire list.
Now the list looks like
According to the Algorithm new lines must be
q → next = NULL; p → next = head; head = p
Question 4 
The following C function takes a singlelinked 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; } }
1,2,3,4,5,6,7  
2,1,4,3,6,5,7  
1,3,2,5,4,7,6  
2,3,4,5,6,7,1 
After 1^{st} Iteration: 2,1,3,4,5,6,7
2^{nd} Iteration: 2,1,4,3,5,6,7
3^{rd} Iteration: 2,1,4,3,6,5,7
After each exchange is done, it starts from unchanged elements due to p=q⟶next;
‘p’ pointing to Null & q pointing to 7.
Hence 2,1,4,3,6,5,7.
Question 5 
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?
rear node  
front node  
not possible with a single pointer  
node next to front 
Question 6 
Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?
union only  
intersection, membership
 
membership, cardinality  
union, intersection 
Let no. of elements in list 2 be n_{2}.
Union:
To union two lists, for each element in one list we will search in other list, to avoid duplicates. So, time complexity will be O(n_{1}×n_{2}).
Intersection:
To take intersection of two lists, for each element in one list we will search in other list if it is present or not. So time complexity will be O(n_{1} × n_{2}).
Membership:
In this we search if particular element is present in the list or not. So time complexity will be O(n_{1} + n_{2}).
Cardinality:
In this we find the size of set or list. So to find size of list we have to traverse each list once. So time complexity will be O(n_{1}+n_{2}).
Hence, Union and Intersection will be slowest.
Question 7 
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 if
the list is empty or has exactly one element  
the elements in the list are sorted in nondecreasing order of data value
 
the elements in the list are sorted in nonincreasing order of data value
 
not all elements in the list have the same data value 
Question 8 
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
log n  
n/2  
(log_{2})^{n}  1  
n 
Question 9 
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 list 
Question 10 
Linked lists are not suitable data structures of which one of the following problems?
Insertion sort  
Binary search  
Radix sort  
Polynomial manipulation

Question 11 
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
θ(n log n)  
θ(n^{2})  
θ(1)  
θ(n) 
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case.
After inserting elements into an empty linked list we have to perform sorting operation.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only.
Let head be the first node of the linked list to be sorted and head Reference be the pointer to head.
The head in MergeSort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^{2}) and heap sort will not be suitable to apply.
Question 12 
In a circular linked list organisation, insertion of a record involves modification of
One pointer.  
Two pointers.  
Multiple pointers.  
No pointer. 
p → next = q → next
q → next = p
So, two pointers modifications.
Question 13 
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worstcase time complexity of the best known algorithm to delete the node x from the list?
O(n)  
O(log^{2} n)  
O(logn)  
O(1) 
Question 14 
Delete the last element of the list  
Delete the first element of the list  
Add an element after the last element of the list  
Interchange the first two elements of the list 
Option B: It needs only the operation F=F→ next
Option C: It needs only the operations L→ next=new node, L = new node
Option D: It needs only the operations T=F, F=F→ next, T→ next =F→ next, F→ next=T
→ All these operations do not depend on the length of the list.
→ Indeed in order to delete the last element from the list, we need to first locate the element before the last (which can not be accessed from L). Thus we must parse all the list from the first and till the element just before the last after which we can delete the last element and assign L to the one before.
Question 15 
(i) Insertion of an element should be done at the last node in a circular list
(ii) Deletion of an element should be done at the last node of the circular list
Both are true  
Both are false  
First is false and second is true  
None of the above 
1.Insertion at the front of Circular linked list.
2.Insertion in the middle of the Circular linked list.
3.Insertion at the end of the Circular linked list.
Question 16 
4  
0  
1  
None of these 
Note: Excluded for evaluation.
Question 17 
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 
Inserting the node after the node with the a given location won’t require of traversing the list to previous nodes or memory locations.In this case also, there is no difference between whether it may be linear linked list or doubly linked list.
The main purpose of double linked list is to traverse the list in both directions so Deleting the node becomes easy while traversing the both directions.
Question 18 
1  
2  
3  
4 
However, each node of doubly linked list can have only 2 fields, i.e., XOR pointer field, and data field. This XOR pointer field can points both previous node and next node, this is the best case with data field. This is called as memory efficient
doubly linked list, Also, if we remove data node from the XOR linked list, then each node of this doubly linked list can have only 1 field, i.e., XOR pointer field. But, this is without data field so, this doubly linked list does not make sense.
Question 19 
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 
2. In order to delete first element , change first pointer to the next element.It won’t require length of the linked list.
3. To interchange first two elements also, We need to work with only first two nodes only.Here also no need of length of linked list.
4. To add an element at the last node, we already has one pointer which is pointing to the last node, simple add new node to last node by storing last pointer next address to new node.
5. But in order to delete last node , we need to traverse the entire list , So it requires length of the linked list. By using the last node pointer , we can’t move to previous node in the single linked list.
Question 20 
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
Prints all nodes of linked lists  
Prints all nodes of linked list in reverse order  
Prints alternate nodes of Linked List  
Prints alternate nodes in reverse order 
Input : Head of following linked list
1>2>3>4>NULL
Output : Linked list should be changed to,
4>3>2>1>NULL
Algorithm:
1. Initialize three pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr>next
// Now change next of current
// This is where actual reversing happens
curr>next = prev
// Move prev and curr one step forward
prev = curr
curr = next
Question 21 
void fun(struct node **head_ref)
{
struct node *temp=NULL;
Struct node *current=*head_ref;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
*head_ref=temp → prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 <> 2 <> 3 <> 4<> 5 <> 6. What should be the modified linked list after the function call?
1<>2<>4<>3<>6<>5  
5<>4<>3<>2<>1<>6  
6<>5<>4<>3<>2<>1  
6<>5<>4<>3<>1<>2 
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
The loop meant for traversing the entire list till to end by changing prev and next pointers of all nodes.
Change prev of the head (or start) and change the head pointer in the end.
Question 22 
no pointer  
1 pointer  
2 pointer  
3 pointer 
x → next = n1 → next
n1 → next = x
So, we need to modify two pointers only to insert node into the linked list.
Question 23 
Consider the singly linked list. What is the worst case time complexity of the bestknown algorithm to delete the node a, pointer to this node is q, from the list ?
O(1)  
O(lg n)
 
O(n)  
O(n lg n)

Question 24 
Struct node* { Int data; node*link; }  
Struct node { int data; Struct node*link; }  
Struct node { int data; node link; }  
Struct node* { int data; struct node*link; } 
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};
Question 25 
Which of the following is wrong while inserting a node in the beginning of list?
Obtain a node from available list
 
Make the next pointer of the current head pointer to new node  
Make the node pointer of the list pointer to new node
 
Make the next pointer of the new node pointer to current head of the list

• Option B, C and D: It shows actual procedure to insert a node at beginning. So, Option A is wrong
Question 26 
Always appends list ‘m’ at the end of list ‘n’  
Always appends list ‘n’ at the end of list ‘m’  
Append list ‘m’ at the end of list ‘n’ with possibility of error  
Appends list ‘n’ at the end of list ‘m’ with possibility of error 
→Nonavailability of the any one of the linked list leads to possibility of error.
Question 27 
Insertion at the front of the linked list.  
Insertion at the end of the linked list.  
Deletion of the front node of the linked list.  
Deletion of the last node of the linked list. 
1. Insertion at the front of the linked list
2. Insertion at the end of the linked list
3. Deletion of the front node of the linked list
→ Linked list worst case complexity is O(n)
Possibilities are
1. Deletion of the last node of the linked list.
Note: We have to traverse entire linked list to get corresponding location. So, it traversing ‘n’ elements, it takes O(n) time worst case situation.
Question 28 
Advance  
Backup  
First  
Retrieve 
Question 29 
O(1)  
O(lg n)  
O(n)  
O(n lg n) 
Question 30 
Queue  
Linked list  
Doubly linked list  
Binary tree 
Question 31 
Binary Search  
Polynomial Manipulation  
Insertion  
Radix Sort 
Note: We can also implement binary search using linked list but it will give time complexity is O(n) instead of O(logn).
Question 32 
Neither of the pointers change  
Only front pointer changes  
Only rear pointer changes  
Both of the pointers changes 
Observe 1, 2, 3 whenever we are inserting an element into a queue (singly linked list) we are updating Rear pointer.
Question 33 
An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case.  
An algorithm for deleting the first element in a singly linked list requires 0(n) operations in the worst case.  
An algorithm for finding the maximum value in a circular linked list requires 0(n) operations.  
An algorithm for deleting the middle node of a circular linked list requires 0(n) operations. 
Question 34 
for (p=list; p !=NULL; p=p →next);
p=q;
 
for (p=list; p !=NULL; p=p →next);
p →next=q;
 
for (p=list; p →next!=NULL; p=p→next);
p=q;
 
for (p=list; p →next !=NULL; p=p →next);
p →next=q;

→ To the traverse the list, we will take one pointer.
→ We will traverse the list till the end by moving the pointer to next node.
→ The pointer will point to the last node and from there the pointer next address will point to the new node.
Option D will provide the above steps.
Q
Question 35 
doubly linked list  
singly linked list  
singly linked circular list  
singly linked list with header node 
Doubly linked list: Since it is doubly linked list so last node will have pointer to its previous node(i.e “n1” ) node. So (n1)th node can be deleted in O(1) time. Single Linked List: Since in this no node have a pointer to its previous node so even if we have a pointer on last node of the list we have to traverse (n1) nodes of the given linked list in order to delete (n1)th node. Hence its time complexity will be O(n). singly linked circular list: For above scenario since the list is unidirect so we have to traverse (n1) elements in best case in order to delete (n1)th node even after having a pointer to nth node.
singly linked list with header node is nothing but Single linked list only. So its time complexity will also be O(n).
Hence Doubly linked list is giving best time complexity to delete a node pointed by ‘p’ from a large collection of nodes constituting the list.
Question 36 
insertion of a node at a position ‘p’  
deletion of a node pointed by ‘p’  
reversing the order of the nodes in the list
 
concatenating two lists into one list 
Question 37 
The operation of processing each element in the list is known as
sorting  
merging  
inserting  
traversal 
Question 38 
Polynomial addition is implemented using ___ data structure.
Trees  
Queue  
Linked List  
Stack

Time complexity of the above algorithm and program is O(m+n) where m and n are orders of two given polynomials.
Question 39 
The time complexity of searching an element in linked n will be:
O(nlogn)
 
O(logn)
 
O(n)
 
O(n^{2})

Question 40 
Insertion  
Binary search  
Radix sort  
Polynomial manipulation 