Programming and data structure miscellaneous

Programming and data structure miscellaneous

Easy Questions

Programming & Data Structure

Programming and data structure miscellaneous
  1. We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how ways can we populate the tree with the given set so that it becomes a binary search tree?








  1. View Hint View Answer Discuss in Forum

    It is stated that there is a binary tree and we have populate the tree with n elements. Sorting the n elements in the increasing order,and placing them in the inorder traversal nodes of the binary tree makes it only BST possible.

    Correct Option: B

    It is stated that there is a binary tree and we have populate the tree with n elements. Sorting the n elements in the increasing order,and placing them in the inorder traversal nodes of the binary tree makes it only BST possible.

  1. The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the below in invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.
    {   if (n = = NULL) return – 1;
       if (n → left = = NULL)
    if (n → right = = NULL) return 0;

    The appropriate expressions for the two boxes B1 and B2 are








  1. View Hint View Answer Discuss in Forum

    The box B1 gets executed when left subtree of n is NULL and right subtree is not NULL. In this case, height of n will be height of right subtree plus one.
    The box B2 gets executed when both left and right subtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.

    Correct Option: A

    The box B1 gets executed when left subtree of n is NULL and right subtree is not NULL. In this case, height of n will be height of right subtree plus one.
    The box B2 gets executed when both left and right subtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.

  1. The pre-order traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the post-order traversal sequence of the same tree ?








  1. View Hint View Answer Discuss in Forum

    NA

    Correct Option: D

    NA

  1. Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes ?








  1. View Hint View Answer Discuss in Forum

    The tightest upper bound that represents the time complexity of inserting an object into a binary search tree with n nodes is O (n).

    Correct Option: C

    The tightest upper bound that represents the time complexity of inserting an object into a binary search tree with n nodes is O (n).

  1. Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O (na logb n + mc logd n), the value of 10b + 100c + 1000d is _______.








  1. View Hint View Answer Discuss in Forum

    It takes (log n) time to determine numbers n1 and n2 in balanced binary search tree T such that
    1. n1 is the smallest number greater than or equal to L and there is no predecessor n¢ 1 of n1 such that n'1 is equal to n1.
    2. n2 is the largest number less than or equal to H and there is no successor of n'2 of n2 such that is equal to n2.
    Since there are m elements between n1 and n2, it takes ‘m’ time to add elements between n1 and n2.
    So time complexity is O (log n + m)
    So the given expression becomes O (n0 log' n + m' log0 n) And a + 10b + 100c + 1000d = 0 + 10 × 1 + 100 × 1 + 1000 × 1 = 10 + 100 = 110
    Because a = 0, b = 1, c = 1 and d = 0

    Correct Option: A

    It takes (log n) time to determine numbers n1 and n2 in balanced binary search tree T such that
    1. n1 is the smallest number greater than or equal to L and there is no predecessor n¢ 1 of n1 such that n'1 is equal to n1.
    2. n2 is the largest number less than or equal to H and there is no successor of n'2 of n2 such that is equal to n2.
    Since there are m elements between n1 and n2, it takes ‘m’ time to add elements between n1 and n2.
    So time complexity is O (log n + m)
    So the given expression becomes O (n0 log' n + m' log0 n) And a + 10b + 100c + 1000d = 0 + 10 × 1 + 100 × 1 + 1000 × 1 = 10 + 100 = 110
    Because a = 0, b = 1, c = 1 and d = 0