This set of Basic Data Structure Questions and Answers focuses on “Length of a Linked List using Recursion”.
1. Consider the following iterative implementation used to find the length of a linked list:
struct Node { int val; struct Node *next; }*head; int get_len() { struct Node *temp = head->next; int len = 0; while(_____) { len++; temp = temp->next; } return len; }
Which of the following conditions should be checked to complete the above code?
a) temp->next != 0
b) temp == 0
c) temp != 0
d) temp->next == 0
View Answer
Explanation: The condition “temp != 0” should be checked to complete the above code.
2. What is the output of the following code?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int get_len() { struct Node *temp = head->next; int len = 0; while(temp != 0) { len++; temp = temp->next; } return len; } int main() { int arr[10] = {1,2,3,4,5}, n = 5, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; temp = head; for(i=0; i<n; i++) { newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = arr[i]; newNode->next = 0; temp->next = newNode; temp = temp->next; } int len = get_len(); printf("%d",len); return 0; }
a) 4
b) 5
c) 6
d) 7
View Answer
Explanation: The program prints the length of the linked list, which is 5.
3. What is the time complexity of the following iterative implementation used to find the length of a linked list?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int get_len() { struct Node *temp = head->next; int len = 0; while(temp != 0) { len++; temp = temp->next; } return len; } int main() { int arr[10] = {1,2,3,4,5}, n = 5, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; temp = head; for(i=0; i<n; i++) { newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = arr[i]; newNode->next = 0; temp->next = newNode; temp = temp->next; } int len = get_len(); printf("%d",len); return 0; }
a) O(1)
b) O(n)
c) O(n2)
d) O(logn)
View Answer
Explanation: The time complexity of the above iterative implementation used to find the length of a linked list is O(n).
4. What is the output of the following code?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int get_len() { struct Node *temp = head->next; int len = 0; while(temp != 0) { len++; temp = temp->next; } return len; } int main() { int arr[10] = {1,2,3,4,5}, n = 5, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; int len = get_len(); printf("%d",len); return 0; }
a) 0
b) Garbage value
c) Compile time error
d) Runtime error
View Answer
Explanation: The program prints the length of the linked list, which is 0.
5. Which of the following can be the base case for the recursive implementation used to find the length of linked list?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int get_len() { struct Node *temp = head->next; int len = 0; while(temp != 0) { len++; temp = temp->next; } return len; } int main() { int arr[10] = {1,2,3,4,5}, n = 5, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; int len = get_len(); printf("%d",len); return 0; }
a) if(current_node == 0) return 1
b) if(current_node->next == 0) return 1
c) if(current_node->next == 0) return 0
d) if(current_node == 0) return 0
View Answer
Explanation: The line “if(current_node == 0) return 0” can be used as a base case in the recursive implementation used to find the length of a linked list. Note: The line “if(current_node->next == 0) return 1” cannot be used because it won’t work when the length of the linked list is zero.
6. Which of the following lines should be inserted to complete the following recursive implementation used to find the length of a linked list?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int recursive_get_len(struct Node *current_node) { if(current_node == 0) return 0; return _____; } int main() { int arr[10] = {1,2,3,4,5}, n = 5, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; temp = head; for(i=0; i<n; i++) { newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = arr[i]; newNode->next = 0; temp->next = newNode; temp = temp->next; } int len = recursive_get_len(head->next); printf("%d",len); return 0; }
a) recursive_get_len(current_node)
b) 1 + recursive_get_len(current_node)
c) recursive_get_len(current_node->next)
d) 1 + recursive_get_len(current_node->next)
View Answer
Explanation: The line “1 + recursive_get_len(current_node->next)” should be inserted to complete the above code.
7. What is the output of the following code?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int recursive_get_len(struct Node *current_node) { if(current_node == 0) return 0; return 1 + recursive_get_len(current_node->next); } int main() { int arr[10] = {-1,2,3,-3,4,5,0}, n = 7, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; temp = head; for(i=0; i<n; i++) { newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = arr[i]; newNode->next = 0; temp->next = newNode; temp = temp->next; } int len = recursive_get_len(head->next); printf("%d",len); return 0; }
a) 6
b) 7
c) 8
d) 9
View Answer
Explanation: The program prints the length of the linked list, which is 7.
8. What is the time complexity of the following code used to find the length of a linked list?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int recursive_get_len(struct Node *current_node) { if(current_node == 0) return 0; return 1 + recursive_get_len(current_node->next); } int main() { int arr[10] = {-1,2,3,-3,4,5,0}, n = 7, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; temp = head; for(i=0; i<n; i++) { newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = arr[i]; newNode->next = 0; temp->next = newNode; temp = temp->next; } int len = recursive_get_len(head->next); printf("%d",len); return 0; }
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer
Explanation: To find the length of the linked list, the program iterates over the linked list once. So, the time complexity of the above code is O(n).
9. What is the output of the following code?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int recursive_get_len(struct Node *current_node) { if(current_node == 0) return 0; return 1 + recursive_get_len(current_node->next); } int main() { int arr[10] = {-1,2,3,-3,4,5}, n = 6, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; temp = head; for(i=0; i<n; i++) { newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = arr[i]; newNode->next = 0; temp->next = newNode; temp = temp->next; } int len = recursive_get_len(head->next); printf("%d",len); return 0; }
a) 5
b) 6
c) 7
d) 8
View Answer
Explanation: The program prints the length of the linked list, which is 6.
10. How many times is the function recursive_get_len() called when the following code is executed?
#include<stdio.h> #include<stdlib.h> struct Node { int val; struct Node *next; }*head; int recursive_get_len(struct Node *current_node) { if(current_node == 0) return 0; return 1 + recursive_get_len(current_node->next); } int main() { int arr[10] = {-1,2,3,-3,4,5}, n = 6, i; struct Node *temp, *newNode; head = (struct Node*)malloc(sizeof(struct Node)); head->next = 0; temp = head; for(i=0; i<n; i++) { newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = arr[i]; newNode->next = 0; temp->next = newNode; temp = temp->next; } int len = recursive_get_len(head->next); printf("%d",len); return 0; }
a) 5
b) 6
c) 7
d) 8
View Answer
Explanation: The function is called “len + 1” times. Since the length of the linked list in the above code is 6, the function is called 6 + 1 = 7 times.
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]
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Computer Science Books
- Check Programming Books
