Search an Element in a Linked List using Recursion Quiz Online Practice Test

1. Which search technique is applicable for locating an element in a linked list?

2. Examine the following code snippet for searching 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 != NULL) {
if(temp->val == value)
return 1;
_________;
}
return 0;
}
Which line should be added to correctly complete the code?

3. What functionality does the following code provide?

#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 != NULL) {
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 = NULL;
struct Node *temp = head;
for(i = 0; i < n; i++) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = NULL;
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;
}
What does this code accomplish?

4. What will be the result when this code is executed?

#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 != NULL) {
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 = NULL;
struct Node *temp = head;
for(i = 0; i < n; i++) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = NULL;
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;
}
What output will this code produce?

5. What is the time complexity of the linear search implementation in the linked list provided below?

#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 != NULL) {
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 = NULL;
struct Node *temp = head;
for(i = 0; i < n; i++) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = NULL;
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;
}
What is the time complexity of the linear_search function in this code?

6. What will be 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 != NULL) {
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 = NULL;
struct Node *temp = head;
for(i = 0; i < n; i++) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = NULL;
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;
}
What result will be produced when this code is executed?

7. Can binary search be performed on a sorted linked list in O(log n) time complexity?

8. What is the time complexity of performing binary search on a linked list?

9. Examine the following recursive function for linear search on a linked list:

struct Node {
int val;
struct Node* next;
} *head;

int linear_search(struct Node *temp, int value) {
if(temp == NULL)
return 0;
if(temp->val == value)
return 1;
return _________;
}
Which line should be added to complete the function and ensure it correctly searches through the linked list?

10. What will be the output of the following code snippet?

#include<stdio.h>
#include<stdlib.h>

struct Node {
int val;
struct Node* next;
} *head;

int linear_search(struct Node *temp, int value) {
if(temp == NULL)
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 = NULL;
struct Node *temp = head;
for(i = 0; i < n; i++) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = NULL;
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;
}
What will be the output when this code is executed?

11. How many times does the linear_search() function get invoked during the execution of the following program?

#include<stdio.h>
#include<stdlib.h>

struct Node {
int val;
struct Node* next;
} *head;

int linear_search(struct Node *temp, int value) {
if(temp == NULL)
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 = NULL;
struct Node *temp = head;
for(i = 0; i < n; i++) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->next = NULL;
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;
}
How many times is linear_search() executed in total?