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 NULL-terminated linked lists, invocation of join will

 A append list m to the end of list n for all inputs. B either cause a null pointer dereference or append list m to the end of list n. C cause a null pointer dereference for all inputs. D append list n to the end of list m for all inputs.
Question 1 Explanation:
As specified in the question m & n are valid lists, but there is no specific condition/ statement tells that lists are empty or not.
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 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: Θ(Ndelete,O(logN) insert, O(logN) ﬁnd, and Θ(N) decrease-key. What is the time complexity of all these operations put together?

 A O(log2 N) B O(N) C O(N2) D Θ(N2 logN)
Question 2 Explanation:
→ 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(N2)
So, overall time complexity is, O(N2).
 Question 3

The following C function takes a simply-linked 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 *p, *q;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
_______________________________
}```

Choose the correct alternative to replace the blank line.

 A q = NULL; p→next = head; head = p; B q→next = NULL; head = p; p→next = head; C head = p; p→next = q; q→next = NULL; D q→next = NULL; p→next = head; head = p;
Question 3 Explanation:
C function takes a simple linked list as input argument.
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 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 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;
}
}```
 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
Question 4 Explanation:
The given list is 1,2,3,4,5,6,7.
After 1st Iteration: 2,1,3,4,5,6,7
2nd Iteration: 2,1,4,3,5,6,7
3rd 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? A rear node B front node C not possible with a single pointer D node next to front
Question 5 Explanation:
We can perform enqueue and dequeue from rear within O(1) time. But from the front node we cannot rear from front in O(1) time.
 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?

 A union only B intersection, membership C membership, cardinality D union, intersection
Question 6 Explanation:
Let no. of elements in list 1 be n1.
Let no. of elements in list 2 be n2.
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(n1×n2).
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(n1 × n2).
Membership:
In this we search if particular element is present in the list or not. So time complexity will be O(n1 + n2).
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(n1+n2).
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

 A the list is empty or has exactly one element B the elements in the list are sorted in non-decreasing order of data value C the elements in the list are sorted in non-increasing order of data value D not all elements in the list have the same data value
Question 7 Explanation:
It return a value '1' when the elements in the list are presented in sorted order and non-decreasing order of 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

 A log n B n/2 C (log2)n - 1 D n
Question 8 Explanation:
Worst case time complexity of singly linked list is O(n). So we need n number of comparisons needed to search a singly linked list of length 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?

 A Singly linked list B Doubly linked list C Circular doubly linked list D Array implementation of list
Question 9 Explanation:
In circular doubly linked list concatenation of two lists is to be performed on O(1) time.
 Question 10

Linked lists are not suitable data structures of which one of the following problems?

 A Insertion sort B Binary search C Radix sort D Polynomial manipulation
Question 10 Explanation:
In linked list finding an element take O(n) which is not suitable for the binary search. And time complexity of binary search is O(log n).
 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?

 A θ(n log n) B θ(n2) C θ(1) D θ(n)
Question 11 Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
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.
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(n2) and heap sort will not be suitable to apply.
 Question 12

In a circular linked list organisation, insertion of a record involves modification of

 A One pointer. B Two pointers. C Multiple pointers. D No pointer.
Question 12 Explanation:
Suppose we have to insert node p after node q then
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 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)
Question 13 Explanation:
Worst case complexity for deleting a node from singly linked list is O(1).
 Question 14
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
 A Delete the last element of the list B Delete the first element of the list C Add an element after the last element of the list D Interchange the first two elements of the list
