Linked-list

Question 1
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
       Data-Structures       Linked-List       ISRO-2018
Question 1 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 2
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
       Data-Structures       Linked-List       ISRO-2017 May
Question 2 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 3
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
       Data-Structures       Linked-List       ISRO-2017 May
Question 3 Explanation: 
It depends on whether to insert the node at first, middle or last. No proper input in question.
Note: Excluded for evaluation.
Question 4
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
       Data-Structures       Linked-list       ISRO CS 2008
Question 4 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 5
The minimum number of fields with each node of doubly linked list is
A
1
B
2
C
3
D
4
       Data-Structures       Linked-list       ISRO CS 2008
Question 5 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 6
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
       Data-Structures       Linked-List       ISRO CS 2014
Question 6 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 7
What does the following functions do for a given Linked list with first node as head?
void fun1(Struct node* head)
{
if(head==NULL)
return;
fun1(head → next);
printf("%d".head → data);
}
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 7 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.
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 8
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
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?
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 8 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 9
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 9 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 10

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 DEC Paper-2
Question 10 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 11
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;
}
       Data-Structures       Linked-List       KVS 22-12-2018 Part-B
Question 11 Explanation: 
Declaration syntax is
Struct tag_name
{
Datatype variable_name;
Struct tag_name *pointer_variable;
};
Question 12

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 12 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 13
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 13 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 14
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 14 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 15
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 15 Explanation: 
→ Backup operation is supported in constant time by the doubly linked list, but not by the singly linked list.
Question 16
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 16 Explanation: 
Doubly linked list is the efficient data structure to insert/delete a number in a stored set of numbers.

Question 17
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 17 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 18
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 18 Explanation: 

Observe 1, 2, 3 whenever we are inserting an element into a queue (singly linked list) we are updating Rear pointer.
Question 19
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 19 Explanation: 
Deleting the first element in a singly linked list requires 0(1) operations in the worst case.
Question 20
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 20 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
There are 20 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com