Data Structure Skills Quiz! Trivia

1. Which of the following real-world scenarios would you associate with a stack data structure?

Piling up of chairs one above the other

People standing in a line to be serviced at a counter

Offer services based on the priority of the customer

All of the above

The scenario of piling up chairs one above the other can be associated with a stack data structure because a stack follows the Last-In-First-Out (LIFO) principle. Just like when we pile up chairs, the last chair we put on top will be the first one to be removed when we want to take a chair from the pile. Similarly, in a stack data structure, the most recently added element is the first one to be removed.

Explanation

The scenario of piling up chairs one above the other can be associated with a stack data structure because a stack follows the Last-In-First-Out (LIFO) principle. Just like when we pile up chairs, the last chair we put on top will be the first one to be removed when we want to take a chair from the pile. Similarly, in a stack data structure, the most recently added element is the first one to be removed.

2. What is the output of the following code? void my_recursive_function(int n) { if(n == 0) return; printf("%d ",n); my_recursive_function(n-1); } int main() { my_recursive_function(10); return 0; }

10

1

10 9 8 ……. 1 0

10 9 8 ……. 1

The code defines a recursive function called "my_recursive_function" that takes an integer parameter "n". If "n" is equal to 0, the function returns. Otherwise, it prints the value of "n" and then calls itself with the parameter "n-1".

In the main function, "my_recursive_function" is called with the argument 10. This means that the function will be called recursively 10 times, each time printing the value of "n" and then calling itself with "n-1".

Therefore, the output of the code will be a sequence of numbers from 10 to 1, with each number separated by a space.

Explanation

The code defines a recursive function called "my_recursive_function" that takes an integer parameter "n". If "n" is equal to 0, the function returns. Otherwise, it prints the value of "n" and then calls itself with the parameter "n-1".

In the main function, "my_recursive_function" is called with the argument 10. This means that the function will be called recursively 10 times, each time printing the value of "n" and then calling itself with "n-1".

Therefore, the output of the code will be a sequence of numbers from 10 to 1, with each number separated by a space.

3. Which data structure can be used suitably to solve the Tower of Hanoi problem?

Tree

Heap

Priority Queue

Stack

The Tower of Hanoi problem involves moving a stack of disks from one peg to another, following specific rules. A stack is a suitable data structure for this problem because it follows the Last-In-First-Out (LIFO) principle, which aligns with the rules of the Tower of Hanoi problem. By using a stack, we can easily keep track of the disks and their order, allowing us to move them according to the problem's constraints.

Explanation

The Tower of Hanoi problem involves moving a stack of disks from one peg to another, following specific rules. A stack is a suitable data structure for this problem because it follows the Last-In-First-Out (LIFO) principle, which aligns with the rules of the Tower of Hanoi problem. By using a stack, we can easily keep track of the disks and their order, allowing us to move them according to the problem's constraints.

4. How many times is the recursive function called, when the following code is executed? void my_recursive_function(int n) { if(n == 0) return; printf("%d ",n); my_recursive_function(n-1); } int main() { my_recursive_function(10); return 0; }

9

10

11

12

The recursive function is called 11 times because it is called recursively until the base case is reached, which is when n becomes 0. In this case, the function is initially called with n = 10, and then it is called again with n = 9, 8, 7, 6, 5, 4, 3, 2, 1, and finally 0. So, the function is called a total of 11 times.

Explanation

The recursive function is called 11 times because it is called recursively until the base case is reached, which is when n becomes 0. In this case, the function is initially called with n = 10, and then it is called again with n = 9, 8, 7, 6, 5, 4, 3, 2, 1, and finally 0. So, the function is called a total of 11 times.

5. What does the following piece of code do? public Object function() { if(isEmpty()) return -999; else { Object high; high = q[front]; return high; } }

Dequeue

Enqueue

Return the front statement

None

The given piece of code is a function that returns the element at the front of a queue. It first checks if the queue is empty using the isEmpty() function. If the queue is empty, it returns -999 as a placeholder value. Otherwise, it assigns the value at the front of the queue to the variable 'high' and returns it. Therefore, the correct answer is "return the front statement".

Explanation

The given piece of code is a function that returns the element at the front of a queue. It first checks if the queue is empty using the isEmpty() function. If the queue is empty, it returns -999 as a placeholder value. Otherwise, it assigns the value at the front of the queue to the variable 'high' and returns it. Therefore, the correct answer is "return the front statement".

6.

What is the output of the following code?

#include<stdio.h> int recursive_search_num(int *arr, int num, int idx, int len) { if(idx == len) return -1; if(arr[idx] == num) return idx; return recursive_search_num(arr, num, idx+1, len); } int main() { int arr[8] ={-11,2,-3,0,3,5,-6,7},num = -2,len = 8; int indx = recursive_search_num(arr,num,0,len); printf("Index of %d is %d",num,indx); return 0; }

Index of -2 is 1

Index of -2 is 0

Index of -2 is -1

None

The code is implementing a recursive search function called recursive_search_num. It takes an array, a number to search for, the current index, and the length of the array as parameters.

In the main function, an array arr is initialized with values {-11,2,-3,0,3,5,-6,7}, and the number to search for is -2. The length of the array is 8.

The recursive_search_num function is called with the array, the number, the initial index 0, and the length 8.

Inside the recursive_search_num function, it checks if the current index is equal to the length of the array. If it is, it means the number was not found in the array, so it returns -1.

If the current element at the index is equal to the number, it means the number was found, so it returns the current index.

If neither of the above conditions is true, it calls the recursive_search_num function again with the incremented index.

In this case, the number -2 is not present in the array arr, so the function will go through all the elements and reach the end of the array without finding the number. Therefore, the output will be "Index of -2 is -1".

Explanation

The code is implementing a recursive search function called recursive_search_num. It takes an array, a number to search for, the current index, and the length of the array as parameters.

In the main function, an array arr is initialized with values {-11,2,-3,0,3,5,-6,7}, and the number to search for is -2. The length of the array is 8.

The recursive_search_num function is called with the array, the number, the initial index 0, and the length 8.

Inside the recursive_search_num function, it checks if the current index is equal to the length of the array. If it is, it means the number was not found in the array, so it returns -1.

If the current element at the index is equal to the number, it means the number was found, so it returns the current index.

If neither of the above conditions is true, it calls the recursive_search_num function again with the incremented index.

In this case, the number -2 is not present in the array arr, so the function will go through all the elements and reach the end of the array without finding the number. Therefore, the output will be "Index of -2 is -1".

7. What is the time complexity of inserting a node in a doubly linked list?

O(nlogn)

O(logn)

O(n)

O(1)

The time complexity of inserting a node in a doubly linked list is O(n). This is because in order to insert a node, we need to traverse the list to find the correct position for insertion. This traversal takes a linear amount of time, proportional to the number of nodes already present in the list. Therefore, the time complexity is O(n).

Explanation

The time complexity of inserting a node in a doubly linked list is O(n). This is because in order to insert a node, we need to traverse the list to find the correct position for insertion. This traversal takes a linear amount of time, proportional to the number of nodes already present in the list. Therefore, the time complexity is O(n).

8. What is the space complexity of the post-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)

O(1)

O(nlogd)

O(logd)

O(d)

The space complexity of the post-order traversal in the recursive fashion is O(d). This is because in a post-order traversal, the recursive function calls are made for each node in the tree, and the maximum depth of the recursion is equal to the depth of the tree. Therefore, the space required for the recursive function calls is proportional to the depth of the tree, resulting in a space complexity of O(d).

Explanation

The space complexity of the post-order traversal in the recursive fashion is O(d). This is because in a post-order traversal, the recursive function calls are made for each node in the tree, and the maximum depth of the recursion is equal to the depth of the tree. Therefore, the space required for the recursive function calls is proportional to the depth of the tree, resulting in a space complexity of O(d).

9. Struct Node{ int val; struct Node *next; }*head; int get_max() { struct Node* temp = head->next; int max_num = temp->val; while(______) { if(temp->val > max_num) max_num = temp->val; temp = temp->next; } return max_num; } Which of the following lines should be inserted to complete the above code?

Temp->next!=0

Head->next!=0

Head != 0

In order to iterate through the linked list and find the maximum value, a condition needs to be added to the while loop to ensure that the loop continues until the end of the linked list is reached. The condition "temp->next!=0" checks if the next pointer of the current node is not NULL, indicating that there is still a node to iterate to. This ensures that the loop continues until the end of the linked list is reached.

Explanation

In order to iterate through the linked list and find the maximum value, a condition needs to be added to the while loop to ensure that the loop continues until the end of the linked list is reached. The condition "temp->next!=0" checks if the next pointer of the current node is not NULL, indicating that there is still a node to iterate to. This ensures that the loop continues until the end of the linked list is reached.

10. What is a dynamic array?

A variable size data structure

An array which is created at runtime

The memory to array is allocated at runtime

An array which is reallocated everytime whenever new elements have to be added

A dynamic array is a variable size data structure that allows for the allocation of memory at runtime. It is different from a static array, which has a fixed size. With a dynamic array, the memory can be reallocated whenever new elements need to be added, making it flexible and efficient for managing changing amounts of data.

Explanation

A dynamic array is a variable size data structure that allows for the allocation of memory at runtime. It is different from a static array, which has a fixed size. With a dynamic array, the memory can be reallocated whenever new elements need to be added, making it flexible and efficient for managing changing amounts of data.