Data Structure Questions and Answers for Entrance exams on “Search an Element in a Linked List using Recursion”.
1. Which of the following methods can be used to search an element in a linked list? Answer: a 2. Consider the following code snippet to search an element in a linked list: Which of the following lines should be inserted to complete the above code? Answer: c 3. What does the following code do? a) Finds the index of the first occurrence of a number in a linked list Answer: c 4. What is the output of the following code? a) Found Answer: b 5. What is the time complexity of the following implementation of linear search on a linked list? a) O(1) Answer: b 6. What is the output of the following code? a) Found Answer: b 7. Can binary search be applied on a sorted linked list in O(Logn) time? Answer: a 8. What will be time complexity when binary search is applied on a linked list? Answer: b 9. Consider the following recursive implementation of linear search on a linked list: Which of the following lines should be inserted to complete the above code? 10. What is the output of the following code? a) Found Answer: a 11. How many times is the function linear_search() called when the following code is executed? a) 5 Answer: b 12. What is the time complexity of the following recursive implementation of linear search? a) O(1) Answer: b
a) Iterative linear search
b) Iterative binary search
c) Recursive binary search
d) Normal binary search
Clarification: Iterative linear search can be used to search an element in a linked list. Binary search can be used only when the list is sorted.struct Node
{
int val;
struct Node* next;
}*head;
int linear_search(int value)
{
struct Node *temp = head->next;
while(temp != 0)
{
if(temp->val == value)
return 1;
_________;
}
return 0;
}
a) temp = next
b) temp->next = temp
c) temp = temp->next
d) return 0
Clarification: The line “temp = temp->next” should be inserted to complete the above code.#include
b) Finds the index of the last occurrence of a number in a linked list
c) Checks if a number is present in a linked list
d) Checks whether the given list is sorted or not
View Answer
Clarification: The above code checks if a number is present in a linked list.#include
b) Not found
c) Compile time error
d) Runtime error
View Answer
Clarification: Since the number -1 is not present in the linked list, the program prints not found.#include
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Clarification: The time complexity of the above implementation of linear search on a linked list is O(n).#include
b) Not found
c) Compile time error
d) Runtime error
Clarification: The condition in the while loop “temp->next == 0”, checks if the current element is the last element. If the current element is the last element, the value of the current element is not compared with the value to be searched. So, even though the number 6 is present in the linked list, it will print not found.
a) No
b) Yes
Clarification: Since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in O(Logn) time.
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Clarification: The time complexity will be O(n) when binary search is applied on a linked list.struct Node
{
int val;
struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return _________;
}
a) 1
b) 0
c) linear_search(temp, value)
d) linear_search(temp->next, value)
Answer: d
Clarification: The line “linear_search(temp->next, value)”, should be inserted to complete the above code.#include
b) Not found
c) Compile time error
d) Runtime error
Clarification: Since the element 6 is present in the linked list, the program prints “Found”.#include
b) 6
c) 7
d) 8
Clarification: The function linear_search() is called 6 times when the above code is executed.#include
b) O(n)
c) O(n2)
d) O(n3)
Clarification: The time complexity of the above recursive implementation of linear search is O(n).