This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Unrolled Linked List”.
1. An unrolled linked list consists of which of the following data structures?
a) Linked-list and array
b) Linked-list and stack
c) Stack and array
d) Array and queue
View Answer
Explanation: An unrolled linked list is a type of linked list, which consists of a linked list with small arrays. It stores an array of fixed size at each node of the list instead of storing just one element. It reduces the memory overhead by using arrays at each node and has the advantage of faster execution of the operations like insertion and deletion due to linked list.
2. What happens if a node cannot fit an element in an unrolled linked list?
a) The element is discarded
b) The elements are moved to the next node
c) The node is discarded
d) Error message is shown
View Answer
Explanation: We can implement unrolled linked list through different algorithms. Generally, the lower watermark is set at 50%, which means if a node cannot accommodate more elements, a new node is created and half of the elements of the previous node are inserted in it. It is related to B-tree.
3. The algorithm given is for deleting an element in an unrolled linked list. What should be the correct statement for the blank given below?
Find an element in node a
a.data.delete(element)
a.elementNum--
while a.elementNum < a.data.size / 2
put element from a.next.data in a.data
a.next.elementNum--
a.elementNum++
if a.next.elementNum < a.next.data.size / 2
_______________________
_______________________a)
merge nodes a and a.next delete node a.next
b)
delete node a
merge nodes a.prev and a.nextc)
a.elementNum-- a.elementNum++
d)
a.next.elementNum-- a.next.elementNum++
Explanation: Whenever we remove an element from a node and if the number of elements drops below half of the original elements, we use elements from the neighboring node to fill up the space. However, if the number of elements present in the neighboring node also drops below half of the originally present, we merge both the nodes.
4. Insertion and deletion are much faster in an unrolled linked list than in a singly linked list.
a) True
b) False
View Answer
Explanation: As unrolled linked-list has the advantage of fast indexing from the array, searching becomes faster. Hence, in an unrolled linked-list insertion and deletion are much faster compared to a singly linked list as it jumps the entire array at once.
5. Which among the following is a typical declaration of an unrolled linked list in C?
a)
#define SIZE N struct node { int node_count; int arr[SIZE]; struct node *next; };
b)
#define SIZE N struct node { int arr[SIZE]; struct node *prev; struct node *top; };
c)
#define SIZE N struct node { int node_count; struct node *next; };
d)
#define SIZE N struct node { int node_count; int arr[SIZE]; };
Explanation: In an unrolled linked list, each node consists of an array of fixed-size elements. It also contains a pointer, which points to the next node in the list. Every node consists of a certain number of maximum elements it can hold.
6. Unrolled linked-list requires more storage space for pointers compared to a singly linked list.
a) True
b) False
View Answer
Explanation: Suppose, if we want to store 12 elements, we can use 3 arrays of size 4 at each node. This will require only 3 next pointers whereas a singly linked list will require 12 next pointers in the same case. Hence, an unrolled linked-list requires less storage space for pointers compared to a singly linked list.
7. Which of the following represents the space complexity for an unrolled linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Explanation: An unrolled linked list takes space varying from (n*c/m) to 2(n*c/m). Here, c is the overhead per node, which is constant, m is the number of maximum elements present in an array at the node and n is the total number of nodes. Hence, the space complexity for an unrolled linked list is O(n).
8. Which of the following is a drawback of an unrolled linked list?
a) Small memory overhead
b) Cache management
c) High overhead per node
d) Slow insertion and deletion
View Answer
Explanation: Suppose, we have an unrolled linked list with an array size of 10 at each node. The array is completely filled with elements. Now, if we refer to only a few of the elements present in the array, the memory used to store the rest of the elements will be wasted. This causes a high overhead per node. Hence, the overhead per node is high in an unrolled linked list compared to that of an ordinary linked list.
9. Which among the following is the time complexity for inserting an element in an unrolled linked list?
a) O(1)
b) O(n)
c) O(log n)
d) O(n2)
View Answer
Explanation: While inserting an element in an unrolled linked list, the list should be maintained in a sorted manner. Hence, we must traverse and find the node in which we want to insert, which takes O(n) time. Hence, the time complexity for inserting an element in an unrolled linked list takes O(n) time.
Sanfoundry Global Education & Learning Series – Data Structure.
To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Data Structure Books
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Programming Books
- Apply for Computer Science Internship
