Miscellaneous On Data Structures - Study Mode
[#1111] Consider the following code snippet to find the smallest element in a linked list: struct Node
{
int val
struct Node* next
}*head
int get_min()
{
struct Node* temp = head->next
int min_num = temp->val
while(temp != 0)
{
if(_________)
min_num = temp->val
temp = temp->next
}
return min_num
} Which of the following lines should be inserted to complete the above code?
Correct Answer
(C) temp->val < min_num
[#1112] What is the time complexity of the following code used to find the length of the string? #include<stdio.h>
int get_len(char *s)
{
int len = 0
while(s[len] != 'x00')
len++
return len
}
int main()
{
char *s = "lengthofstring"
int len = get_len(s)
printf("%d",len)
return 0
}
Correct Answer
(B) O(n)
[#1113] What is the time complexity of the recursive implementation used to find the largest and smallest element in a linked list? #include<stdio.h>
#include<stdlib.h>
struct Node
{
int val
struct Node* next
}*head
int max_of_two(int a, int b)
{
if(a > b)
return a
return b
}
int recursive_get_max(struct Node* temp)
{
if(temp->next == 0)
return temp->val
return max_of_two(temp->val,recursive_get_max(temp->next))
}
int min_of_two(int a, int b)
{
if(a < b)
return a
return b
}
int recursive_get_min(struct Node* temp)
{
if(temp->next == 0)
return temp->val
return min_of_two(temp->val,recursive_get_min(temp->next))
}
int main()
{
int n = 9, arr[9] ={1,3,2,4,5,0,5,6,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->next = 0
newNode->val = arr[i]
temp->next =newNode
temp = temp->next
}
int max_num = recursive_get_max(head->next)
int min_num = recursive_get_min(head->next)
printf("%d %d",max_num,min_num)
return 0
}
Correct Answer
(B) O(n)
[#1114] 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
}
Correct Answer
(B) O(n)
[#1115] What is the output of the following code? #include<stdio.h>
int sum_of_digits(int n)
{
int sm = 0
while(n != 0)
{
sm += n%10
n /= 10
}
return sm
}
int main()
{
int n = 1234
int ans = sum_of_digits(n)
printf("%d",ans)
return 0
}
Correct Answer
(D) 10