Basic Data Structure Questions and Answers 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
Answer: c
Clarification: The condition “temp != 0” should be checked to complete the above code.
2. What is the output of the following code?
#include
#include
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
Answer: b
Clarification: 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
#include
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)
Answer: b
Clarification: 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
#include
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
Answer: a
Clarification: 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
#include
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
Answer: d
Clarification: 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
#include
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)
Answer: d
Clarification: 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
#include
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
Answer: b
Clarification: 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
#include
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)
Answer: b
Clarification: 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
#include
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
Answer: b
Clarification: 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
#include
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
Answer: c
Clarification: 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.
and Answers.