250+ TOP MCQs on Search an Element in a Linked List using Recursion and Answers

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?
a) Iterative linear search
b) Iterative binary search
c) Recursive binary search
d) Normal binary search

Answer: a
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.

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

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;
}

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

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

3. What does the following code do?

#include
#include
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;
           temp = temp->next;
      }
      return 0;
}
int main()
{
      int arr[5] = {1,2,3,4,5};
      int n = 5,i;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      struct Node *temp;
      temp = head;
      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
      printf("Not found");
      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
View Answer

Answer: c
Clarification: The above code checks if a number is present in a linked list.

4. What is the output of the following code?

#include
#include
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;
           temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[5] = {1,2,3,4,5};
     int n = 5,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     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
     printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error
View Answer

Answer: b
Clarification: 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
#include
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;
           temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[5] = {1,2,3,4,5};
     int n = 5,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     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
     printf("Not found");
     return 0;
}

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

Answer: b
Clarification: 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
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      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;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     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
       printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error

Answer: b
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.

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

Answer: a
Clarification: 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)

Answer: b
Clarification: 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;
}*head;
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)
Answer: d
Clarification: 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
#include
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 linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     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(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error

Answer: a
Clarification: 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
#include
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 linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     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(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
    return 0;
}

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

Answer: b
Clarification: 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
#include
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 linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     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(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
    return 0;
}

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *