Data Structure Quiz Questions!

1. Which one of the following is an application of Queue Data Structure?

When a resource is shared among multiple consumers

When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes

Load Balancing

All of these

The correct answer is "all of these". Queue data structure can be used in various scenarios. When a resource is shared among multiple consumers, a queue can be used to manage the access and ensure fairness. When data is transferred asynchronously between two processes, a queue can be used to buffer the incoming and outgoing data. Additionally, in load balancing, a queue can be used to distribute the workload among multiple servers or processes. Therefore, all of the given options are valid applications of a queue data structure.

Explanation

The correct answer is "all of these". Queue data structure can be used in various scenarios. When a resource is shared among multiple consumers, a queue can be used to manage the access and ensure fairness. When data is transferred asynchronously between two processes, a queue can be used to buffer the incoming and outgoing data. Additionally, in load balancing, a queue can be used to distribute the workload among multiple servers or processes. Therefore, all of the given options are valid applications of a queue data structure.

2. Let the following circular queue can accommodate maximum six elements with the             following data
            front = 2 rear = 4
            queue = __ , L, M, N, ___, ___
What will happen after insert O operation takes place?

Front = 2 rear = 5 queue = __, L, M, N, O, ___

Front = 3 rear = 5 queue = __, L, M, N, O, ___

Front = 3 rear = 4 queue = __, L, M, N, O, ___

Front = 2 rear = 4 queue = L, M, N, O, ___

After the insert O operation takes place, the rear pointer will move to the next empty position in the circular queue, which is at index 5. The element "O" will be inserted at this position. Therefore, the front and rear pointers will be updated to front = 2 and rear = 5 respectively. The circular queue will then contain the elements L, M, N, O in that order.

Explanation

After the insert O operation takes place, the rear pointer will move to the next empty position in the circular queue, which is at index 5. The element "O" will be inserted at this position. Therefore, the front and rear pointers will be updated to front = 2 and rear = 5 respectively. The circular queue will then contain the elements L, M, N, O in that order.

3. What is a leaf node in a tree?

Node with 1 child

Node with n children

Node with zero child

None of these

A leaf node in a tree refers to a node that does not have any children. In other words, it is a node that is located at the end of a branch and does not have any further branches extending from it. This means that it is the last node in a particular path of the tree and does not have any descendants.

Explanation

A leaf node in a tree refers to a node that does not have any children. In other words, it is a node that is located at the end of a branch and does not have any further branches extending from it. This means that it is the last node in a particular path of the tree and does not have any descendants.

4. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for "stack full" is

(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)

Top1 + top2 = MAXSIZE

(top1= MAXSIZE/2) or (top2 = MAXSIZE)

Top1= top2 -1

The condition for "stack full" is that the variable top1 is equal to top2 minus 1. This means that the topmost element in the first stack (top1) is one position less than the topmost element in the second stack (top2). This ensures that both stacks are utilizing the available space efficiently and there is no wasted space between them.

Explanation

The condition for "stack full" is that the variable top1 is equal to top2 minus 1. This means that the topmost element in the first stack (top1) is one position less than the topmost element in the second stack (top2). This ensures that both stacks are utilizing the available space efficiently and there is no wasted space between them.

5. What does the following function do for a given Linked List? void fun2(struct Node* head) { if(start== NULL) return; printf("%d ", start->data); if(start->next != NULL ) fun2(start->next->next); printf("%d ", start->data); }

Print the linked list from beginning

Print the alternate node of the linked list

Print the first node only

None of the these

The given function, fun2, prints the alternate nodes of the linked list. It first checks if the head of the linked list is NULL, and if so, it returns. Then it prints the data of the current node (start) and checks if the next node (start->next) is not NULL. If it is not NULL, it recursively calls the function with the next next node (start->next->next). Finally, it prints the data of the current node again. This process continues until all the alternate nodes are printed.

Explanation

The given function, fun2, prints the alternate nodes of the linked list. It first checks if the head of the linked list is NULL, and if so, it returns. Then it prints the data of the current node (start) and checks if the next node (start->next) is not NULL. If it is not NULL, it recursively calls the function with the next next node (start->next->next). Finally, it prints the data of the current node again. This process continues until all the alternate nodes are printed.

6. A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

An array of 50 numbers

An array of 100 numbers

An array of 500 numbers

A dynamically allocated array of 550 numbers

Since the program is only interested in the frequency of scores above 50, it would be sufficient to store the frequencies in an array of 50 numbers. This is because the range of possible scores is [0..100], and any score below or equal to 50 would not be counted. Therefore, an array of 50 numbers would be the most efficient way to store the frequencies of scores above 50.

Explanation

Since the program is only interested in the frequency of scores above 50, it would be sufficient to store the frequencies in an array of 50 numbers. This is because the range of possible scores is [0..100], and any score below or equal to 50 would not be counted. Therefore, an array of 50 numbers would be the most efficient way to store the frequencies of scores above 50.

7. Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 < k <= n: reverse (s, 1, k);reverse (s, k + 1, n);reverse (s, 1, n);

Rotates s left by k positions

Leaves s unchanged

Reverses all elements of s

None of the above

The given sequence of operations reverses the order of elements in the array s between positions 1 and k, then reverses the order of elements between positions k+1 and n, and finally reverses the entire array s. This sequence effectively rotates the array s left by k positions.

Explanation

The given sequence of operations reverses the order of elements in the array s between positions 1 and k, then reverses the order of elements between positions k+1 and n, and finally reverses the entire array s. This sequence effectively rotates the array s left by k positions.

8. An item that is read as input can be either pushed to a stack and later popped and printed, or printed directly. Which of the following will be the output if the input is the sequence of items 1, 2, 3, 4, 5?

3, 4, 5, 1, 2

3, 4, 5, 2, 1

1, 5, 2, 3, 4

5, 4, 3, 1, 2

The given sequence of items 1, 2, 3, 4, 5 will be pushed to the stack in the order they are read. However, when popping and printing the items, the last item pushed will be the first one to be popped and printed. Therefore, the output will be 3, 4, 5, 2, 1.

Explanation

The given sequence of items 1, 2, 3, 4, 5 will be pushed to the stack in the order they are read. However, when popping and printing the items, the last item pushed will be the first one to be popped and printed. Therefore, the output will be 3, 4, 5, 2, 1.

9. Stack A has the entries a, b, c (with a on top), Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of stack B can only be printed. In the arrangement, which of the following permutations of printed values (a, b, c) is not possible?

B a c

B c a

C a b

A b c

The given arrangement allows for printing the values in the order of a, b, c. This means that the permutation b a c is not possible because it contradicts the allowed order.

Explanation

The given arrangement allows for printing the values in the order of a, b, c. This means that the permutation b a c is not possible because it contradicts the allowed order.

10. What does the following function do for a given Linked List? void fun1(struct Node* start) { if( start == NULL) return; fun1(start->next); printf("%d ", start->data); }

Print the linked list from beginning

Print the linked list after first node

Print the first node only

None of these

The given function, fun1, recursively calls itself with the next node in the linked list until it reaches the end (start == NULL). Then, it prints the data of each node in reverse order. Therefore, the function does not print the linked list from the beginning, nor does it print the linked list after the first node, or print only the first node. Hence, the correct answer is "none of these".

Explanation

The given function, fun1, recursively calls itself with the next node in the linked list until it reaches the end (start == NULL). Then, it prints the data of each node in reverse order. Therefore, the function does not print the linked list from the beginning, nor does it print the linked list after the first node, or print only the first node. Hence, the correct answer is "none of these".