This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Triply Linked List”.
1. Where does a triply linked list contains an extra pointer in comparison to a doubly linked list?
a) Top of the node
b) Bottom of the node
c) Before the node
d) After the node
View Answer
Explanation: Doubly linked list contains a previous and a next pointer, but along with that, a triply linked list also contains an extra pointer at the top of the node, called a top pointer. The value of the top pointer is initialized to null.
2. For which of the following purpose a top pointer can be used?
a) Storing the address of the head pointer
b) Storing the address of the previous node
c) Storing the address of the next node
d) Storing equal values on the same level
View Answer
Explanation: The extra pointer in a triply linked list called as a top pointer can be used to store equal values on the same level. If we insert the nodes in the linked list in sorted order, we can store all the equal elements in such a way that they will be on the same level. Hence, they can be accessed by the top pointer.
3. Which of the following is a typical declaration of a triply linked list in C?
a)
struct node { int data; struct node *previous; struct node *top; };
b)
struct node { int data; struct node *next; struct node *top; };
c)
struct node { int data; struct node *next; struct node *previous; struct node *top; };
d)
struct node { int data; struct node *next; struct node *previous; };
Explanation: In a triply linked list, each node consists of a previous pointer, next pointer and a top pointer. The next pointer is used to point the next node in the list. Similarly, the previous pointer is used to point to the previous node and the top pointer is used to access equal values on the same level.
4. Suppose, in a triply linked list, the elements 2, 3, 3, 5, 5, 5 and 6 are inserted in the given sequence. To which of the following elements will the top pointer point, if the linked list is traversed starting from the head?
a) \(\begin{matrix}2 & 3\; top\rightarrow 3 & 5 \;top\rightarrow 5 & 5 \; top\rightarrow 6 \end{matrix}\)
b) \(\begin{matrix}2 \; top\rightarrow 3 & 3 \;top\rightarrow 5 & 5 & 5 \; top\rightarrow 6 \end{matrix}\)
c) \(\begin{matrix}2 & 3 \; top\rightarrow 3 & 5\; top\rightarrow 5 \; top\rightarrow 5 & 6\end{matrix}\)
d) \(\begin{matrix}2 \;top\rightarrow 3\; top\rightarrow 3\; top\rightarrow 5 & 5 & 5 & 6\end{matrix}\)
View Answer
Explanation: In a triply linked list, we can store equal values at the same level. While traversing starting from the head, if a value is repeated, then the top pointer points to the repeated value. Hence, in this case, the pointer points to the second 3, second 5 and third 5.
5. A node will be rejected while inserting if the given node is already present in a triply linked list.
a) True
b) False
View Answer
Explanation: At the time of insertion, nodes are to be inserted in a sorted manner. Hence, it is important to find the correct position for the element in the list. If the given node already exists, then the node is inserted at the top of the list.
6. Which of the following is true about a triply linked list?
a) Dynamic in nature
b) Allows random access
c) Less memory wastage
d) Reverse traversing is difficult
View Answer
Explanation: Triply linked list is dynamic in nature, it allocates the memory at run time. In a linked list, elements at each node are accessed sequentially. Memory wastage is more in triply linked list, as more pointers are to be stored. Due to the presence of the previous pointer, reverse traversing is not difficult.
7. Memory usage in triply linked list is higher than doubly linked list.
a) True
b) False
View Answer
Explanation: For storing pointers, extra memory is required. Compared to a doubly linked list, a triply linked list contains an extra pointer known as a top pointer. Hence, memory usage in a triply linked list is more than a doubly linked list.
8. Consider the following algorithm to insert an element in a triply linked list.
insertelement(data)
{
create a node with given data.
if the linked list is empty
{
_____________
_____________
}
if the given node is less than the head
{
link the nodes through address and adjust the tail
}
if the given node is not less than the head
{
if the given node is equal to the head
{
new node is inserted on top of the head
}
else
{
traverse the linked list to find an element greater than the node and insert in front of the node
}
}
} Which of the following option is best suited to fill the blank?
a)
initializing previous, next and top pointers to null
pointing the head and tail to the node created
b)
pointing previous, next and top pointers to the node created
initializing the head and tail to null
c)
initializing previous, next and top pointers to null
initializing the head and tail to null
d)
pointing previous, next and top pointers to the nodeView Answer
Explanation: Whenever a node is inserted in a triply linked list, three cases arise. In case of inserting an element in an empty triply linked list, the previous, next, and the top pointers are initialized to null. The head and the tail pointers are made to point to the created node.
9. Which among the following is the time complexity for inserting at the beginning of a triply linked list?
a) O(n)
b) O(1)
c) O(log n)
d) O(n2)
View Answer
Explanation: If we want to insert an element in the front of a triply linked list, we just have to change the addresses of pointers. The following operations are performed:
Let us consider newnode as the node created and head points to the first node of the list.
newnode -> next = head newnode -> previous = null head -> prev = newnode head = newnode
These operations require constant time and hence the time complexity of inserting an element in front of a triply linked list in O(1).
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]
- Practice Programming MCQs
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Design & Analysis of Algorithms MCQ
- Check Programming Books
