Data Structures Quiz

Which data structure is used for implementing recursion?

• Stack

• Queue

• List

• Array

Answer explanation

Stack is the data structure used for implementing recursion. This is because each recursive call needs to remember the return address and local variables of the calling function.

These are pushed onto the call stack during function calls and popped off when the function returns, maintaining the correct execution order (LIFO – Last In, First Out).

Other structures like queues or arrays do not support this kind of execution flow naturally.

What is the value of the postfix expression 6 3 2 4 + - *?

• 74

• -18

• 22

• 40

Answer explanation

The given postfix expression is: 6 3 2 4 + – *

Step 1: Read 6 → Push to stack
Stack: [6]

Step 2: Read 3 → Push to stack
Stack: [6, 3]

Step 3: Read 2 → Push to stack
Stack: [6, 3, 2]

Step 4: Read 4 → Push to stack
Stack: [6, 3, 2, 4]

Step 5: Read + → Pop 4 and 2 → compute (2 + 4 = 6), push result
Stack: [6, 3, 6]

Step 6: Read – → Pop 6 and 3 → compute (3 – 6 = -3), push result
Stack: [6, -3]

Step 7: Read → Pop -3 and 6 → compute (6 -3 = -18), push result
Stack: [-18]

Which of the following points is/are not true about Linked List data structure when it is compared with an array?

• Random access is not allowed in a typical implementation of Linked Lists

• Access of elements in linked list takes less time than compared to arrays

• Arrays have better cache locality that can make them better in terms of performance

• It is easy to insert and delete elements in Linked List

Which of the following application makes use of a circular linked list?

• Recursive function calls

• Undo operation in a text editor

• Implement Hash Tables

• Allocating CPU to resources

Answer explanation

Circular linked lists are well-suited for applications where the data needs to be cycled through repeatedly, such as in CPU scheduling.

In operating systems, Round Robin scheduling uses a circular linked list to allocate CPU time slices to processes in a repeating cycle, moving from one process to the next and looping back to the beginning after reaching the end.

Which data structure is typically used to implement a hash table?

• Linked list

• Array

• Binary Tree

• Stack

Answer explanation

A hash table is typically implemented using an array because the hash function maps keys directly to indices in the array. This allows for efficient access and retrieval operations with average constant time complexity, O(1).

Which collision resolution technique involves maintaining a linked list of collided keys?

• Linear probing

• Quadratic probing

• Chaining

• Double hashing

Answer explanation

Chaining is a method where each bucket of the hash table holds a linked list. When a collision occurs (i.e., two keys hash to the same index), the new key is added to the list. This approach allows the hash table to handle collisions without affecting the performance of other entries.

Which of the following symbol table implementations is best suited if access time is to be minimum?

• Linear list

• Search tree

• Hash Table

• Self-organization list

Answer explanation

A hash table provides the fastest access time for symbol table implementations due to its constant time complexity, O(1), for searching, insertion, and deletion operations. This is achieved by using a hash function that maps keys to array indices.

Given an expression: (A + B^ * D) / (E - F) + G. Choose the most appropriate answer from the options given below:

• A, C, and D only

• C and D only

• A and B only

• A and D only

Answer explanation

The prefix notation (Polish notation) is created by placing operators before their operands. For the given infix expression, the prefix notation is correctly derived as +/+A^ * DB - EFG.

Statement C is correct because the order of operands in infix and postfix expressions remains the same, as the changes only involve operator placement.

Statement D is also valid since the order of operands is consistent across infix, prefix, and postfix notations.

Thus, the correct answer is C and D only.

The seven elements A, B, C, D, E, F, and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times, and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is:

• A

• B

• F

• G

Answer explanation

Initial Stack Configuration:
The elements are pushed onto the stack in reverse order. The stack starts with:
G,F,E,D,C,B,A
(Top of stack is G).

1. Pop 5 Elements from Stack and Insert into Queue:
   The first five elements popped from the stack are:
   G,F,E,D,C
   These are inserted into the queue in the same order:
   Queue: G,F,E,D,C
   Stack after popping: B,A

2. Delete 2 Elements from Queue and Push Back onto Stack:
   Two elements deleted from the queue are G and F.
   These are pushed back onto the stack in order:
   Stack: B,A,G,F
   Queue: E,D,C

Pop One Element from Stack:
The top of the stack is F. Popping it leaves:
Stack after popping: B,A,G

A priority queue is implemented as a max-heap. Initially, it has five elements. The level-order traversal of the heap is as follows: 20, 18, 15, 13, 12. Two new elements '10' and '17' are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

• 20, 18, 17, 15, 13, 12, 10

• 20, 18, 17, 12, 13, 10, 15

• 20, 18, 17, 10, 12, 13, 15

• 20, 18, 17, 13, 12, 10, 15

Answer explanation

1. Initial Heap Structure:
   The initial heap has elements:  20, 18, 15, 13, 12

2. Inserting Element '10':
   The element '10' is inserted at the next available position in the heap. Since '10' is smaller than its parent node '15', no further adjustment is needed, and the heap remains as:
   20, 18, 15, 13, 12, 10

Inserting Element '17':
Now, we insert the element '17'. '17' will be placed at the next available position (as a child of 18). After insertion, the heap is checked to maintain the max-heap property. The value '17' is compared to its parent node '18' and swapped, making the heap:
20, 18, 17, 13, 12, 10, 15