Basic CS-Data Structures [Redpine Infotech Placement]: Sample Questions 1 - 2 of 4

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 1

Describe in Detail Essay▾

Explain two problems related to in order and post order traversal.

Edit

Explanation

Given Order Travel, Root, Left Subtree and Right Subtree

Inorder Traversal

  • Algorithm:
    • Traverse the left sub tree, i.e.. , call inorder (left-sub tree)
    • Visit the root
    • Traverse the right sub tree, i.e.. , call inorder (right-sub tree)
  • Uses of Inorder
    • Binary search trees, inorder traversal provides nodes in non-decreasing order.
    • To get nodes of BST in non-increasing order, a variation of inorder traversal where inorder traversal is reversed can be used.

    Ex

In Order Travel (Left, Root, Right)
  • In order travel (left, root, right) : 4, 2,5, 1,3

Post Order

  • Algorithm:
    • Traverse the left sub tree, i.e.. , call Postorder (left-sub tree)
    • Traverse the right sub tree, i.e.. , call Postorder (right-sub tree)
    • Visit the root.
  • Use of Postorder:
    • Used to delete the tree.
    • To get the postfix expression of expression tree.

Ex

Postorder (Left, Right, Root)

Postorder (Left, Right, Root) : 4 5 2 3 1

Question 2

Describe in Detail Essay▾

Difference between re-entrance and recursion.

Edit

Explanation

Difference between Re-Entrance and Recursion
Re-entranceRecursion
A re-entrant function can be safely executed concurrently.A recursive function calls upon itself until a given condition is met
Re-entrant function does operations like protect/lock static state.Recursive functions do not need to protect/lock access static state.
Re-entrant function needs able to handle concurrent execution with different threads.Recursive able to handle entry while it is running, but it access controlled manner and not other thread.
Re-entrant recursive functions are thread-safe.Recursive functions are not thread-safe
Re-enter functions cannot modify static variablesRecursion functions can modify static variables.