Question 14 Explanation:
F and L must point to the first and last elements respectively.
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
Given two statements:
(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
 A Both are true B Both are false C First is false and second is true D None of the above
Question 15 Explanation:
There are three situation for inserting element and deleting an element in Circular linked list.
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
In a doubly linked list, the number of pointers affected for an insertion operation will be
 A 4 B 0 C 1 D None of these
Question 16 Explanation:
It depends on whether to insert the node at first, middle or last. No proper input in question.
Note: Excluded for evaluation.
 Question 17
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?
 A Deleting a node whose location is given B Searching an unsorted list for a given item C Inserting a node after the node with a given location D Traversing the list to process each node
Question 17 Explanation:
Searching node / traversing the list means we need to traverse the entire list whether it may be linear linked list or doubly linked list.
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
The minimum number of fields with each node of doubly linked list is
 A 1 B 2 C 3 D 4
Question 18 Explanation:
Explanation: In general, each node of doubly link list always has 3 fields, i.e., the previous node pointer, the data field, and the next node pointerSo, answer should be option (C) 3.
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
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? A Delete the first element of the list B Interchange the first two elements of the list C Delete the last element of the list D Add an element at the end of the list
Question 19 Explanation:
1. Two pointers are pointing to first and last node in the linked 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
What does the following functions do for a given Linked list with first node as head?
{
return;
}
 A Prints all nodes of linked lists B Prints all nodes of linked list in reverse order C Prints alternate nodes of Linked List D Prints alternate nodes in reverse order
Data-Structures       Linked-List       Nielit Scientist-B CS 22-07-2017
Question 20 Explanation:
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.
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
Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next
{
struct node *temp=NULL;
while(current!=NULL)
{
temp=current → prev;
Current → prev=current → next;
Current → next=temp;
current=current → prev;
}
if(temp!=NULL)
}
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?
 A 1<-->2<-->4<-->3<-->6<-->5 B 5<-->4<-->3<-->2<-->1<-->6 C 6<-->5<-->4<-->3<-->2<-->1 D 6<-->5<-->4<-->3<-->1<-->2
Data-Structures       Linked-List       Nielit Scientist-B CS 22-07-2017
Question 21 Explanation:
Struct node *current=*head_ref; ---> This statement meant for storing start of linked list onto current pointer.
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
In a circularly linked list organization, insertion of a record involves the modification of
 A no pointer B 1 pointer C 2 pointer D 3 pointer
Data-Structures       Linked-List       Nielit Scientist-C 2016 march
Question 22 Explanation:
Suppose we have to insert node “x” after node “n1” then
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 best-known algorithm to delete the node a, pointer to this node is q, from the list ?

 A O(1) B O(lg n) C O(n) D O(n lg n)
Question 23 Explanation:
If we have pointer to the tail of the list in order to delete it, which can be obtained by traversing the list which takes O(n) time.
 Question 24
Which of the following is the correct declaration of linked list?
 A Struct node* { Int data; node*link; } B Struct node { int data; Struct node*link; } C Struct node { int data; node link; } D Struct node* { int data; struct node*link; }
Question 24 Explanation:
Declaration syntax is
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?

 A Obtain a node from available list B Make the next pointer of the current head pointer to new node C Make the node pointer of the list pointer to new node D Make the next pointer of the new node pointer to current head of the list
Data-Structures       Linked-List       JT(IT) 2016 PART-B Computer Science
Question 25 Explanation:
• Option A: If we want to insert a node but the node is already in available list we can’t insert a node at beginning.
• Option B, C and D: It shows actual procedure to insert a node at beginning. So, Option A is wrong
 Question 26
Given m and n as pointers to two linked lists, what does the following functions do? Void op(node *m,node *n) { Node *p=m; while(P→ next !=null) { P=P→ next; } P→ next=n; }
 A Always appends list ‘m’ at the end of list ‘n’ B Always appends list ‘n’ at the end of list ‘m’ C Append list ‘m’ at the end of list ‘n’ with possibility of error D Appends list ‘n’ at the end of list ‘m’ with possibility of error
Data-Structures       Linked-List       KVS 30-12-2018 Part B
Question 26 Explanation:
→The while loop will traverse the at the end of the list “m” and this is appended to the link list “n”.
→Non-availability of the any one of the linked list leads to possibility of error.
 Question 27
Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in O(1) time ?
 A Insertion at the front of the linked list. B Insertion at the end of the linked list. C Deletion of the front node of the linked list. D Deletion of the last node of the linked list.
Programmin-in-c       Linked-list       UGC NET CS 2016 Aug- paper-2
Question 27 Explanation:
→ Linked list best case complexity is O(1) Possibilities are
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
What operation is supported in constant time by the doubly linked list, but not by the singly linked list ?
 A Advance B Backup C First D Retrieve
Data-Structures       Linked-List       UGC NET CS 2004 Dec-Paper-2
Question 28 Explanation:
→ Backup operation is supported in constant time by the doubly linked list, but not by the singly linked list.
 Question 29
Consider the singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list ?
 A O(1) B O(lg n) C O(n) D O(n lg n)
Data-Structures       Linked-List       UGC NET CS 2018-DEC Paper-2
Question 29 Explanation:
If we have pointer to the tail of the list in order to delete it, which can be obtained by traversing the list which takes O(n) time.
 Question 30
The efficient data structure to insert/delete a number in a stored set of numbers is
 A Queue B Linked list C Doubly linked list D Binary tree
Data-Structures       Linked-List       UGC NET CS 2013 Sep-paper-2
Question 30 Explanation:
Doubly linked list is the efficient data structure to insert/delete a number in a stored set of numbers. Question 31
Linked Lists are not suitable for _____.
 A Binary Search B Polynomial Manipulation C Insertion D Radix Sort
Data-Structures       Linked-List       UGC NET CS 2013 Sep-paper-2
Question 31 Explanation:
Linked Lists are not suitable for binary search.
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
If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a non-empty queue ?
 A Neither of the pointers change B Only front pointer changes C Only rear pointer changes D Both of the pointers changes
Data-Structures       Linked-List       UGC NET CS 2013 Dec-paper-2
Question 32 Explanation: Observe 1, 2, 3 whenever we are inserting an element into a queue (singly linked list) we are updating Rear pointer.
 Question 33
With regard to linked list, which of the following statement is false ?
 A An algorithm to search for an element in a singly linked list requires 0(n) operations in the worst case. B An algorithm for deleting the first element in a singly linked list requires 0(n) operations in the worst case. C An algorithm for finding the maximum value in a circular linked list requires 0(n) operations. D An algorithm for deleting the middle node of a circular linked list requires 0(n) operations.
Data-Structures       Linked-List       UGC NET CS 2009 Dec-Paper-2
Question 33 Explanation:
Deleting the first element in a singly linked list requires 0(1) operations in the worst case.
 Question 34
Consider the following linked list: Which of the following piece of code will insert the node pointed to by q at the end of the list ?
 A for (p=list; p !=NULL; p=p →next); p=q; B for (p=list; p !=NULL; p=p →next); p →next=q; C for (p=list; p →next!=NULL; p=p→next); p=q; D for (p=list; p →next !=NULL; p=p →next); p →next=q;
Data-Structures       Linked-List       UGC NET CS 2007-Dec-Paper-2
Question 34 Explanation:
→ n order to add a new node to the end of the list, first we need to traverse the entire list.
→ 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
Which of the following types of the linked list is fastest to delete a node pointed by ‘p’ from a large collection of nodes constituting the list?
Question 35 Explanation:
Worst case of deleting a node from a linked list is when we are on the last node of the list and we want to delete (n-1)th node from the list. In this case above lists will have the following time complexity:
Doubly linked list: Since it is doubly linked list so last node will have pointer to its previous node(i.e “n-1” ) node. So (n-1)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 (n-1) nodes of the given linked list in order to delete (n-1)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 (n-1) elements in best case in order to delete (n-1)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
Singly linked circular list with header pointing to the last node is the data structure preferred in the context of
 A insertion of a node at a position ‘p’ B deletion of a node pointed by ‘p’ C reversing the order of the nodes in the list D concatenating two lists into one list
Question 36 Explanation:
Singly linked circular list with header pointing to the last node is the data structure preferred in the context of concatenating two lists into one list, because it can be done in O(1) time.
 Question 37

The operation of processing each element in the list is known as

 A sorting B merging C inserting D traversal
Question 37 Explanation:
The operation of processing each element in the list is simply known as traversal because we are just traversing the list.
 Question 38

Polynomial addition is implemented using ___ data structure.

 A Trees B Queue C Linked List D Stack
Question 38 Explanation:
Polynomial addition algorithm is implemented using either array or linked list data structure.
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:

 A O(nlogn) B O(logn) C O(n) D O(n2)