## MCQ On Linked List - Data Structure

21. Which of the following points is/are true about Linked List data structure when it is compared with array

A. Arrays have better cache locality that can make them better in terms of performance

B. It is easy to insert and delete elements in Linked List

C. Random access is not allowed in a typical implementation of Linked Lists

D. All of the mentioned

View Answer

Ans : D

Explanation: None.

22. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

A. Insertion Sort

B. Quick Sort

C. Heap Sort

D. Merge Sort

View Answer

Ans : D

Explanation: Both Merge sort and Insertion sort can be used for linked lists. The slow random-access performance of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Since worst case time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n2), merge sort is preferred.

23. Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

A. Possible if X is not last node

B. Possible if size of linked list is even

C. Possible if size of linked list is odd

D. Possible if X is not first node

View Answer

Ans : A

Explanation:
Following are simple steps.

struct node *temp = X->next;

X->data = temp->data;

X->next = temp->next;

free(temp);

24. The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end of the function.

struct node

{

int data;

struct node* next;

};

static void reverse(struct node** head_ref)

{

struct node* prev = NULL;

struct node* current = *head_ref;

struct node* next;

while (current != NULL)

{

next = current->next;

current->next = prev;

current = next;

}

/*ADD A STATEMENT HERE*/

}

What should be added in place of “/*ADD A STATEMENT HERE*/”, so that the function correctly reverses a linked list.

A. *head_ref = prev;

B. *head_ref = current;

C. *head_ref = next;

D. *head_ref = NULL;

View Answer

Ans : A

Explanation: *head_ref = prev; At the end of while loop, the prev pointer points to the last node of original linked list.

We need to change *head_ref so that the head pointer now starts pointing to the last node.

25. he 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

View Answer

Ans : B

Explanation: The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

**Also check : **

Discussion