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
View Answer
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; }*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
View Answer
Explanation: The line “temp = temp->next” should be inserted to complete the above code.
3. What does the following code do?
#include<stdio.h> #include<stdlib.h> 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
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; }*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
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; }*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
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; }*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
View Answer
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
View Answer
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)
View Answer
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; }*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)
View Answer
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; }*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
View Answer
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; }*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
View Answer
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; }*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)
View Answer
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.
- Check Design and Analysis of Algorithms Books
- Practice Data Structure MCQ
- Apply for Computer Science Internship
- Check Computer Science Books
- Check Programming Books
