# Data Structure Questions and Answers – Search an Element in a Linked List using Recursion

This set of Data Structure Questions and Answers for Entrance exams focuses 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?
a) Iterative linear search
b) Iterative binary search
c) Recursive binary search
d) Normal binary search

Explanation: 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.

2. Consider the following code snippet to search an element in a linked list:

```struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp != 0)
{
if(temp->val == value)
return 1;
_________;
}
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) temp = next
b) temp->next = temp
c) temp = temp->next
d) return 0

Explanation: The line “temp = temp->next” should be inserted to complete the above code.

3. What does the following code do?

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp != 0)
{
if(temp->val == value)
return 1;
temp = temp->next;
}
return 0;
}
int main()
{
int arr[5] = {1,2,3,4,5};
int n = 5,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
int ans = linear_search(60);
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Finds the index of the first occurrence of a number in a linked list
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

Explanation: The above code checks if a number is present in a linked list.

4. What is the output of the following code?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp != 0)
{
if(temp->val == value)
return 1;
temp = temp->next;
}
return 0;
}
int main()
{
int arr[5] = {1,2,3,4,5};
int n = 5,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
int ans = linear_search(-1);
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Found
c) Compile time error
d) Runtime error

Explanation: Since the number -1 is not present in the linked list, the program prints not found.

5. What is the time complexity of the following implementation of linear search on a linked list?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp != 0)
{
if(temp->val == value)
return 1;
temp = temp->next;
}
return 0;
}
int main()
{
int arr[5] = {1,2,3,4,5};
int n = 5,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
int ans = linear_search(-1);
if(ans == 1)
printf("Found");
else
return 0;
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Explanation: The time complexity of the above implementation of linear search on a linked list is O(n).

6. What is the output of the following code?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(int value)
{
while(temp -> next != 0)
{
if(temp->val == value)
return 1;
temp = temp->next;
}
return 0;
}
int main()
{
int arr[6] = {1,2,3,4,5,6};
int n = 6,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
int ans = linear_search(60);
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Found
c) Compile time error
d) Runtime error

Explanation: 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.

7. Can binary search be applied on a sorted linked list in O(Logn) time?
a) No
b) Yes

Explanation: Since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in O(Logn) time.

8. What will be time complexity when binary search is applied on a linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Explanation: The time complexity will be O(n) when binary search is applied on a linked list.

9. Consider the following recursive implementation of linear search on a linked list:

```struct Node
{
int val;
struct Node* next;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return _________;
}```

Which of the following lines should be inserted to complete the above code?
a) 1
b) 0
c) linear_search(temp, value)
d) linear_search(temp->next, value)

Explanation: The line “linear_search(temp->next, value)”, should be inserted to complete the above code.

10. What is the output of the following code?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return linear_search(temp->next, value);
}
int main()
{
int arr[6] = {1,2,3,4,5,6};
int n = 6,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
if(ans == 1)
printf("Found");
else
return 0;
}```

a) Found
c) Compile time error
d) Runtime error

Explanation: Since the element 6 is present in the linked list, the program prints “Found”.

11. How many times is the function linear_search() called when the following code is executed?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return linear_search(temp->next, value);
}
int main()
{
int arr[6] = {1,2,3,4,5,6};
int n = 6,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
if(ans == 1)
printf("Found");
else
return 0;
}```

a) 5
b) 6
c) 7
d) 8

Explanation: The function linear_search() is called 6 times when the above code is executed.

12. What is the time complexity of the following recursive implementation of linear search?

```#include<stdio.h>
#include<stdlib.h>
struct Node
{
int val;
struct Node* next;
int linear_search(struct Node *temp,int value)
{
if(temp == 0)
return 0;
if(temp->val == value)
return 1;
return linear_search(temp->next, value);
}
int main()
{
int arr[6] = {1,2,3,4,5,6};
int n = 6,i;
struct Node *temp;
for(i=0; i<n; i++)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = 0;
newNode->val = arr[i];
temp->next = newNode;
temp = temp->next;
}
if(ans == 1)
printf("Found");
else
return 0;
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Explanation: The time complexity of the above recursive implementation of linear search is O(n).

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]