Data Structure MCQ - Linked List
Q1.Which of the following information is stored in a doubly-linked list’s nodes?
- Value of node
- Address of next node
- Address of the previous node
- All of the above
Answer:- (D).
Explanations : Explanation: A doubly linked list stores information about the value, and addresses of previous and next nodes.
Explanations : Explanation: A doubly linked list stores information about the value, and addresses of previous and next nodes.
- Node list
- Linked list
- Primitive list
- Unordered list
Answer:- (B).
Explanations :In Linked list each node has its own data and the address of next node. These nodes are linked by using pointers. Node list is an object that consists of a list of all nodes in a document with in a particular selected set of nodes.
Explanations :In Linked list each node has its own data and the address of next node. These nodes are linked by using pointers. Node list is an object that consists of a list of all nodes in a document with in a particular selected set of nodes.
- Pointer to character
- Pointer to integer
- Node
- Pointer to node
Answer:- (D).
Explanations :Each node in a linked list contains data and a pointer (reference) to the next node. Second field contains pointer to node.
Explanations :Each node in a linked list contains data and a pointer (reference) to the next node. Second field contains pointer to node.
- O(1)
- O(n)
- θ(1)
- θ(n)
Answer:- (D).
Explanations :In case of a linked list having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time complexity is θ(n).
Explanations :In case of a linked list having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time complexity is θ(n).
- Singly linked list
- Circular doubly linked list
- Doubly linked list
- Array implementation of list
Answer:- (B).
Explanations :We can easily concatenate two lists in O (1) time using singly or doubly linked list, provided that we have a pointer to the last node at least one of the lists. But in case of circular doubly linked lists, we will break the link in both the lists and hook them together. Thus circular doubly linked list concatenates two lists in O (1) time.
Explanations :We can easily concatenate two lists in O (1) time using singly or doubly linked list, provided that we have a pointer to the last node at least one of the lists. But in case of circular doubly linked lists, we will break the link in both the lists and hook them together. Thus circular doubly linked list concatenates two lists in O (1) time.
- Binary search
- Insertion sort
- Radix sort
- Polynomial manipulation
Answer:- (A).
Explanations :It cannot be implemented using linked lists.
Explanations :It cannot be implemented using linked lists.
- Space Utilization and Computational Time
- Computational Time
- Space Utilization
- Speed Utilization
Answer:- (A).
Explanations :Linked lists saves both space and time.
Explanations :Linked lists saves both space and time.
- Insertion Sort
- Quick Sort
- Merge Sort
- Heap Sort
Answer:- (C).
Explanations :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.
Explanations :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.
1->2->3->4->5->6 void fun(struct node* start) { if(start == NULL) return; printf("%d ", start->data); if(start->next != NULL ) fun(start->next->next); printf("%d ", start->data); }
- 1 4 6 6 4 1
- 1 3 5 1 3 5
- 1 3 5 5 3 1
- 1 2 3 5
Answer:- (C).
Explanations :fun() prints alternate nodes of the given Linked List, first from head to end, and then from end to head. If Linked List has even number of nodes, then skips the last node
Explanations :fun() prints alternate nodes of the given Linked List, first from head to end, and then from end to head. If Linked List has even number of nodes, then skips the last node
- Delete the first element
- Delete the last element of the list
- Insert a new element as a first element
- Add a new element at the end of the list
Answer:- (B).
Explanations :Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer. Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node. Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list. Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.
Explanations :Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer. Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node. Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list. Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.
Copyright © 2022 Shineskill Software Pvt. Ltd., All rights reserved.