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

Write in Short Short Answer▾

What is the data structure used to perform recursion?

Edit

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

Edit

Explanation

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.
The Balanced B-Tree of Order 3
The Balanced Binary Tree