Basic CS-Data Structures [3i Infotech Placement]: Sample Questions 50 - 51 of 52
Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.
Question 50
Explanation
- Stack data structure is usually used to perform recursion.
- Recursion is a function which calls itself with an argument.
- A termination condition, the control returns to the calling function.
- Stack is container of object where objects are inserted and removed according to LIFO.
- Stacks allows two operations- push the item into the stack and pop the item out of the stack.
- Recursion makes use of system stack to store the return address, arguments and return values of the function calls.
- Some recursions can use the explicit program defined constructs.
Question 51
Describe in Detail Essay▾
Draw the balanced B-tree of order 3 created by inserting the following data arriving in sequence 92 24 6 7 11 8 22 4 5 16 19 20 78
EditExplanation
For creating balanced Binary Tree read the first array element, create a new node with data and put it in queue. Do the below operations until the queue is empty.
- Dequeue the data (Node) from queue and populate its left and Right child with data from array.
- put the Left and Right child created in step 1 in Queue.
For solving the problem, sort the array first now on this sorted array:
- Get the middle element of the array and make it as Root of Binary Search Tree:
- After getting the middle of array, it is divided into 2 parts, left half and right half.
- Middle element of Left half will become Left child of Root Node (created in step 1)
- Middle element of Right half will become Right child of Root Node (created in step 1)
- Do above step recursively for left half and right half.
- Get the middle of left half and make it left child of the root created in step 1.
- Get the middle of right half and make it right child of the root created in step 1.