This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Floyd’s cycle-finding algorithm”.
1. Which of the following algorithm can be used to detect a cycle in a singly linked list?
a) Simplex algorithm
b) DSW algorithm
c) Floyd’s algorithm
d) Aging algorithm
View Answer
Explanation: To check whether a singly linked list contains a cycle or not, floyd’s cycle detection algorithm can be used. The idea of this algorithm is simple, it uses two pointers, where one pointer is moving fast compared to another. If both the pointer meet, there exists a cycle in the singly linked list.
2. Which happens if the fast-moving pointer(hare) reaches the tail of the linked list?
a) The other pointer points to the first node of the linked list
b) The other pointer points to the last node of the linked list
c) Cycle exists in the linked list
d) No cycle exists in the linked list
View Answer
Explanation: Floyd’s cycle detection algorithm uses two pointers. They are also referred to as tortoise and hare, as one pointer moves faster than another pointer. If the fast-moving pointer reaches the tail of the linked list, terminated by null, it means that no cycle exists in the linked list.
3. Given below is the pseudocode of floyd’s cycle detection algorithm. Which of the following best suits the blank?
Start traversing the linked list using two pointers
move one pointer with ____________________
if pointers meet at any node
{
loop exists in the linked list
}
else
{
linked list doesn’t have a loop
}a) same speed
b) one fourth the speed of another
c) twice the speed of another
d) thrice the speed of another
View Answer
Explanation: The given pseudocode is for floyd’s cycle detection algorithm. Start traversing the linked list using two-pointers. Move a pointer by one, and another by twice of it. If both the pointers meet at any node in the list, a cycle exists or else the cycle doesn’t exist in the linked list.
4. What is the time complexity of floyd’s cycle finding algorithm?
a) O(n)
b) O(n log n)
c) O(1)
d) O(n2)
View Answer
Explanation: In the floyd’s cycle finding algorithm, we use two pointers. The slow pointer moves by one and the other moves by two. One traversal of the linked list is required. Hence, the time complexity of floyd’s algorithm is O(n), where n is the total number of nodes in the linked list.
5. Floyd’s cycle detection algorithm is a pointer algorithm.
a) True
b) False
View Answer
Explanation: Floyd’s cycle detection algorithm works on the idea of using two pointers, where one pointer is moving with twice the speed of another pointer. This algorithm accesses the nodes by storing and copying pointers and checks if they are equal or not. Hence, it is a pointer algorithm.
6. What is the space complexity of floyd’s cycle finding algorithm?
a) O(1)
b) O(n)
c) O(n2)
d) O(n log n)
View Answer
Explanation: To detect a cycle in the graph, floyd’s cycle detection algorithm is used. This algorithm uses two pointers. No other extra space is required apart from these two pointers. Hence, the space complexity of this algorithm is constant.
7. Floyd’s cycle detection algorithm is also called the ‘tortoise and hare algorithm’.
a) True
b) False
View Answer
Explanation: Floyd’s cycle detection algorithm works on the basic idea of using two pointers, where one pointer is moving twice the speed of another pointer. Here, the fast-moving pointer is referred to as hare and the slow-moving pointer is referred to as tortoise. Hence, it is also called the ‘tortoise and hare algorithm’.
8. Where does the tortoise point to, when the hare has completed one iteration of the sequence?
a) First node of the linked list
b) Last node of the linked list
c) Middle node of the linked list
d) Any random node of the linked list
View Answer
Explanation: The slow pointer in the floyd’s cycle detection algorithm is referred to as tortoise and the other is referred to as hare. The hare moves twice the speed of the slow pointer. Hence, when it reaches the end of the path the tortoise will be pointing to the middle of the linked list.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice Computer Science MCQs
- Practice Programming MCQs
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Data Structure MCQ
