Binary-search-tree

Question 1
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
A
B
C
D
Question 1 Explanation: 

The time complexity of searching an element in T that is smaller than the maximum element in T is O(1) time.

Example:

 

Comparing that 5<10 will take only a constant amount of time.

Question 2

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

A
Θ (n log n)
B
Θ (n2n)
C
Θ (n)
D
Θ (log n)
Question 2 Explanation: 
→ Worst case running time to search for an element in a balanced binary search tree of ‘n’ elements is (log n).
→ No of elements = n.2n then search time = (log n.2n)
= (log n + log 2n)
= (log n + n log 2)
= O(n)
Question 3

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.

A
61 52 14 17 40 43
B
2 3 50 40 60 43
C
10 65 31 48 37 43
D
81 61 52 14 41 43
E
17 77 27 66 18 43
Question 4

Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

      var          i,j,k: integer; x: integer;
                   a:= array; [1...N] of integer;
      begin	   i:= 1; j:= N;
      repeat	   k:(i+j) div 2;
                   if a[k] < x then i:= k 
                   else j:= k 
      until (a[k] = x) or (i >= j);
      if (a[k] = x) then
      writeln ('x is in the array')
      else
      writeln ('x is not in the array')
      end; 
A
Theory Explanation.
Question 5

(a) In a binary tree, a nil node is defined to be a node with 2 children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves.

(b) Draw a min-heap that results from insertion of the following elements in order into an initially empty min-heap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.

A
Theory Explanation.
Question 6

(a) Insert the following keys one by one into a binary search tree in the order specified.

         15, 32, 20, 9, 3, 25, 12, 1  

Show the final binary search tree after the insertions.
(b) Draw the binary search tree after deleting 15 from it.
(c) Complete the statements S1, S2 and S3 in the following function so that the function computes the depth of a binary rooted at t.

              typedef struct tnode{
                  int key;
                  struct tnode *left, *right;
              } *Tree;
              int depth(Tree t)
              {
                  int x,y;
                  it (t == NULL) return0;
                  x=depth(t → left);
 S1:              ____________;
 S2:              if(x>y) return _____________:
 S3:              else return _____________;
              } 
A
Theory Explanation is given below.
Question 7

Let T(n) be the number of different binary search trees on n distinct elements. Then , where x is

A
n – k + 1
B
n – k
C
n – k – 1
D
n – k – 2
Question 7 Explanation: 
A binary search tree consists of n distinct elements. Let consider on left subtree, it consists of (k-1) elements. Then right subtree consists of (n-k) elements. From this we c an write recursive function as T(k-1)*(n-k) i.e.,
Question 8

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

A
7 5 1 0 3 2 4 6 8 9
B
0 2 4 3 1 6 5 9 8 7
C
0 1 2 3 4 5 6 7 8 9
D
9 8 6 4 2 3 0 1 5 7
Question 8 Explanation: 

Inorder: 0 1 2 3 4 5 6 7 8 9
Question 9
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_____________.
A
509
Question 9 Explanation: 
Array indices shown beside node

Now, the 3^rd largest number will be at location of max3. We can find what can be the probable index values of max1 at different levels. They will be 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 . . .
∴ 511 is index value of our max1
510 is index value of our max2
509 is index value of our max3
& Hence, Answer is 509
Question 10

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

A
2
B
3
C
4
D
6
Question 10 Explanation: 

Height of the binary search tree = 3
Question 11

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(nalogbn + mclogdn), the value of a + 10b + 100c + 1000d is ____.

A
110
B
111
C
112
D
113
Question 11 Explanation: 
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 n1' of >n1 such that n1' is equal to n1.
2. n22' of n2 such that is equal to n2.
Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.
So time complexity is O(log n+m)
So the given expression becomes O(n0log'n+m'log0n)
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
There are 11 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access